Stacks

Problem

Many inputs have nested structure: parentheses inside brackets, a sub-expression inside an expression, a path with .. steps that undo earlier ones. The most recently opened thing is always the first one to close. A stack stores exactly the set of things that are open right now, innermost on top, so each new item only needs to look at the top. Without a stack you end up scanning back and forth for the matching partner, which costs O(n²).

Intuition

A stack of plates in a cafeteria: you can only touch the top one. Parsing a nested structure has the same shape. Each opening symbol is a promise ("I still owe a closing partner"). Each closing symbol must settle the most recent unsettled promise, which is the top of the stack. If it names a different promise, the input is broken. If the input ends and promises remain, it is broken too.

The second idea is that a stack entry can hold more than one value. A min stack stores (value, minimum so far). Because the minimum at depth d depends only on entries 1 to d, popping the top automatically reveals the right minimum for the entries left behind.

The stack after each character. Amber is the item just pushed; a column that shrinks is a pop. The last column is empty: everything that opened was closed.

Mechanics

The invariant

After reading a prefix, the stack holds exactly the unresolved items of that prefix, oldest at the bottom. For brackets, that means the openers not yet closed, and the prefix is still a possible start of a valid string exactly when every closer so far matched the top at its moment. Pushing an opener keeps the invariant because the new opener is unresolved. Popping on a matching closer keeps it because that pair resolves the top. A closer that does not match the top (or arrives on an empty stack) can never be matched later, because the unresolved items beneath the top can only be reached after the top is gone. So the answer is: valid when no mismatch occurred and the stack is empty at the end.

Entries with memory

Anything computed from "the stack below me" can be stored in the entry at push time. The min stack stores the running minimum; a stack-based calculator stores the running result and sign when it enters a parenthesis; a decoder stores the string built so far and the repeat count. When the scope closes, the pop returns the stored outer state and you combine it with the inner result.

Postfix evaluation

In reverse Polish notation operators come after their operands, so there is no precedence to parse. Push numbers. On an operator, pop the right operand first (it was pushed last), then the left, apply, and push the result. The order of the two pops matters for subtraction and division. A valid expression ends with exactly one value on the stack.

Each box shows value · minimum at push time. Popping the 2 and then the 7 shows the minimum falling back to 3 with no search.

Worked example

Brackets in {[()()]}:

The stack is empty at the end, so {[()()]} is valid.

For ([)] the closer ) at index 2 arrives while the top is [, so the scan stops with a mismatch: the closing round bracket skipped over an unresolved square bracket.

Postfix 8 3 2 * - 10 5 / +:

The result is 4.

Min stack after each operation:

Implementation

def is_valid(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in s:
        if ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
        else:
            stack.append(ch)
    return not stack


class MinStack:
    def __init__(self):
        self.items = []                     # (value, minimum at push time)

    def push(self, x):
        low = x if not self.items else min(x, self.items[-1][1])
        self.items.append((x, low))

    def pop(self):
        return self.items.pop()[0]

    def top(self):
        return self.items[-1][0]

    def get_min(self):
        return self.items[-1][1]


def eval_rpn(tokens):
    stack = []
    for t in tokens:
        if t in {"+", "-", "*", "/"}:
            right, left = stack.pop(), stack.pop()
            if t == "+": stack.append(left + right)
            elif t == "-": stack.append(left - right)
            elif t == "*": stack.append(left * right)
            else: stack.append(int(left / right))      # truncate toward zero
        else:
            stack.append(int(t))
    return stack[-1]

Variations and edge cases

• Store indices, not values. When the answer is a distance or a length (the longest valid parentheses run), push indices; the value is always s[i] and the position is free. Seeding the stack with a sentinel index -1 removes the empty-stack special case.
• Saving state at a scope boundary. A calculator with parentheses pushes the running total and sign on ( and pops them on ); a decoder pushes the string and repeat count. The pattern is identical to the bracket check with richer entries.
• Multiplication and division without parentheses. Push signed terms and fold * and / straight into the top; the answer is the sum of the stack.
• Collisions. Asteroids moving in opposite directions resolve against the top of the stack until one side is gone: a loop of pops, not a single comparison.
• Queue from two stacks. An inbox and an outbox: refill the outbox from the inbox only when the outbox is empty. Each element moves at most twice, so every operation is amortised O(1).
• Edge cases: a closer on an empty stack, openers left over at the end, an odd length (cannot be valid), division truncating toward zero (Python's // floors), popping an empty stack in a malformed expression, and a path that tries to go above the root.

Complexity and tradeoffs

• Brute-force baseline: without a stack, a bracket check keeps deleting adjacent matching pairs until nothing changes. Each pass is O(n) and there can be n/2 passes, so O(n²). The stack makes the same cancellations in one pass, because its top is always the innermost opener still waiting for a partner.
• Time: O(n). Each element is pushed once and popped at most once, so even a loop of pops is amortised constant per element.
• Space: O(n) in the worst case (all openers). A bracket check with one bracket type needs only a counter, O(1), but with several types the stack is required.
• Python: a list with append and pop is a fast stack. Do not use pop(0) or insert(0, x) for a stack or queue.
• When it fails. If matching partners are not nested (crossing intervals), a stack is the wrong shape; if you need the next greater or smaller element, keep the stack ordered (monotonic stack); if you need the oldest item first, use a queue.

Problems

Most home problems are one of three shapes: match and cancel (parentheses, asteroids, path simplification), evaluate with saved state (calculators, decode string, postfix) or build a data structure out of stacks (min stack, queue from stacks, stack from queues). The longest valid parentheses problem also leans on dynamic programming; the stack version is the cleanest.

Easy

• 20. Valid Parentheses Blind 75 Grind 169 NeetCode 150 NeetCode 250
  Push every opener and require each closer to match the top of the stack, so the string is valid exactly when the stack ends empty.
• 225. Implement Stack using Queues NeetCode 250
  After each push rotate the queue so the newest element sits at the front, making pop and top single dequeues.
• 232. Implement Queue using Stacks Grind 169 NeetCode 250
  Push onto an inbox stack and pop from an outbox stack, refilling it only when empty, which makes every operation amortized O(1).
• 682. Baseball Game NeetCode 250
  Keep the valid scores on a stack, so undo and the previous-score operations only touch its top.

Medium

• 71. Simplify Path NeetCode 250
  Split on slashes and treat directory names as pushes and '..' as a pop, ignoring empty pieces and '.'.
• 150. Evaluate Reverse Polish Notation Grind 169 NeetCode 150 NeetCode 250
  Push numbers, and on an operator pop two operands, apply it in the right order and push the result.
• 155. Min Stack Grind 169 NeetCode 150 NeetCode 250
  Store alongside each element the minimum at the moment it was pushed, so popping restores the earlier minimum for free.
• 227. Basic Calculator II Grind 169
  Push signed terms, multiplying or dividing straight into the top of the stack, then sum it, so precedence needs no parentheses.
• 394. Decode String Grind 169 NeetCode 250
  On an opening bracket push the current string and repeat count, and on a closing bracket pop them and append the repeated inner string.
• 735. Asteroid Collision Grind 169 NeetCode 250
  Keep surviving asteroids on a stack and let each left-moving one collide with right-moving ones on top until one side is destroyed.

Hard

• 32. Longest Valid Parentheses Grind 169
  Keep a stack of indices with the index just before the current valid run at the bottom, so each match measures its length from there.
• 224. Basic Calculator Grind 169
  Track a running result and sign, and on an opening parenthesis push both so the inner expression starts fresh.

Also uses this pattern

These problems have a different home page, but this idea is part of their solution.

• 94. Binary Tree Inorder Traversal Easy
• 144. Binary Tree Preorder Traversal Easy
• 145. Binary Tree Postorder Traversal Easy
• 844. Backspace String Compare Easy
• 22. Generate Parentheses Medium
• 649. Dota2 Senate Medium
• 895. Maximum Frequency Stack Hard

Connections

The call stack of the recursion page is this structure managed by the language; any recursive algorithm can be rewritten with an explicit stack, which is how iterative tree traversals work. The next page keeps the stack sorted to answer next-greater queries in one pass.

Check yourself

References

• Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms: the section on stacks and queues in the elementary data structures chapter.
• Sedgewick and Wayne, Algorithms, section 1.3: stacks and queues, with Dijkstra's two-stack algorithm for evaluating expressions, which is the origin of the calculator problems.
• Skiena, The Algorithm Design Manual: the section on stacks and queues.
• Knuth, The Art of Computer Programming, volume 1, section 2.2.1 on stacks, queues and deques.
• The NeetCode roadmap and the Blind 75, Grind 169, NeetCode 150 and NeetCode 250 lists, used as the index of topics and problems.