Stacks: Remembering What Isn't Resolved Yet

A stack is the data structure for “I can’t deal with this yet — hold it until I can.” Every time you read something whose meaning depends on what comes later, you push it and move on; when the later thing arrives, the most recently deferred item is exactly the one it resolves. That last-in-first-out order isn’t a quirk to memorize, it’s the shape of nested and pending things: the inner parenthesis closes before the outer one, the last operand pushed is the first an operator needs.

Valid Parentheses is that idea with nothing added — push every opening bracket, and when a closing bracket arrives, the top of the stack had better be its match:

Deque<Character> stack = new ArrayDeque<>();
for (char c : s.toCharArray()) {
    if (c == '(' || c == '[' || c == '{') {
        stack.push(c);                              // defer: resolved by a later close
    } else if (stack.isEmpty() || !matches(stack.pop(), c)) {
        return false;                               // nothing to match, or wrong match
    }
}
return stack.isEmpty();                              // everything got resolved

That covers one whole family of these problems. The other family — the one most stack interview questions are really built around — is the monotonic stack.

The stack as a pile of deferred work

When a problem is about nesting or “resolve in reverse order,” a stack falls out naturally:

• Valid Parentheses defers each opener until its closer.
• Evaluate Reverse Polish Notation pushes operands and, on hitting an operator, pops the two it applies to — RPN is designed so the stack always holds exactly the pending numbers.
• Min Stack keeps a second stack of running minimums alongside the main one, so “what’s the smallest right now” is always the top of the helper.
• Generate Parentheses is worth a mention as a near-miss — NeetCode now files it under backtracking, since it leans on the call stack to remember partial strings rather than an explicit Stack of data.

The monotonic stack: answers found on the way out

The clever pattern keeps the stack monotonic — increasing or decreasing, strictly or allowing equal values depending on the problem — and enforces that order on every push. The payoff is subtle: when an incoming element violates the order, the elements you pop to restore it have just met the thing they were waiting for. That is exactly “next greater element” or “next smaller element,” computed for every position in a single pass.

Daily Temperatures makes it concrete. You want, for each day, how many days until it gets warmer. Keep a stack of indices whose temperatures are decreasing; each new day pops every colder day still waiting, because it is their warmer day:

int[] answer = new int[temps.length];
Deque<Integer> stack = new ArrayDeque<>();   // indices of days still waiting; coldest on top
for (int i = 0; i < temps.length; i++) {
    while (!stack.isEmpty() && temps[i] > temps[stack.peek()]) {
        int day = stack.pop();
        answer[day] = i - day;               // today is that day's answer
    }
    stack.push(i);
}

Each index is pushed and popped at most once, so the whole thing is $O(n)$ even though it looks doubly nested. Largest Rectangle in Histogram is the same machine pointed at a harder question — a bar popped by a shorter one has found the right edge of the widest rectangle it can anchor — and Car Fleet uses a monotonic stack of arrival times to collapse cars that catch up to each other into one fleet.

The one decision this pattern forces is direction. A stack kept decreasing pops when a larger value arrives, so its pops answer “next greater”; kept increasing, it pops on a smaller value and answers “next smaller.” Daily Temperatures wants the next warmer day, so the stack decreases and the coldest waiting day sits on top; Largest Rectangle wants the first shorter bar on either side, so the stack increases and the tallest bar sits on top — a shorter incoming bar pops it, and that pop is the moment the popped bar learns its right boundary. Write the question down first — “next greater” or “next smaller” — and the comparison in the while loop follows from it rather than from guesswork.

Where you’ve already used one

RPN is exactly how a stack-based virtual machine runs. The JVM evaluates a + b by pushing a and b onto an operand stack and letting iadd pop them — Evaluate Reverse Polish Notation with a bytecode accent. The same structure is the undo history in an editor and the call stack that unwinds when an exception is thrown, the very stack a recursive tree traversal rides on. Having read more than a few stack traces over the years, I find the operand-stack framing makes RPN feel less like a puzzle and more like something I’d already been debugging in thread dumps.

Two stacks, one habit

Sort any stack problem into the two piles and the rest is mechanical. If the problem is about matching, nesting, or resolving in reverse, you want a plain stack of the pending things. If it asks “for each element, the next one that’s bigger or smaller,” reach for a monotonic stack and let the pops hand you the answers — the doubly-nested look is a lie the $O(n)$ bound sees through.

References

• NeetCode 150 — Stack — the six problems, easy to hard.