Stacks

Start here: what this lesson is for

A stack is the smallest useful data structure in this course, and it is the one you have already been using without being told. Every recursive call in chapter 3 pushed a frame onto one, and every return popped one off.

The idea takes a sentence: you may only add and remove at one end. What is worth your time is the consequence - that removing power from a container is what makes it useful, because code written against a stack can only express the one behaviour the problem actually needs.

By the end you will recognise stack problems by their phrasing, know why deep recursion crashes, and be able to convert any recursion into a loop when it does.

A container with the rules turned up

A stack is not a new way to store things. It's an array or a linked list with a rule bolted on: you may only add and remove at one end. Last in, first out.

Removing power sounds like a downside. It's the opposite. Because there is only one place anything can happen, both operations are O(1) with no shifting, no searching, and no decisions - and code that uses a stack can only express the one behaviour the problem actually needs.

You have been watching a stack for three chapters. Every recursive call in chapter 3 pushed a frame; every return popped one. That's why deep recursion throws StackOverflowError - it is a real stack, with a real limit.

Matching brackets: the pattern in miniature

Check whether {[()]} is balanced. Counting won't do it - {[}] has the right counts and is nonsense. What matters is that the most recent unclosed bracket is the one that must close next.

'Most recent unfinished thing' is a stack, exactly. Push every opener. On a closer, pop and check the pair matches. Two extra rules cover the edges: popping an empty stack means a closer with nothing to close, and a non-empty stack at the end means something never closed.

This is the shape of every parser, every JSON reader, and the compiler that reads your own code.

boolean balanced(String s) {
    Deque<Character> stack = new ArrayDeque<>();   // Java's recommended stack
    Map<Character, Character> pairs =
        Map.of(')', '(', ']', '[', '}', '{');

    for (char c : s.toCharArray()) {
        if (pairs.containsValue(c)) {
            stack.push(c);                          // an opener: remember it
        } else if (pairs.containsKey(c)) {
            // nothing open, or the wrong thing open
            if (stack.isEmpty() || stack.pop() != pairs.get(c)) return false;
        }
    }
    return stack.isEmpty();                         // anything left is unclosed
}

"{[()]}"    push { [ (   pop ( ] ) match   -> true
"{[}]"      push { [       pop [ vs { mismatch  -> false
"(("        push ( (       end, stack not empty -> false
"))"        pop on empty                        -> false

Undo, and turning recursion into a loop

Undo is the same shape wearing different clothes. Every action pushes a description of itself; Ctrl+Z pops the most recent and reverses it. A redo stack sits alongside it, receiving whatever undo pops.

The deeper use is replacing recursion. Any recursive algorithm can be rewritten as a loop with an explicit stack, because that's precisely what the call stack was doing for you. You push the work you still owe, and loop until you owe nothing.

It's worth knowing for one practical reason: an explicit stack lives on the heap, which is large, while the call stack is small and fixed. A tree walk that overflows at a depth of ten thousand recursively will run happily with an explicit stack.

// recursive: elegant, but bounded by the call stack
void walk(Node n) {
    if (n == null) return;
    visit(n);
    walk(n.left);
    walk(n.right);
}

// iterative: identical order, bounded only by the heap
void walkIterative(Node root) {
    Deque<Node> todo = new ArrayDeque<>();
    if (root != null) todo.push(root);
    while (!todo.isEmpty()) {
        Node n = todo.pop();
        visit(n);
        if (n.right != null) todo.push(n.right);  // right FIRST...
        if (n.left  != null) todo.push(n.left);   // ...so left pops first
    }
}

depth 10,000 tree
  walk(root)           StackOverflowError
  walkIterative(root)  completes, 10,000 nodes visited

The monotonic stack: next greater element

One stack pattern is worth meeting now because it turns an obvious O(n squared) solution into O(n), and it appears constantly once you can recognise it.

The question: for each item, what is the next larger value to its right? The obvious approach scans forward from every position, which is quadratic.

The trick is to keep a stack of items still waiting for their answer, kept in decreasing order. When a new value arrives, anything on the stack smaller than it has just found its answer - pop those and record it. Then push the newcomer.

Each item is pushed once and popped once, so despite the inner while loop the total work is O(n). That is the same argument as the sliding-window deque later in this chapter: a nested loop is not automatically quadratic if each element can only be processed a bounded number of times.

int[] nextGreater(int[] a) {
    int[] out = new int[a.length];
    Arrays.fill(out, -1);
    Deque<Integer> waiting = new ArrayDeque<>();   // INDICES, decreasing values

    for (int i = 0; i < a.length; i++) {
        // everything smaller than a[i] has just found its answer
        while (!waiting.isEmpty() && a[waiting.peek()] < a[i]) {
            out[waiting.pop()] = a[i];
        }
        waiting.push(i);
    }
    return out;                                    // anything left never found one
}

a   = [2, 1, 2, 4, 3]
out = [4, 2, 4, -1, -1]

i=0  push 0                  stack [2]
i=1  1 < 2, push 1           stack [2,1]
i=2  2 > 1 -> out[1]=2       stack [2,2]
i=3  4 pops both -> out=4    stack [4]
i=4  3 < 4, push             stack [4,3]

5 pushes, 5 pops - O(n), not O(n squared)

Recap: a container with one legal end

A stack is defined by what it refuses to let you do, and that restriction is the whole value.

Push, pop and peek are all O(1) with no shifting and no searching, because there is only one place anything can happen.

Reach for it whenever the phrase 'the most recent unfinished thing' fits: matching brackets, parsing, undo and redo, and the call stack itself.

And remember the escape hatch. An explicit stack lives on the heap, which is large, while the call stack is small and fixed - so a tree walk that overflows at depth 10,000 recursively will run happily with your own stack.

The next lesson flips the rule to the other end and gets a queue - and that single change turns depth-first exploration into breadth-first, which chapter 10 depends on completely.