Stack

At a glance

The instinct

A stack shines when the most recent unfinished thing is the one that matters next. An open bracket waits for its closer, a letter waits to see if its twin arrives to cancel it, an operand waits for its operator, and an outer expression waits while an inner one is evaluated. Each time you scan left to right and the newest pending item is the only candidate to resolve, a stack turns a messy nested problem into one linear pass.

Recognise it

Not this pattern if...

• You need the next greater / smaller element for every index - that is the specialised monotonic stack.
• First come, first served (level order, sliding window max from the front) - use a queue or deque.
• You only need a count of open brackets of a single type - a plain integer counter is enough.

Memory hack

Analogy: Russian nesting dolls. You open dolls from the outside in (push), but you must close them from the inside out (pop). Any time a problem describes something closing in the reverse order it opened, picture the dolls.

Say it out loud in the interview:

1. "What do I push - the character, its index, a number, or a saved state?"
2. "What event triggers a pop, and what do I check when I pop?"
3. "What does the stack mean at the end - empty for valid, or the remaining items are the answer?"

How it works

Scan the input once. For each token decide: push (it opens or waits), pop and combine (it closes or completes something), or pop and discard (it cancels). The final stack contents, or whether it is empty, is the answer.

Worked trace for Valid Parentheses on "{[()]}":

For Basic Calculator II, push each term with its sign: +x pushes x, -x pushes -x, and * or / pop the top, combine it with the new number, and push the result. Summing the stack at the end applies the remaining additions, because the higher-precedence work has already been done.

For Longest Valid Parentheses, push indices instead of characters, and keep a base index at the bottom: the length of a valid run is i - stack.peek() after a successful pop.

Java template

import java.util.*;

class StackKit {
    // Template 1: matching pairs with an ArrayDeque used as a stack.
    static boolean isValid(String s) {
        Deque<Character> st = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (c == '(') st.push(')');            // push the EXPECTED closer
            else if (c == '[') st.push(']');
            else if (c == '{') st.push('}');
            else if (st.isEmpty() || st.pop() != c) return false;
        }
        return st.isEmpty();
    }

    // Template 2: cancel adjacent items; StringBuilder doubles as a char stack.
    static String removeAdjacent(String s) {
        StringBuilder sb = new StringBuilder();
        for (char c : s.toCharArray()) {
            int n = sb.length();
            if (n > 0 && sb.charAt(n - 1) == c) sb.deleteCharAt(n - 1); // problem-specific cancel rule
            else sb.append(c);
        }
        return sb.toString();
    }

    // Template 3: evaluate postfix tokens.
    static int evalRPN(String[] tokens) {
        Deque<Integer> st = new ArrayDeque<>();
        for (String t : tokens) {
            switch (t) {
                case "+" -> st.push(st.pop() + st.pop());
                case "*" -> st.push(st.pop() * st.pop());
                case "-" -> { int b = st.pop(), a = st.pop(); st.push(a - b); }
                case "/" -> { int b = st.pop(), a = st.pop(); st.push(a / b); }
                default -> st.push(Integer.parseInt(t));
            }
        }
        return st.pop();
    }
}

// Template 4: O(1) getMin by pairing each value with the min at that depth.
class MinStack {
    private final Deque<int[]> st = new ArrayDeque<>();
    void push(int x) { st.push(new int[]{x, st.isEmpty() ? x : Math.min(x, st.peek()[1])}); }
    void pop() { st.pop(); }
    int top() { return st.peek()[0]; }
    int getMin() { return st.peek()[1]; }
}

Complexity

Each element is pushed once and popped at most once, so the total work stays linear even with an inner while loop.

Variations

• Pair matching - push openers (or expected closers): Valid Parentheses.
• Neighbour cancellation - top equals current, so both disappear: Remove All Adjacent Duplicates In String, Removing Stars From a String.
• Expression evaluation - operands on the stack: Evaluate Reverse Polish Notation, Basic Calculator II.
• Index stack with a base - lengths from index differences: Longest Valid Parentheses.
• Augmented stack - store extra info per level: Min Stack.
• Greedy stack with "seen" set - pop larger letters that reappear later: Remove Duplicate Letters.
• State save at nesting - push (count, string) or (result, sign) at each [ or (: Decode String, Basic Calculator.

Common mistakes

• Forgetting the final isEmpty() check - "((" never fails during the scan but is still invalid.
• Using java.util.Stack (synchronised, extends Vector) when ArrayDeque is faster and idiomatic; remember ArrayDeque rejects null.
• Popping operands in the wrong order for - and /: the first pop is the right operand.
• Comparing boxed Integer objects with == from two stacks - values above 127 are different objects; use .equals or unbox.
• In calculators, forgetting to apply the last pending number when the string ends.

All practice problems

8 problems on this site use this pattern, easiest first. Solve them in order and say the instinct out loud before you code.