What is a Stack?
A stack stores items in last-in, first-out order. The newest item is the first one removed.
You need arrays and the operations push, peek, and pop. The short version is: use a stack when the latest unfinished piece must be completed first.
The Core Idea: Match the Latest Opening
In Valid: {[()]}, every closing bracket must match the most recent opening bracket.
When ) appears, ( is on top.
Then ] matches [, and } matches {.
Why can we ignore older opening brackets until the top is closed? Nested structure requires inner work to finish before outer work can finish.
It is like stacking plates. Taking a plate from the middle would disturb everything above it, so the top plate comes off first.
How Bracket Matching Uses the Stack
The Rule You Keep True
After reading any prefix of the expression, the stack contains exactly the opening brackets that have not yet been matched, in their nesting order. The top is the only opening bracket the next closing bracket may legally close.
The stored item changes by problem:
- Valid Parentheses stores unmatched opening brackets.
- Min Stack stores enough minimum information to restore the previous minimum after a pop.
- Reverse Polish Notation stores completed operand values.
- Monotonic stack problems store unresolved indexes in a chosen order.
Evaluate Reverse Polish Notation is the one that usually trips us up.
For a b -, the first popped value is b and the second is a.
Using the pop order directly computes b - a, which is wrong.
Picking the Right Shape
From Rule to Code
- Decide what one stack entry represents.
- Push when new unfinished work begins.
- Peek before an operation that depends on the current top.
- Pop only when that top item has been completed or consumed.
- Check the final stack state when unfinished entries would make the answer invalid.
Each item is pushed and popped at most once, so these scans take O(n) time and O(n) stack space.
When to use it
- •The most recently added unfinished item must be handled first.
- •Nested structures must close in the reverse order they opened.
- •An expression or sequence must be evaluated from recent partial results.
- •You need to undo, backtrack, or track a previous state in reverse order.
How to identify it
- •The prompt contains nested brackets, expressions, undo operations, or recursive structure.
- •A closing item must match the latest unmatched opening item.
- •Only the top unfinished item is needed at each step.
- •Last in, first out matches the required processing order.
Key insights
- →A stack exposes only its most recently pushed item.
- →Valid Parentheses pushes opening brackets and matches each closing bracket with the top.
- →An empty stack at the end means no opening bracket remains unmatched.
- →Stacks can hold values, indexes, operators, or complete state snapshots.
- →An auxiliary stack can maintain extra information such as the current minimum.
Common mistakes
- 01Popping before checking whether the stack is empty.
- 02Matching a closing bracket against any earlier opening bracket instead of the top one.
- 03Returning true before confirming the stack is empty after the scan.
- 04Reversing operand order when evaluating subtraction or division in postfix notation.
- 05Updating a main stack without updating its auxiliary minimum state.