Stack

A stack does one thing: it hands back whatever you put in most recently. That single property makes it the right structure for two very different families of problem — anything with nesting, and anything that asks about the nearest larger or smaller neighbour.

Why it works#

Last in, first out matches the shape of nested structure. When you open a bracket, start a subexpression, or descend into something, the thing you opened most recently is always the thing you have to close first. A stack enforces that ordering for free, which is why bracket matching is four lines rather than a parser.

The invariant worth naming is this: everything on the stack is unfinished business, in the order it will be resolved. The top is the item that will be settled next. Whenever you can phrase a problem that way, a stack is the structure.

Matching and nesting#

Push when something opens, pop when something closes, and check that the pair agrees.

stack = empty

for ch in input:
    if ch opens:
        push ch
    else:
        if stack is empty:          // closing with nothing open
            return false
        if not matches(pop(), ch):  // closed the wrong thing
            return false

return stack is empty               // anything left open is a failure

The three failure modes are the whole problem, and each is one line: closing when nothing is open, closing the wrong kind of thing, and reaching the end with something still open. Miss the last check and "(((" passes.

Expression evaluation is the same idea with values instead of brackets. In reverse Polish notation the operands are already in order, so you push numbers, and each operator pops the two it applies to and pushes the result. Because the notation encodes the nesting, no precedence rules are needed at all — the stack is the parse.

Monotonic stacks#

This is the technique that makes several Hard problems tractable, and it is worth the time it takes to get comfortable.

Keep the stack sorted — say, increasing from bottom to top. Before pushing a new element, pop everything that breaks that order. The elements you pop are exactly the ones for which the new element is the answer to “what is the next greater value?”

Step through it and watch what the stack means. Every index on it is still waiting for a bigger value to show up. When one arrives, it settles all the smaller ones underneath it at once, and they leave. Indices still on the stack at the end were never beaten, so their answer is “none”.

stack = empty            // holds indices, values increasing bottom to top
answer = all none

for i = 0 .. n - 1:
    while stack not empty and nums[top] < nums[i]:
        j = pop()
        answer[j] = nums[i]      // nums[i] is the first greater value after j

    push i

// whatever is left never found a greater value

Like a sliding window, the inner while looks quadratic and is not: every index is pushed once and popped at most once, so the whole scan is O(n) amortised. Flip the comparison to get the next smaller value, and walk the array backwards to get the previous one instead of the next.

This is the engine behind Largest Rectangle in Histogram, where each bar’s rectangle is bounded by the first shorter bar on either side — precisely the two questions a monotonic stack answers.

Designing with stacks#

A third family asks you to build something whose behaviour depends on stack ordering.

Min Stack — report the smallest element in O(1). The trick is that you cannot recompute it on demand, so you store it alongside: each entry carries the minimum of everything at or below it. Popping restores the previous minimum automatically, because it was never overwritten.

A queue from two stacks — one stack takes pushes, the other serves pops. When the out stack empties, tip the in stack into it, which reverses the order and turns last-in-first-out into first-in-first-out. Each element is moved at most once, so despite the occasional expensive transfer the cost per operation is O(1) amortised.

Both share a lesson: when an operation needs to be fast, precompute what it needs at push time rather than searching for it at read time.

Recognising it#

Reach for a stack when:

• The input has nesting — brackets, tags, expressions, or anything that opens and closes.
• You need the nearest greater or smaller element, on either side. That is a monotonic stack, essentially always.
• The problem is about undo, backtracking one step, or the most recent thing that satisfies some condition.
• You are asked to design a structure with an O(1) operation that looks like it needs a scan — the answer is usually to carry the extra information on each entry.

Summary#

A stack holds unfinished business in the order it will be resolved. For nesting problems that ordering is the answer directly. For monotonic problems the ordering is a filter: each element clears out everything it beats, so every item is touched twice at most and questions that look quadratic turn out to be linear.