Stacks

Intro

Another AbstractDataType that represents a sequential collection of data. Stacks are characterised by their LIFO (Last In First OUT) operation order.

Operations

The support the operations push (insert a new element on the top of the stack) and pop (remove and return the most recently added element, the element at the top of the stack).

Implementation

Similar to a Queue a Stack can also be implemented using arrays or singly linked lists. Here’s an example I built using Java’s ArrayList data type:

import java.util.ArrayList;
 
// Stack class
class MyStack {
    private int length;
    private final ArrayList<Character> items;
 
    public MyStack() {
        this.length = 0;
        this.items = new ArrayList<Character>();
    }
    
    // Insert a character to the top (end) of the stack
    public void push(char character) {
        this.items.add(character);
        this.length++;
    }
 
    // Remove and return the top character from the stack
    public void pop() {
        if (this.length > 0) {
            char popped = this.items.get(this.length - 1);
            this.items.remove(this.length - 1);
            this.length--;
        }
    }
 
    // Show the top character in the stack
    public char peak() {
        return this.items.get(this.length - 1);
    }
 
    public int size() {
        return this.length;
    }
}

Stacks and Recursion

Stacks are important for implementing and supporting nested or recursive behavior. It’s also used to implement DFS, which is either done by recursive calls or manually managing a stack.

Time complexity

Operation	Big-O
Top/Peek	O(1)
Push	O(1)
Pop	O(1)
isEmpty	O(1)
Search	O(n)

Edge cases

• Empty stack. Popping from an empty stack
• Stack with one item
• Stack with two items

Essential questions

• Valid Parentheses
• Implement Queue using Stacks

Recommended practice questions

• Implement Stack using Queues
• Min Stack
• Asteroid Collision
• Evaluate Reverse Polish Notation
• Basic Calculator
• Basic Calculator II
• Daily Temperatures
• Trapping Rain Water
• Largest Rectangle in Histogram

---

References

• Tech Interview Handbook