Stack

Stack Fundamentals

A stack is a Last In First Out (LIFO) data structure. Think of a stack of plates - you can only add or remove from the top.

Core Operations

Visual Example

push(1) → [1]
push(2) → [1, 2]
push(3) → [1, 2, 3]
peek()   → returns 3
pop()    → returns 3, stack becomes [1, 2]

Java Stack Implementation

// Using Java's built-in Stack
Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
int top = stack.peek();  // 2
int val = stack.pop();   // 2
boolean empty = stack.isEmpty(); // false

// Using Deque (preferred in modern Java)
Deque<Integer> deque = new ArrayDeque<>();
deque.push(1);  // or deque.addFirst(1)
deque.push(2);
int top = deque.peek();  // 2
int val = deque.pop();   // 2

Why Use Stack?

1. Undo operations - text editors, browsers
2. Function calls - recursion uses call stack
3. Expression evaluation - postfix, infix
4. Balanced parentheses - compiler syntax checking
5. Depth-First Search - graph traversal
6. Backtracking - maze solving, permutations

Stack Applications

1. Balanced Parentheses (LeetCode 20)

public boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') {
            stack.push(c);
        } else {
            if (stack.isEmpty()) return false;
            char top = stack.pop();
            if ((c == ')' && top != '(') ||
                (c == ']' && top != '[') ||
                (c == '}' && top != '{')) {
                return false;
            }
        }
    }
    return stack.isEmpty();
}
// Time: O(n), Space: O(n)

2. Min Stack (LeetCode 155)

class MinStack {
    Deque<Integer> stack;
    Deque<Integer> minStack;
    
    public MinStack() {
        stack = new ArrayDeque<>();
        minStack = new ArrayDeque<>();
    }
    
    public void push(int val) {
        stack.push(val);
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        }
    }
    
    public int pop() {
        int val = stack.pop();
        if (val == minStack.peek()) {
            minStack.pop();
        }
        return val;
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return minStack.peek();
    }
}

3. Evaluate Reverse Polish Notation (LeetCode 150)

public int evalRPN(String[] tokens) {
    Deque<Integer> stack = new ArrayDeque<>();
    for (String token : tokens) {
        switch (token) {
            case "+": stack.push(stack.pop() + stack.pop()); break;
            case "-":
                int b = stack.pop(), a = stack.pop();
                stack.push(a - b);
                break;
            case "*": stack.push(stack.pop() * stack.pop()); break;
            case "/":
                b = stack.pop(); a = stack.pop();
                stack.push(a / b);
                break;
            default: stack.push(Integer.parseInt(token));
        }
    }
    return stack.pop();
}

4. Next Greater Element (LeetCode 496)

public int[] nextGreaterElement(int[] nums1, int[] nums2) {
    Map<Integer, Integer> map = new HashMap<>();
    Deque<Integer> stack = new ArrayDeque<>();
    
    for (int num : nums2) {
        while (!stack.isEmpty() && stack.peek() < num) {
            map.put(stack.pop(), num);
        }
        stack.push(num);
    }
    
    int[] result = new int[nums1.length];
    for (int i = 0; i < nums1.length; i++) {
        result[i] = map.getOrDefault(nums1[i], -1);
    }
    return result;
}

When to Use Stack