Stacks
A stack is a sequence you can touch at only one end. You push an item on top, you pop the top item off, you may peek at the top without removing it, and you can ask whether it is empty. Nothing else. That poverty of operations is the point: because the stack forbids access to anything below the top, it can promise that the item you get back is always the most recently added one still present — last in, first out (LIFO).
This page goes from the ADT to the machinery that runs your programs. You will prove why a stack recognises balanced brackets, build a stack that answers getMin in constant time, turn infix arithmetic into something a machine can evaluate with Dijkstra's shunting-yard algorithm, convert recursion into explicit iteration, and see why the JVM, WebAssembly, and every native call frame on your laptop are stacks. The next two lessons, Queues, Deques & Circular Buffers and Monotonic Stack & Monotonic Deque, build directly on it.
Why this exists
The stack is older than the discipline that named it. In his 1945 report on the ACE, Alan Turing described "bury" and "unbury" operations for saving and restoring the return address of a subroutine, which is a stack in everything but name. Friedrich Bauer and Klaus Samelson independently formulated the Kellerprinzip ("cellar principle") in 1955 and filed a patent on it in 1957, using it to translate and evaluate arithmetic expressions in their early ALGOL work. Dijkstra published the shunting-yard algorithm in 1961 while writing one of the first ALGOL 60 compilers. The structure arrived with compilers, and compilers remain its largest user.
Why does something so restricted keep showing up? Because an enormous number of real processes are properly nested: a function call that must finish before its caller resumes, a parenthesis that must close before the one around it, an HTML tag that must close before its parent, an editor action that must be undone before the one taken before it, a transaction savepoint that must be released before the outer one. Nesting is LIFO. Whenever the thing you need to come back to is always the most recent unfinished thing, a stack is not one data structure among many; it is the only one that models the situation exactly, and anything more general (a list with arbitrary access) merely invites bugs.
The stack also has a second life as a conversion tool. Every recursive algorithm uses the machine's call stack implicitly. When recursion depth threatens to overflow it, or when a language makes recursion slow, you move that implicit stack into an explicit one you control. Iterative depth-first search, iterative tree traversals, iterative quicksort, and the mark phase of garbage collectors are all recursion with the stack made visible.
Finally, a disciplined variant of the stack, the monotonic stack, turns a whole family of "nearest greater / nearest smaller" problems from quadratic to linear. That variant has its own lesson; here we build the foundation it stands on.
Pattern triggers
| If the problem says or has… | Think of… |
|---|---|
| "balanced", "valid parentheses", "matching tags", nested brackets of several kinds | Stack of unmatched openers |
| "evaluate this expression", infix / postfix / prefix, "basic calculator" | Operator stack + operand stack (two-stack evaluation) or infix → RPN then evaluate |
"decode", "expand", nested repetitions like 3[a2[c]] | Stack of (count, partial string) frames |
"simplify a path", ".. goes up one level" | Stack of path components |
| "remove adjacent duplicates", "collapse pairs", "collisions" where only the most recent survivor matters | Stack where the top interacts with the new element |
| "undo / redo", "back / forward", "most recent" | Two stacks |
| "most recent unfinished", "nested calls", "exclusive time of functions" | Stack of frames with timestamps |
| "next greater / smaller element", "span", "largest rectangle", "trapping water" | Monotonic stack — see Monotonic Stack & Monotonic Deque |
| "implement a queue using stacks" / "stack using queues" | Two-stack queue with amortized analysis |
| "iterative DFS", "without recursion", recursion depth 10⁵+ | Explicit stack replacing the call stack |
| "min / max of the stack in O(1)" | Auxiliary min stack or the store-difference trick |
The common thread: the problem has a notion of "the most recently opened thing that is not yet closed". If you find yourself wanting to look at the second most recent thing without first dealing with the most recent one, a stack is probably the wrong tool (or you need two of them).
Intuition & first principles
The ADT
An abstract data type (ADT) is a contract: a set of operations and the promises those operations make, with no commitment to a representation. The stack ADT has four core operations:
| Operation | Promise |
|---|---|
push(x) | Afterwards peek() returns x and isEmpty() is false |
pop() | Removes and returns the element the most recent unmatched push added; error if empty |
peek() (also top) | Returns what pop() would return without removing it; error if empty |
isEmpty() | True iff every push has been matched by a pop |
Some libraries add size(). Everything else, such as searching the stack or indexing into it, is outside the ADT; if you need it you are using an array that happens to have a push method, which is fine, but be honest about it.
The algebraic specification is short and worth internalising, because every proof about stacks reduces to it: for any stack s and value x, pop(push(s, x)) = s and peek(push(s, x)) = x. A stack is the free structure generated by these two laws.
Two ways to build it
Array-backed. Keep a dynamic array and an integer top (the count). push writes at index top and increments; pop decrements and reads. When the array is full, allocate a larger one (typically 1.5× to 2×) and copy. Every operation is except the occasional resize, which costs but happens so rarely that the amortized cost of push is ; the argument is the standard doubling argument from Complexity Analysis. Elements are contiguous, so iterating or copying the stack is cache-friendly.
Linked. Each node holds a value and a pointer to the node below it; the stack is a pointer to the top node. push allocates a node and points it at the old top; pop reads the top and advances. Every operation is worst-case with no resizing, at the cost of one allocation per push, pointer-chasing on every access, and roughly 2–3× the memory per element (value plus pointer plus allocator overhead). The linked form is what you get for free from a singly linked list used only at its head.
| Array-backed | Linked | |
|---|---|---|
push | amortized, worst case on resize | worst case |
pop / peek / isEmpty | ||
| Memory per element | value only (plus slack ≤ growth factor) | value + pointer + allocator header |
| Locality | excellent | poor |
| Persistent / shareable versions | no | yes (share tails) |
In practice the array-backed stack wins on every workload that is not real-time, because the allocation per push in the linked version costs more than the amortized copying. The linked version matters when you need a persistent stack (two stacks sharing a common tail), which arises in functional languages and in some undo systems.
The call stack: the original stack
When your program calls a function, the machine has to remember where to come back to, what the caller's local variables were, and where the callee's locals live. Because the callee must return before the caller can continue, these records are LIFO, and so every mainstream runtime stores them on a stack: the call stack. Each record is a frame (or activation record). On x86-64 the call instruction pushes the return address onto the stack and jumps; the callee typically saves the caller's frame pointer, reserves space for its locals by moving the stack pointer, and ret pops the return address back into the instruction pointer. The stack grows toward lower addresses on nearly every mainstream ABI; the "top" of the stack is the lowest address in use.
This is why recursion works at all, and why it has a limit. Each recursive call pushes a frame; frames are typically tens to a few hundred bytes; the default main-thread stack is 8 MB on most Linux distributions and 1 MB on Windows, and language runtimes impose their own caps (CPython's default recursion limit is 1000 frames; the JVM's default thread stack is around 1 MB on most 64-bit platforms, though the exact figure is platform-dependent). Exceed the cap and you get a stack overflow, which is just a stack that cannot push. The cure is in Recursion & Mathematical Induction and in the "recursion → explicit stack" section below: move the frames into a heap-allocated stack you control.
Per-language stack idioms
Every language in this course has a built-in that does the job well, and at least one trap.
| Language | Use | Avoid | Notes |
|---|---|---|---|
| Python | list with append / pop / [-1] | collections.deque is fine but unnecessary for a pure stack; list.insert(0, x) / pop(0) is | append is amortized ; CPython over-allocates by roughly an eighth plus a small constant |
| Java | ArrayDeque<T> with push / pop / peek | java.util.Stack | Stack extends Vector: every method is synchronized, it allows indexed access, and its iterator runs bottom-to-top, which surprises people. The Stack Javadoc itself tells you to prefer Deque |
| C++ | std::stack<T> (adapter over std::deque by default), or std::vector<T> with push_back / pop_back / back | — | std::stack<T, std::vector<T>> is often faster for small element types; pop() returns void, so read top() first |
| JavaScript / TypeScript | Array with push / pop / arr[arr.length - 1] | shift / unshift for stack use (they are the queue end) | arr.at(-1) is a readable peek |
Two specifics worth knowing. Java's ArrayDeque.push and pop operate on the head of the deque, so iterating an ArrayDeque used as a stack yields top-first, the opposite of Stack's iteration order; code that migrates from Stack to ArrayDeque and iterates will silently reverse. And ArrayDeque rejects null elements, so a stack of nullable values needs an explicit sentinel. See Your Language's Data Structures for the surrounding library details.
Mechanics
The core operations
flowchart LR
S0["[ ] empty"] -->|"push 7"| S1["[7]"]
S1 -->|"push 3"| S2["[7, 3]"]
S2 -->|"peek -> 3"| S2
S2 -->|"pop -> 3"| S3["[7]"]
S3 -->|"pop -> 7"| S4["[ ] empty"]
S4 -->|"pop -> error"| S4
The only state is the sequence itself; top is wherever the sequence ends. A pop on an empty stack is a contract violation and should fail loudly (Python raises IndexError, Java ArrayDeque.pop throws NoSuchElementException, C++ std::stack::pop on empty is undefined behaviour, JavaScript returns undefined silently, which is the most dangerous of the four).
Matching brackets
The first non-trivial algorithm. Scan left to right. On an opener, push it. On a closer, the stack must be non-empty and its top must be the matching opener; pop it. At the end the stack must be empty.
def is_balanced(s: str) -> bool:
pairs = {")": "(", "]": "[", "}": "{"}
stack: list[str] = []
for ch in s:
if ch in "([{":
stack.append(ch)
elif ch in pairs:
if not stack or stack[-1] != pairs[ch]:
return False
stack.pop()
return not stack
assert is_balanced("([]{()})")
assert not is_balanced("([)]")
assert not is_balanced("((")
assert not is_balanced("))")
assert is_balanced("")
Why not just count? For a single bracket type counting works: increment on (, decrement on ), fail if the count goes negative, succeed if it ends at zero. With two or more types counting fails: ([)] has one of each opener and closer and never goes negative, yet is invalid, because the order of unmatched openers matters. The stack records exactly that order and nothing more. The proof is in the Correctness section.
Min-stack: getMin in O(1)
Problem: support push, pop, top, and getMin, all in . The trick is to maintain, alongside the main stack, a second stack mins where mins[i] is the minimum of main[0..i]. On push(x), push min(x, mins.top) onto mins (or x if empty). On pop, pop both. getMin is mins.top. Here is the sequence push 5, push 3, push 7, push 3, getMin, pop, getMin, pop, getMin, pop, getMin, computed by script:
| Operation | Returns | Main stack | Min stack |
|---|---|---|---|
| push(5) | – | [5] | [5] |
| push(3) | – | [5, 3] | [5, 3] |
| push(7) | – | [5, 3, 7] | [5, 3, 3] |
| push(3) | – | [5, 3, 7, 3] | [5, 3, 3, 3] |
| getMin() | 3 | [5, 3, 7, 3] | [5, 3, 3, 3] |
| pop() | 3 | [5, 3, 7] | [5, 3, 3] |
| getMin() | 3 | [5, 3, 7] | [5, 3, 3] |
| pop() | 7 | [5, 3] | [5, 3] |
| getMin() | 3 | [5, 3] | [5, 3] |
| pop() | 3 | [5] | [5] |
| getMin() | 5 | [5] | [5] |
Notice the second push(3): the min stack must record 3 again, not skip it. A tempting "optimisation" that only pushes onto mins when the new value is strictly smaller breaks here, because after popping the second 3 the first 3 is still present and still the minimum. If you want the lazy version, push when x <= mins.top (non-strict) and pop mins only when the popped value equals mins.top.
The store-difference trick (O(1) extra space). Keep a single variable mn and store on the stack not x but x - mn (as computed before mn is updated). Then:
- On
push(x): if the stack is empty, push0and setmn = x. Otherwise pushx - mn; ifx < mn, setmn = x. - On
pop(): letdbe the popped value. Ifd < 0, the popped element was the minimum: its value is the currentmn, and the previous minimum wasmn - d, so restoremn = mn - d. Otherwise the value isd + mn. getMin()ismn;top()ismnif the stored top is negative, elsetop + mn.
Same operation sequence:
| Operation | Returns | Stored differences | mn |
|---|---|---|---|
| push(5) | – | [0] | 5 |
| push(3) | – | [0, -2] | 3 |
| push(7) | – | [0, -2, 4] | 3 |
| push(3) | – | [0, -2, 4, 0] | 3 |
| getMin() | 3 | [0, -2, 4, 0] | 3 |
| pop() | 3 | [0, -2, 4] | 3 |
| getMin() | 3 | [0, -2, 4] | 3 |
| pop() | 7 | [0, -2] | 3 |
| getMin() | 3 | [0, -2] | 3 |
| pop() | 3 | [0] | 5 |
| getMin() | 5 | [0] | 5 |
The difference x - mn can be as large as twice the magnitude of the input range: with 32-bit inputs it needs 64-bit storage, and with 64-bit inputs it can overflow. Use the auxiliary-stack version unless the memory saving is actually measured to matter, and if you use this one, store long / int64_t / BigInt.
Expression evaluation
Humans write infix (3 + 4 * 2), where operator precedence and parentheses decide the order. Machines prefer postfix, also called Reverse Polish Notation (RPN) (3 4 2 * +), where every operator applies to the operands immediately before it and no precedence or parentheses are needed. Jan Łukasiewicz introduced prefix "Polish notation" in 1924 for logic; the reversed form was proposed in the 1950s and became famous through Hewlett-Packard calculators, starting with the 9100A in 1968 and the HP-35 in 1972.
Evaluating RPN is a single stack: scan left to right, push numbers, and on an operator pop two operands (the second popped is the left operand), apply, push the result. One number remains at the end.
Shunting-yard: infix → postfix. Dijkstra's algorithm uses an output queue and an operator stack. Operators wait on the stack until something of lower precedence (or a closing parenthesis, or the end of input) forces them out. The name comes from railway shunting yards where cars are shuffled between tracks.
The rules, for each token:
- Number → append to output.
- Operator
o→ while the stack top is an operatort(not() with higher precedence thano, or equal precedence andois left-associative, poptto output. Then pusho. (→ push.)→ pop operators to output until(is on top; pop and discard the(. (If the stack empties first, the parentheses are mismatched.)- End of input → pop every remaining operator to output. A
(remaining here is a mismatch.
The precedence/associativity table used below:
| Operator | Precedence | Associativity |
|---|---|---|
+ - | 1 | left |
* / | 2 | left |
^ | 3 | right |
unary - | 4 | right |
flowchart TD
T["next token"] --> Q{"kind?"}
Q -->|"number"| OUT["append to output queue"]
Q -->|"left paren"| PUSHP["push ( onto operator stack"]
Q -->|"right paren"| POPP["pop operators to output until (<br/>then discard the ("]
Q -->|"operator o"| W{"top is operator t with<br/>prec(t) > prec(o), or<br/>equal and o left-assoc?"}
W -->|"yes"| POPT["pop t to output"] --> W
W -->|"no"| PUSHO["push o"]
OUT --> T
PUSHP --> T
POPP --> T
PUSHO --> T
Trace: shunting-yard on 3 + 4 * 2 / ( 1 - 5 ) ^ 2. Computed by script; the stack is written bottom → top.
| Token | Action | Output queue | Operator stack |
|---|---|---|---|
| 3 | number → output | 3 | |
| + | push + | 3 | + |
| 4 | number → output | 3 4 | + |
| * | push * (prec 2 > prec 1 of +) | 3 4 | + * |
| 2 | number → output | 3 4 2 | + * |
| / | pop * (equal prec, left-assoc); push / | 3 4 2 * | + / |
| ( | push ( | 3 4 2 * | + / ( |
| 1 | number → output | 3 4 2 * 1 | + / ( |
| - | push - (top is (, nothing to pop) | 3 4 2 * 1 | + / ( - |
| 5 | number → output | 3 4 2 * 1 5 | + / ( - |
| ) | pop - to output; discard ( | 3 4 2 * 1 5 - | + / |
| ^ | push ^ (prec 3 > prec 2 of /) | 3 4 2 * 1 5 - | + / ^ |
| 2 | number → output | 3 4 2 * 1 5 - 2 | + / ^ |
| end | flush ^ | 3 4 2 * 1 5 - 2 ^ | + / |
| end | flush / | 3 4 2 * 1 5 - 2 ^ / | + |
| end | flush + | 3 4 2 * 1 5 - 2 ^ / + |
Result: 3 4 2 * 1 5 - 2 ^ / +. The / step is the one people get wrong: * and / have equal precedence and are left-associative, so the earlier * must be emitted before / is pushed, which is what makes 4 * 2 / x mean (4 * 2) / x. Had ^ been treated as left-associative, 2 ^ 3 ^ 2 would come out as (2^3)^2 = 64 instead of the mathematically standard 2^(3^2) = 512.
Trace: evaluating the RPN 3 4 2 * 1 5 - 2 ^ / + with integer arithmetic (division truncates toward zero):
| Token | Action | Stack |
|---|---|---|
| 3 | push 3 | [3] |
| 4 | push 4 | [3, 4] |
| 2 | push 2 | [3, 4, 2] |
| * | pop 4, 2; push 4 * 2 = 8 | [3, 8] |
| 1 | push 1 | [3, 8, 1] |
| 5 | push 5 | [3, 8, 1, 5] |
| - | pop 1, 5; push 1 - 5 = -4 | [3, 8, -4] |
| 2 | push 2 | [3, 8, -4, 2] |
| ^ | pop -4, 2; push (-4) ^ 2 = 16 | [3, 8, 16] |
| / | pop 8, 16; push 8 / 16 = 0 | [3, 0] |
| + | pop 3, 0; push 3 + 0 = 3 | [3] |
In real arithmetic the answer is ; with integer truncation it is 3. The difference is the reason the implementation section insists on one explicit division semantics across languages.
Dijkstra's two-stack algorithm: evaluating infix directly. You do not have to produce RPN as an intermediate. Run shunting-yard, but instead of appending to an output queue, maintain an operand stack: when a number arrives, push it; whenever shunting-yard would have emitted an operator to output, instead pop its operands from the operand stack, apply it, and push the result. This is the algorithm Sedgewick and Wayne present in Algorithms, 4th ed., §1.3 as "Dijkstra's two-stack algorithm for expression evaluation". It evaluates in one pass with two stacks and is what the canonical implementation below does.
Unary minus. -3, 2 * -3, -(1 + 2) are all legal and a naïve tokenizer treats every - as binary. The fix is contextual: a - is unary when it appears at the start of input, immediately after (, or immediately after another operator; otherwise it is binary. Represent the unary one as a distinct operator (say ~) with the highest precedence and right associativity, and when applying it pop one operand. Right associativity matters so that - - 3 parses as -(-3). An alternative hack, inserting a 0 operand before a unary minus so that it becomes binary, works for -3 but gives 2 ^ -3 the wrong meaning if ^ is present, so prefer the explicit operator.
Stack-based parsing problems
A family of interview problems are "parsers" in disguise: a single pass where the top of the stack is the thing the current character interacts with.
- Decode string (
3[a2[c]]→accaccacc): on[push the current count and the partial string built so far, then reset both; on]pop them and append the inner string repeatedcounttimes to the restored partial string. The stack holds exactly the unfinished enclosing frames. - Simplify path (
/a/./b/../../c/→/c): split on/, ignore empty and., pop on..if non-empty, push anything else. The stack is the directory chain. - Remove all adjacent duplicates (
abbaca→ca): push each character; if it equals the top, pop instead. The stack is the string with every eliminable pair already removed, and new eliminations can only happen at the boundary. - Asteroid collision: asteroids move right (positive) or left (negative). Only a right-mover on the stack and a new left-mover can collide. Pop while the top is a smaller right-mover; if equal, both vanish; if the top is larger, the new one vanishes. The stack holds survivors whose fate may still change.
- Remove k digits (
1432219, k = 3 →1219): pop while the top digit is greater than the incoming one and removals remain. This is a monotonic stack: the stack is kept non-decreasing. It is a preview of Monotonic Stack & Monotonic Deque, where the technique is proved and generalised.
The pattern in every case: the new element interacts only with the most recent survivor, and after the interaction the stack is again a valid partial answer.
Recursion → explicit stack
Any recursive function can be rewritten with an explicit stack of frames. The mechanical recipe: a frame holds the arguments plus a "program counter" saying which part of the body to resume at; push the initial frame; loop while the stack is non-empty, popping a frame and executing the next piece of the body, pushing child frames for recursive calls. Most of the time you do not need the full generality.
Iterative DFS. Push the start; loop: pop u, skip if visited, mark it, push every unvisited neighbour. This visits the same set of vertices as recursive DFS, in a different order (neighbours are expanded in reverse), which is fine for reachability and connected components but not for things that depend on exact pre/post order. For a true preorder match, push neighbours in reverse order; for postorder (needed by topological sort), you need the two-phase frame trick: push (u, entered=false), and when you pop it with entered=false, push (u, entered=true) back and then its children. See Graphs.
Iterative inorder traversal. Push left spine to the stack, then pop, visit, and move to the right child and repeat. This is the standard way to produce a BST iterator with memory and amortized per next: see Trees.
def inorder(root):
out, stack, node = [], [], root
while stack or node:
while node: # descend the left spine
stack.append(node)
node = node.left
node = stack.pop()
out.append(node.val)
node = node.right
return out
class N:
def __init__(self, v, l=None, r=None): self.val, self.left, self.right = v, l, r
t = N(4, N(2, N(1), N(3)), N(6, N(5), N(7)))
assert inorder(t) == [1, 2, 3, 4, 5, 6, 7]
assert inorder(None) == []
Backtracking is recursion whose call stack is the partial solution: each frame has made one more choice. Converting backtracking to iteration means storing the choice path explicitly, which is exactly what Backtracking & Recursion does when it builds a path list alongside the recursion.
Undo/redo, browser history
Two stacks. undo holds completed actions, newest on top; redo holds actions that were undone. Performing a new action pushes onto undo and clears redo (the branch of history you undid is gone, which matches what every editor does). undo() pops from undo, reverses the action, pushes onto redo. redo() pops from redo, reapplies, pushes onto undo. Browser back/forward is identical with "action" = "navigated to URL": visiting a new page clears the forward stack. The design browser history problem is this with a bound on how many steps you can move.
A queue from two stacks
Enqueue pushes onto an inbox stack. Dequeue pops from an outbox stack; if outbox is empty, first pour every element of inbox into outbox (pop from one, push onto the other), which reverses their order so that the oldest element is now on top. A single dequeue can therefore cost , but amortized each operation is : each element is pushed onto inbox once, moved once (one pop and one push), and popped from outbox once, for at most 4 stack operations per element over its lifetime. The potential-function version, with the potential , makes every enqueue cost 3 and every dequeue cost 1 amortized; the full credit table is in Queues, Deques & Circular Buffers and the technique in Complexity Analysis.
Stacks inside compilers and runtimes
The JVM is a stack machine. Each method invocation gets a frame containing a local-variable array and an operand stack. Bytecodes such as iload, iadd, invokevirtual push and pop that operand stack; the compiler computes the maximum operand-stack depth per method (max_stack in the class file) so the JVM can allocate the frame exactly. Expression a + b * c compiles to roughly iload a; iload b; iload c; imul; iadd, which is RPN. The JIT then maps operand-stack slots onto registers, so the stack is an abstraction, not a runtime cost.
WebAssembly is also a stack machine, with a structured control flow (block, loop, if) whose validation rules guarantee the operand stack has a statically known type at every instruction. CPython's bytecode interpreter is a stack machine too (LOAD_FAST, BINARY_OP). Forth and PostScript are stack languages: the programmer manipulates the stack directly.
Register machines (Lua 5.x's VM, Android's Dalvik/ART bytecode, every real CPU) name operands explicitly instead. Stack code is more compact and trivially easy to generate from a syntax tree (post-order walk = emit RPN); register code dispatches fewer instructions because it does not need separate loads and stores. The classic measurement (Shi, Casey, Ertl & Gregg, "Virtual machine showdown: stack versus registers", VEE 2005) found register VMs execute about 47% fewer instructions at the cost of about 25% larger code.
Native call frames. On x86-64 the hardware stack pointer rsp and the call/ret/push/pop instructions implement the stack directly. A stack trace is just a walk up this chain of frames, following saved frame pointers or, with frame-pointer omission, DWARF unwind tables. When you read a stack trace you are reading the call stack, top frame first.
The ladder: brute force → better → optimal
Ladder 1: valid parentheses
Rung 0: repeated elimination, . Repeatedly delete any adjacent (), [], {} pair until nothing changes; the string is valid iff it is now empty. Each pass is and there can be passes (consider ((((...))))). Correct, but quadratic.
Rung 1: counting, but only for one bracket type. A counter that goes +1 on (, −1 on ), must never go negative and must end at 0. This is a complete characterisation for a single type (it is exactly the Dyck-language condition), and in fact it is the right tool for "minimum additions to make parentheses valid" and "score of parentheses" too. But it has no memory of which opener is pending.
Rung 2: stack, time, space. Replace the counter with a stack of pending openers. The counter is recovered as the stack's size; the stack adds the identity of each pending opener in order. This is optimal in time (every character must be read) and in space for this ADT (an adversary can make all first characters openers of mixed types; any correct algorithm must remember which, which takes bits).
| Rung | Idea | Time | Space | Handles mixed types? |
|---|---|---|---|---|
| 0 | repeatedly delete adjacent pairs | yes | ||
| 1 | counter | no | ||
| 2 | stack of openers | yes |
Ladder 2 (preview): largest rectangle in a histogram
This problem is treated fully in the monotonic lesson, but the ladder shows how a plain stack becomes a monotonic one.
Rung 0: all pairs, or . For each pair of bar indices the rectangle height is the minimum bar in between; maintaining the running minimum as grows gives .
Rung 1: per-bar expansion, . For each bar , walk left and right until a shorter bar; the best rectangle with bar as its lowest bar has width equal to that span. Correct (every maximal rectangle has some bar as its height), still quadratic because the walks repeat work.
Rung 2: monotonic stack, . Scan once, keeping a stack of bar indices with non-decreasing heights. When a shorter bar arrives, each popped bar has just discovered its right boundary (the current bar), and its left boundary is the new stack top. Appending a sentinel bar of height 0 flushes the stack. Each index is pushed and popped once. For [2, 1, 5, 6, 2, 3] the answer is 10 (bars 5 and 6, width 2); the full trace and proof are in Monotonic Stack & Monotonic Deque.
Correctness
Bracket matching
Let the input be . Define the string to be balanced by the usual grammar: the empty string is balanced; if and are balanced then so are , , , and .
Invariant. After processing , the stack (bottom to top) contains exactly the openers in that are unmatched within , in order of appearance — where an opener is matched if the prefix contains a closer that closes it under the grammar — and the algorithm has not yet returned false if and only if is a prefix of some balanced string.
Proof by induction on . The base case holds: empty stack, empty prefix.
Inductive step. Suppose the invariant holds for and consider .
- If is an opener: it is unmatched in the prefix (no later characters yet), so the correct new stack is the old stack plus on top, which is what
pushdoes. Any prefix of a balanced string followed by an opener is still such a prefix (close everything later), so not returningfalseis correct. - If is a closer: in a balanced string, a closer always matches the most recent unmatched opener (this is the nesting rule: between a closer and its opener everything is itself balanced, hence contains no unmatched openers). So is a prefix of a balanced string iff the stack is non-empty and its top is the opener of the same type. If it is, popping yields exactly the new set of unmatched openers in order. If not, no completion exists and returning
falseis correct.
At the end, is balanced iff it is a prefix of a balanced string with no unmatched openers, i.e. iff the algorithm has not returned false and the stack is empty.
The single-counter method is the special case where openers are indistinguishable, so the stack carries no information beyond its height.
Shunting-yard: the precedence invariant
Invariant. At every moment, reading the operator stack from bottom to top and ignoring ( markers, precedences within each parenthesis group are non-decreasing, and two adjacent operators of equal precedence in the stack occur only if that precedence level is right-associative.
Why it holds. The only way an operator enters the stack is after the pop loop has removed every top operator with , or with when is left-associative. So when is pushed, the operator beneath it (within the group) has lower precedence, or equal precedence with right-associative. Pushing ( starts a fresh group, and ) removes a whole group. No other operation touches the stack.
Why the invariant implies correctness. An operator is emitted to output exactly when an operator of lower-or-equal precedence (or a ) or end of input) arrives. Everything emitted before it was emitted earlier in time, hence binds tighter or appears to its left at equal precedence; everything emitted after it binds looser. In postfix, an operator applies to the two values most recently completed, so emitting in this order means each operator applies to exactly the operands the precedence/associativity rules assign it. For a complete formal proof see Knuth, The Art of Computer Programming, Vol. 1, §2.3.1, or the treatment in Aho, Lam, Sethi & Ullman (the Dragon Book), §4.4 on operator-precedence parsing.
RPN evaluation
Invariant. After processing the first tokens of a well-formed RPN string, the operand stack holds the values of the maximal complete subexpressions among those tokens, in left-to-right order. An operator token completes a subexpression from the two most recent complete subexpressions — which are exactly the top two stack entries — so applying it and pushing restores the invariant. A well-formed RPN string is a single complete expression, so one value remains.
Complexity
| Operation | Array-backed | Linked |
|---|---|---|
push | amortized; worst-case when resizing | worst-case |
pop, peek, isEmpty, size | ||
| Space for elements | to slots (growth factor 2) | nodes, each value + pointer + allocator overhead |
Algorithms on this page:
| Algorithm | Time | Space |
|---|---|---|
| Bracket matching | worst case (all openers) | |
| Min-stack operations | each | auxiliary, or auxiliary with differences |
| Shunting-yard | — each token is pushed and popped at most once | |
| RPN evaluation | ||
| Two-stack infix evaluation | ||
| Queue via two stacks | amortized per operation | |
| Iterative DFS / inorder | / | / |
Constants: an array-backed stack of integers is about as fast as any data structure gets. push is a bounds check, a store, and an increment; the top of the stack is almost always in L1 cache because it was just touched. The cost that actually shows up in profiles is the resize copy (mitigated by pre-sizing when is known) and, in languages with boxed values, the allocation per element. For the shunting-yard family, tokenisation usually costs more than the stack work.
Implementation
Three canonical pieces, each self-checking with identical test data in all four languages:
isValid— bracket matching.MinStack— auxiliary-stack version.evaluate— Dijkstra's two-stack infix evaluator supporting+ - * /, parentheses, and unary minus, over integers. Division truncates toward zero in every language: Java, C++, andMath.truncin JavaScript already do that; Python's//floors, so the Python version computes the truncated quotient explicitly.
from __future__ import annotations
def is_valid(s: str) -> bool:
pairs = {")": "(", "]": "[", "}": "{"}
stack: list[str] = []
for ch in s:
if ch in "([{":
stack.append(ch)
elif ch in pairs:
if not stack or stack[-1] != pairs[ch]:
return False
stack.pop()
else:
return False # not a bracket
return not stack
class MinStack:
def __init__(self) -> None:
self._main: list[int] = []
self._mins: list[int] = []
def push(self, x: int) -> None:
self._main.append(x)
self._mins.append(x if not self._mins else min(x, self._mins[-1]))
def pop(self) -> int:
self._mins.pop()
return self._main.pop()
def top(self) -> int:
return self._main[-1]
def get_min(self) -> int:
return self._mins[-1]
# ---- infix evaluator: Dijkstra's two-stack algorithm ----
PREC = {"+": 1, "-": 1, "*": 2, "/": 2, "~": 3} # '~' = unary minus
RIGHT_ASSOC = {"~"}
def _trunc_div(a: int, b: int) -> int:
"""Integer division truncating toward zero (C/Java semantics)."""
if b == 0:
raise ZeroDivisionError("division by zero")
q = abs(a) // abs(b)
return q if (a < 0) == (b < 0) else -q
def _apply(op: str, operands: list[int]) -> None:
if op == "~":
operands.append(-operands.pop())
return
b = operands.pop()
a = operands.pop()
if op == "+":
operands.append(a + b)
elif op == "-":
operands.append(a - b)
elif op == "*":
operands.append(a * b)
else:
operands.append(_trunc_div(a, b))
def evaluate(expr: str) -> int:
operands: list[int] = []
ops: list[str] = []
i, n = 0, len(expr)
prev_was_operand = False # decides whether '-' is unary
while i < n:
c = expr[i]
if c == " ":
i += 1
continue
if c.isdigit():
j = i
while j < n and expr[j].isdigit():
j += 1
operands.append(int(expr[i:j]))
i = j
prev_was_operand = True
continue
if c == "(":
ops.append(c)
prev_was_operand = False
elif c == ")":
while ops[-1] != "(":
_apply(ops.pop(), operands)
ops.pop()
prev_was_operand = True
else:
op = "~" if (c == "-" and not prev_was_operand) else c
while ops and ops[-1] != "(" and (
PREC[ops[-1]] > PREC[op]
or (PREC[ops[-1]] == PREC[op] and op not in RIGHT_ASSOC)
):
_apply(ops.pop(), operands)
ops.append(op)
prev_was_operand = False
i += 1
while ops:
_apply(ops.pop(), operands)
return operands[-1]
if __name__ == "__main__":
assert is_valid("([]{()})")
assert not is_valid("([)]")
assert not is_valid("((")
assert not is_valid("))")
assert is_valid("")
ms = MinStack()
for v in (5, 3, 7, 3):
ms.push(v)
got = [ms.get_min(), ms.pop(), ms.get_min(), ms.pop(), ms.get_min(), ms.pop(), ms.get_min()]
assert got == [3, 3, 3, 7, 3, 3, 5], got
cases = {
"1 + 2 * 3": 7,
"(1 + 2) * 3": 9,
"7 / 2": 3,
"-7 / 2": -3,
"(-7) / 2": -3,
"2 - -3": 5,
"-(3 + 4) * 2": -14,
"100 - 3 * (4 + 5) / 2": 87,
"10 / 3 * 3": 9,
"3 + 4 * 2 / (1 - 5)": 1,
"--4": 4,
}
for expr, want in cases.items():
assert evaluate(expr) == want, (expr, evaluate(expr), want)
print("stacks: all tests passed")
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.List;
import java.util.Map;
public class Stacks {
static boolean isValid(String s) {
Deque<Character> stack = new ArrayDeque<>();
for (char ch : s.toCharArray()) {
switch (ch) {
case '(', '[', '{' -> stack.push(ch);
case ')' -> { if (stack.isEmpty() || stack.pop() != '(') return false; }
case ']' -> { if (stack.isEmpty() || stack.pop() != '[') return false; }
case '}' -> { if (stack.isEmpty() || stack.pop() != '{') return false; }
default -> { return false; }
}
}
return stack.isEmpty();
}
static final class MinStack {
private final Deque<Integer> main = new ArrayDeque<>();
private final Deque<Integer> mins = new ArrayDeque<>();
void push(int x) {
main.push(x);
mins.push(mins.isEmpty() ? x : Math.min(x, mins.peek()));
}
int pop() {
mins.pop();
return main.pop();
}
int top() { return main.peek(); }
int getMin() { return mins.peek(); }
}
// ---- infix evaluator: Dijkstra's two-stack algorithm ----
static final Map<Character, Integer> PREC = Map.of('+', 1, '-', 1, '*', 2, '/', 2, '~', 3);
static void apply(char op, Deque<Long> operands) {
if (op == '~') { operands.push(-operands.pop()); return; }
long b = operands.pop();
long a = operands.pop();
switch (op) {
case '+' -> operands.push(a + b);
case '-' -> operands.push(a - b);
case '*' -> operands.push(a * b);
case '/' -> operands.push(a / b); // Java '/' truncates toward zero
default -> throw new IllegalArgumentException("bad op " + op);
}
}
static long evaluate(String expr) {
Deque<Long> operands = new ArrayDeque<>();
Deque<Character> ops = new ArrayDeque<>();
boolean prevWasOperand = false;
int i = 0, n = expr.length();
while (i < n) {
char c = expr.charAt(i);
if (c == ' ') { i++; continue; }
if (Character.isDigit(c)) {
int j = i;
while (j < n && Character.isDigit(expr.charAt(j))) j++;
operands.push(Long.parseLong(expr.substring(i, j)));
i = j;
prevWasOperand = true;
continue;
}
if (c == '(') {
ops.push(c);
prevWasOperand = false;
} else if (c == ')') {
while (ops.peek() != '(') apply(ops.pop(), operands);
ops.pop();
prevWasOperand = true;
} else {
char op = (c == '-' && !prevWasOperand) ? '~' : c;
boolean rightAssoc = op == '~';
while (!ops.isEmpty() && ops.peek() != '('
&& (PREC.get(ops.peek()) > PREC.get(op)
|| (PREC.get(ops.peek()).equals(PREC.get(op)) && !rightAssoc))) {
apply(ops.pop(), operands);
}
ops.push(op);
prevWasOperand = false;
}
i++;
}
while (!ops.isEmpty()) apply(ops.pop(), operands);
return operands.peek();
}
static void check(boolean cond, String msg) {
if (!cond) throw new AssertionError(msg);
}
public static void main(String[] args) {
check(isValid("([]{()})"), "balanced");
check(!isValid("([)]"), "interleaved");
check(!isValid("(("), "unclosed");
check(!isValid("))"), "unopened");
check(isValid(""), "empty");
MinStack ms = new MinStack();
for (int v : new int[]{5, 3, 7, 3}) ms.push(v);
List<Integer> got = List.of(ms.getMin(), ms.pop(), ms.getMin(), ms.pop(), ms.getMin(), ms.pop(), ms.getMin());
check(got.equals(List.of(3, 3, 3, 7, 3, 3, 5)), "minstack " + got);
String[] exprs = {"1 + 2 * 3", "(1 + 2) * 3", "7 / 2", "-7 / 2", "(-7) / 2", "2 - -3",
"-(3 + 4) * 2", "100 - 3 * (4 + 5) / 2", "10 / 3 * 3", "3 + 4 * 2 / (1 - 5)", "--4"};
long[] want = {7, 9, 3, -3, -3, 5, -14, 87, 9, 1, 4};
for (int k = 0; k < exprs.length; k++) {
long got2 = evaluate(exprs[k]);
check(got2 == want[k], exprs[k] + " = " + got2 + ", want " + want[k]);
}
System.out.println("stacks: all tests passed");
}
}
#include <cctype>
#include <cstdint>
#include <cstdlib>
#include <iostream>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
static void check(bool cond, const std::string& msg) {
if (!cond) { std::cerr << "FAIL: " << msg << "\n"; std::exit(1); }
}
bool isValid(const std::string& s) {
std::stack<char> st;
for (char ch : s) {
switch (ch) {
case '(': case '[': case '{': st.push(ch); break;
case ')': if (st.empty() || st.top() != '(') return false; st.pop(); break;
case ']': if (st.empty() || st.top() != '[') return false; st.pop(); break;
case '}': if (st.empty() || st.top() != '{') return false; st.pop(); break;
default: return false;
}
}
return st.empty();
}
class MinStack {
std::vector<int> main_, mins_;
public:
void push(int x) {
main_.push_back(x);
mins_.push_back(mins_.empty() ? x : std::min(x, mins_.back()));
}
int pop() { int v = main_.back(); main_.pop_back(); mins_.pop_back(); return v; }
int top() const { return main_.back(); }
int getMin() const { return mins_.back(); }
};
// ---- infix evaluator: Dijkstra's two-stack algorithm ----
static const std::unordered_map<char, int> PREC = {{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}, {'~', 3}};
static void apply(char op, std::vector<std::int64_t>& operands) {
if (op == '~') { operands.back() = -operands.back(); return; }
std::int64_t b = operands.back(); operands.pop_back();
std::int64_t a = operands.back(); operands.pop_back();
switch (op) {
case '+': operands.push_back(a + b); break;
case '-': operands.push_back(a - b); break;
case '*': operands.push_back(a * b); break;
case '/': operands.push_back(a / b); break; // C++ '/' truncates toward zero
}
}
std::int64_t evaluate(const std::string& expr) {
std::vector<std::int64_t> operands;
std::vector<char> ops;
bool prevWasOperand = false;
std::size_t i = 0, n = expr.size();
while (i < n) {
char c = expr[i];
if (c == ' ') { ++i; continue; }
if (std::isdigit(static_cast<unsigned char>(c))) {
std::size_t j = i;
while (j < n && std::isdigit(static_cast<unsigned char>(expr[j]))) ++j;
operands.push_back(std::stoll(expr.substr(i, j - i)));
i = j;
prevWasOperand = true;
continue;
}
if (c == '(') {
ops.push_back(c);
prevWasOperand = false;
} else if (c == ')') {
while (ops.back() != '(') { apply(ops.back(), operands); ops.pop_back(); }
ops.pop_back();
prevWasOperand = true;
} else {
char op = (c == '-' && !prevWasOperand) ? '~' : c;
bool rightAssoc = (op == '~');
while (!ops.empty() && ops.back() != '('
&& (PREC.at(ops.back()) > PREC.at(op)
|| (PREC.at(ops.back()) == PREC.at(op) && !rightAssoc))) {
apply(ops.back(), operands);
ops.pop_back();
}
ops.push_back(op);
prevWasOperand = false;
}
++i;
}
while (!ops.empty()) { apply(ops.back(), operands); ops.pop_back(); }
return operands.back();
}
int main() {
check(isValid("([]{()})"), "balanced");
check(!isValid("([)]"), "interleaved");
check(!isValid("(("), "unclosed");
check(!isValid("))"), "unopened");
check(isValid(""), "empty");
MinStack ms;
for (int v : {5, 3, 7, 3}) ms.push(v);
std::vector<int> got = {ms.getMin(), ms.pop(), ms.getMin(), ms.pop(), ms.getMin(), ms.pop(), ms.getMin()};
check(got == std::vector<int>{3, 3, 3, 7, 3, 3, 5}, "minstack");
const std::vector<std::pair<std::string, std::int64_t>> cases = {
{"1 + 2 * 3", 7}, {"(1 + 2) * 3", 9}, {"7 / 2", 3}, {"-7 / 2", -3}, {"(-7) / 2", -3},
{"2 - -3", 5}, {"-(3 + 4) * 2", -14}, {"100 - 3 * (4 + 5) / 2", 87}, {"10 / 3 * 3", 9},
{"3 + 4 * 2 / (1 - 5)", 1}, {"--4", 4}};
for (const auto& [expr, want] : cases) {
std::int64_t got2 = evaluate(expr);
check(got2 == want, expr + " = " + std::to_string(got2));
}
std::cout << "stacks: all tests passed\n";
return 0;
}
function isValid(s: string): boolean {
const pairs: Record<string, string> = { ")": "(", "]": "[", "}": "{" };
const stack: string[] = [];
for (const ch of s) {
if (ch === "(" || ch === "[" || ch === "{") {
stack.push(ch);
} else if (ch in pairs) {
if (stack.length === 0 || stack[stack.length - 1] !== pairs[ch]) return false;
stack.pop();
} else {
return false;
}
}
return stack.length === 0;
}
class MinStack {
private main: number[] = [];
private mins: number[] = [];
push(x: number): void {
this.main.push(x);
this.mins.push(this.mins.length === 0 ? x : Math.min(x, this.mins[this.mins.length - 1]));
}
pop(): number {
this.mins.pop();
return this.main.pop()!;
}
top(): number {
return this.main[this.main.length - 1];
}
getMin(): number {
return this.mins[this.mins.length - 1];
}
}
// ---- infix evaluator: Dijkstra's two-stack algorithm ----
const PREC: Record<string, number> = { "+": 1, "-": 1, "*": 2, "/": 2, "~": 3 }; // '~' = unary minus
function applyOp(op: string, operands: number[]): void {
if (op === "~") {
operands.push(-operands.pop()!);
return;
}
const b = operands.pop()!;
const a = operands.pop()!;
switch (op) {
case "+": operands.push(a + b); break;
case "-": operands.push(a - b); break;
case "*": operands.push(a * b); break;
case "/": operands.push(Math.trunc(a / b)); break; // truncate toward zero
default: throw new Error("bad op " + op);
}
}
function evaluate(expr: string): number {
const operands: number[] = [];
const ops: string[] = [];
let prevWasOperand = false;
let i = 0;
const n = expr.length;
while (i < n) {
const c = expr[i];
if (c === " ") { i++; continue; }
if (c >= "0" && c <= "9") {
let j = i;
while (j < n && expr[j] >= "0" && expr[j] <= "9") j++;
operands.push(Number(expr.slice(i, j)));
i = j;
prevWasOperand = true;
continue;
}
if (c === "(") {
ops.push(c);
prevWasOperand = false;
} else if (c === ")") {
while (ops[ops.length - 1] !== "(") applyOp(ops.pop()!, operands);
ops.pop();
prevWasOperand = true;
} else {
const op = c === "-" && !prevWasOperand ? "~" : c;
const rightAssoc = op === "~";
while (
ops.length > 0 &&
ops[ops.length - 1] !== "(" &&
(PREC[ops[ops.length - 1]] > PREC[op] ||
(PREC[ops[ops.length - 1]] === PREC[op] && !rightAssoc))
) {
applyOp(ops.pop()!, operands);
}
ops.push(op);
prevWasOperand = false;
}
i++;
}
while (ops.length > 0) applyOp(ops.pop()!, operands);
return operands[operands.length - 1];
}
function check(cond: boolean, msg: string): void {
if (!cond) throw new Error("FAIL: " + msg);
}
check(isValid("([]{()})"), "balanced");
check(!isValid("([)]"), "interleaved");
check(!isValid("(("), "unclosed");
check(!isValid("))"), "unopened");
check(isValid(""), "empty");
const ms = new MinStack();
for (const v of [5, 3, 7, 3]) ms.push(v);
const got = [ms.getMin(), ms.pop(), ms.getMin(), ms.pop(), ms.getMin(), ms.pop(), ms.getMin()];
check(JSON.stringify(got) === JSON.stringify([3, 3, 3, 7, 3, 3, 5]), "minstack " + got);
const cases: Array<[string, number]> = [
["1 + 2 * 3", 7], ["(1 + 2) * 3", 9], ["7 / 2", 3], ["-7 / 2", -3], ["(-7) / 2", -3],
["2 - -3", 5], ["-(3 + 4) * 2", -14], ["100 - 3 * (4 + 5) / 2", 87], ["10 / 3 * 3", 9],
["3 + 4 * 2 / (1 - 5)", 1], ["--4", 4],
];
for (const [expr, want] of cases) {
const got2 = evaluate(expr);
check(got2 === want, `${expr} = ${got2}, want ${want}`);
}
console.log("stacks: all tests passed");
Notes on the evaluator:
prev_was_operandis the whole unary-minus story. It is true after a number or a), false after an operator or(or at the start. A-seen when it is false is unary.- The operand stack holds 64-bit integers in Java and C++; JavaScript numbers are doubles with 53 bits of exact integer precision, which is enough for these tests but not for a general calculator (use
BigIntthere). - Error handling is deliberately minimal (a malformed expression will throw an index error or similar). A production parser should tokenise first and validate the token sequence; see Regex Mastery for the lexing side.
- To support
^, add it with precedence 3 and right associativity, bump~to 4, and decide what-2 ^ 2should mean; most languages that have both treat unary minus as binding looser than exponentiation, so-2 ^ 2 = -4, which would put~at precedence between*and^instead. There is no universal answer; document whichever you pick.
Variant: shunting-yard producing RPN
If you need the postfix string itself (to compile once and evaluate many times, say), replace "apply" with "append to output" and tokenise the output. The trace table above is exactly what that variant produces.
def to_rpn(tokens: list[str]) -> list[str]:
prec = {"+": 1, "-": 1, "*": 2, "/": 2, "^": 3}
right = {"^"}
out: list[str] = []
ops: list[str] = []
for t in tokens:
if t.isdigit():
out.append(t)
elif t == "(":
ops.append(t)
elif t == ")":
while ops[-1] != "(":
out.append(ops.pop())
ops.pop()
else:
while ops and ops[-1] != "(" and (
prec[ops[-1]] > prec[t] or (prec[ops[-1]] == prec[t] and t not in right)
):
out.append(ops.pop())
ops.append(t)
while ops:
out.append(ops.pop())
return out
assert to_rpn("3 + 4 * 2 / ( 1 - 5 ) ^ 2".split()) == "3 4 2 * 1 5 - 2 ^ / +".split()
assert to_rpn("2 ^ 3 ^ 2".split()) == "2 3 2 ^ ^".split() # right-assoc
assert to_rpn("8 / 4 / 2".split()) == "8 4 / 2 /".split() # left-assoc
Real-world uses
Call stacks and stack traces. Every exception report you have ever read is a dump of the call stack at the moment of the throw. Profilers (perf, async-profiler, py-spy) sample the call stack thousands of times per second and aggregate the frames into flame graphs; the entire technique rests on the stack being walkable. Debuggers' "step out" is "run until this frame is popped".
Operand stacks in the JVM, CPython, and WebAssembly. As described above, three of the most widely deployed execution engines compile source to stack-machine bytecode. The JVM verifier type-checks the operand stack statically; WebAssembly's validation does the same and is what lets browsers compile untrusted modules safely.
Parsers. Every LR parser (yacc, bison, the parsers in GCC and Clang for certain sublanguages) is a pushdown automaton: a finite control plus a stack of grammar states. Recursive-descent parsers use the call stack instead, which is why deeply nested input can crash them with a stack overflow, a real class of denial-of-service bug in JSON and XML parsers. The theory is the pushdown automaton / context-free grammar equivalence; the practice is covered alongside lexing in Regex Mastery.
Undo systems and back buttons. Text editors (Emacs's undo ring is a variant), image editors with history panels, IDEs, and browser history are two-stack undo/redo. Emacs is an interesting exception: its undo list never clears the redo branch, so undoing an undo is itself an action, which makes history a stack that never forgets.
Garbage collectors. The mark phase of a tracing collector is a graph traversal from the roots; HotSpot's collectors use explicit mark stacks (with overflow handling to a separate structure when the stack fills), and Go's collector uses per-processor work buffers. Nobody uses recursion here, because the object graph can be millions deep and the collector runs on a fixed-size thread stack.
Transaction savepoints. SQL SAVEPOINT creates a nested checkpoint inside a transaction; ROLLBACK TO SAVEPOINT x discards everything after x and destroys every savepoint created after it, which is a stack pop down to a named entry. PostgreSQL's documentation states this explicitly. The implementation in Write-Ahead Logging and How Databases Work is a stack of sub-transaction records.
Memory allocators and arena stacks. The fastest allocator is a bump allocator, which is a stack: allocation increments a pointer, and freeing everything resets it. Compilers use these for per-phase allocations; see Memory Allocators.
Pitfalls & edge cases
- Popping an empty stack. The source of most crashes in bracket-matching and evaluator code. Always check
isEmpty()beforepop()on input you do not control. In JavaScript,[].pop()returnsundefinedwith no error; a comparison against it then silently fails, so guard explicitly. - Forgetting to flush the operator stack at the end of shunting-yard, or forgetting to pop the
(after processing). Both leave operators stranded and produce a too-short output. - Unary minus. Decide the rule (unary iff at start, after
(, or after an operator) and test2 - -3,-(1),--4, and(-7) / 2. - Integer division semantics. Python
//floors (); C, C++, Java, Go, Rust truncate toward zero (); JavaScript/is floating point and needsMath.trunc. Interview problems almost always specify truncation. Also check%: Python's result takes the sign of the divisor, C/Java's the sign of the dividend. - Java
Stack. It is a synchronizedVector. It is slower, it permitsget(i), and it iterates bottom-to-top. UseArrayDeque. If you need the stack's contents in push order, iterate withdescendingIterator(). - Recursion depth. A recursive bracket matcher or expression parser on adversarial input (
((((...ten thousand deep) overflows the call stack in Python and often in Java. The iterative versions on this page do not. - Stack of pairs vs two parallel stacks. Both work for the min-stack; two parallel stacks are usually faster (no allocation per push in Java/Python), but they must be pushed and popped together, and an early
returnbetween the two operations desynchronises them. Prefer a single stack of records when the code has multiple exits. - Peek before pop in C++.
std::stack::pop()returnsvoid;int v = st.pop();does not compile, and the idiom isint v = st.top(); st.pop();. - Null elements in
ArrayDeque. It throwsNullPointerExceptiononpush(null). Use a sentinel object orOptional. - Growth in a pre-sized array stack. If you implement your own fixed-capacity stack,
pushon a full stack must either grow or fail; silently overwriting indexcapacityis a memory-safety bug in C++ and an exception in Java. - Decode-string with multi-digit counts.
12[a]has a count of 12, not 1 then 2; accumulate digits withcount = count * 10 + digit. - Store-difference min-stack overflow. The stored difference can exceed the input type's range. Use 64-bit storage for 32-bit inputs; do not use this trick for 64-bit inputs.
Variations
- Monotonic stack. A stack whose values are kept sorted by popping violators before each push. Turns "next greater element", "largest rectangle", "trapping rain water", and "sum of subarray minimums" into algorithms. The next-but-one lesson, Monotonic Stack & Monotonic Deque, is devoted to it.
- Min / max stack. The auxiliary-stack construction above, or the store-difference trick. Symmetric for max. A min-queue is harder and leads to the monotonic deque.
- Persistent stack. A linked stack where
pushreturns a new head pointing at the old one and never mutates; two versions share their common tail. Every version is a valid stack forever, in per operation. This is theconslist of Lisp and the foundation of persistent data structures. - Stack with
getMiddle/deleteMiddlein : keep a doubly linked list plus a pointer to the middle node and a size; on push/pop move the middle pointer by at most one step, depending on the parity of the new size. - Two stacks in one array. Grow one from index 0 upward and the other from index downward; the array is full when the two tops meet. Used in embedded systems and, historically, for the heap/stack split of a process address space.
- Stack of frames with timestamps. For "exclusive time of functions": a frame is pushed on
startand popped onend; the elapsed time of the inner call is subtracted from the frame below. - Deque as a stack. Every deque is also a stack (use one end).
ArrayDeque,std::deque, andcollections.dequeare all fine stacks; the pure stack ADT just promises less.
Practice ladder
Each problem is described in my own words. Solutions are Python and are run as part of this page's checks.
1. Valid Parentheses (LeetCode 20) — Easy. Three bracket types; decide if the string is balanced. Teaches the fundamental stack-of-openers invariant.
Hint
Map each closer to its opener. On a closer, the stack must be non-empty and its top must match. Do not forget the final isEmpty check.
2. Min Stack (LeetCode 155) — Medium. Stack with getMin in . Teaches the auxiliary-stack idea.
Hint
Keep a parallel stack of running minimums. Push min(x, mins.top) on every push, including when x equals the current minimum.
3. Evaluate Reverse Polish Notation (LeetCode 150) — Medium. Evaluate a postfix token list with + - * / and truncating division. Teaches operand ordering and division semantics.
Hint
The second value popped is the left operand. For division use int(a / b) in Python, which truncates toward zero (values fit in a double here), or implement truncation explicitly.
Solution
def eval_rpn(tokens: list[str]) -> int:
st: list[int] = []
for t in tokens:
if t in ("+", "-", "*", "/"):
b, a = st.pop(), st.pop()
if t == "+": st.append(a + b)
elif t == "-": st.append(a - b)
elif t == "*": st.append(a * b)
else:
q = abs(a) // abs(b)
st.append(q if (a < 0) == (b < 0) else -q)
else:
st.append(int(t))
return st[-1]
assert eval_rpn(["2", "1", "+", "3", "*"]) == 9
assert eval_rpn(["4", "13", "5", "/", "+"]) == 6
assert eval_rpn(["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]) == 22
assert eval_rpn(["3", "4", "2", "*", "1", "5", "-", "/", "+"]) == 1
Time , space . The third case is the one that catches floor division: 6 / -132 must give 0, not −1.
4. Implement Queue using Stacks (LeetCode 232) — Easy. Teaches the inbox/outbox transfer and amortized analysis.
Hint
Only pour inbox into outbox when outbox is empty. Argue each element moves at most once.
5. Implement Stack using Queues (LeetCode 225) — Easy. Teaches the rotation trick: after enqueuing, rotate the queue size − 1 times so the new element is at the front. Covered in Queues, Deques & Circular Buffers.
Hint
One queue suffices if you make push by rotating; pop and top are then .
6. Remove All Adjacent Duplicates In String (LeetCode 1047) — Easy. Teaches "the top interacts with the newcomer".
Hint
Push each character unless it equals the top, in which case pop. The stack at the end is the answer.
7. Simplify Path (LeetCode 71) — Medium. Canonicalise a Unix path with . and ... Teaches tokenising first, then stacking.
Hint
Split on /. Skip empty and .. On .., pop if non-empty. Join with / and prefix one /.
8. Decode String (LeetCode 394) — Medium. Expand nested k[...] groups. Teaches frames of (count, partial string).
Hint
Keep a current count and a current string. On [, push both and reset. On ], pop (prev_string, count) and set current to prev_string + current * count.
Solution
def decode_string(s: str) -> str:
stack: list[tuple[str, int]] = []
cur, count = "", 0
for ch in s:
if ch.isdigit():
count = count * 10 + int(ch)
elif ch == "[":
stack.append((cur, count))
cur, count = "", 0
elif ch == "]":
prev, k = stack.pop()
cur = prev + cur * k
else:
cur += ch
return cur
assert decode_string("3[a]2[bc]") == "aaabcbc"
assert decode_string("3[a2[c]]") == "accaccacc"
assert decode_string("2[abc]3[cd]ef") == "abcabccdcdcdef"
assert decode_string("12[x]") == "x" * 12
Time , space . The multi-digit accumulation (count * 10 + digit) is the usual slip.
9. Asteroid Collision (LeetCode 735) — Medium. Teaches a stack where the newcomer may destroy several survivors.
Hint
Only a right-moving top and a left-moving newcomer collide. Loop: compare magnitudes, pop or drop accordingly, stop when the newcomer dies or the top is left-moving.
Solution
def asteroid_collision(asteroids: list[int]) -> list[int]:
st: list[int] = []
for a in asteroids:
alive = True
while alive and a < 0 and st and st[-1] > 0:
if st[-1] < -a:
st.pop() # top destroyed, keep checking
elif st[-1] == -a:
st.pop()
alive = False # both destroyed
else:
alive = False # newcomer destroyed
if alive:
st.append(a)
return st
assert asteroid_collision([5, 10, -5]) == [5, 10]
assert asteroid_collision([8, -8]) == []
assert asteroid_collision([10, 2, -5]) == [10]
assert asteroid_collision([-2, -1, 1, 2]) == [-2, -1, 1, 2]
Time : each asteroid is pushed at most once and popped at most once. Space .
10. Validate Stack Sequences (LeetCode 946) — Medium. Given a push order and a pop order, decide if some interleaving of pushes and pops produces them. Teaches greedy simulation.
Hint
Simulate: push each element, then pop greedily while the top equals the next expected popped value. Valid iff the stack ends empty.
11. Score of Parentheses (LeetCode 856) — Medium. () scores 1, AB adds, (A) doubles. Teaches carrying partial scores in frames, and the counting shortcut.
Hint
Stack of partial scores: on ( push 0; on ) pop v, add max(2v, 1) to the new top. Or: every () at depth contributes .
Solution
def score_of_parentheses(s: str) -> int:
st = [0]
for ch in s:
if ch == "(":
st.append(0)
else:
v = st.pop()
st[-1] += max(2 * v, 1)
return st[0]
def score_counting(s: str) -> int:
depth, total = 0, 0
for i, ch in enumerate(s):
if ch == "(":
depth += 1
else:
depth -= 1
if s[i - 1] == "(":
total += 1 << depth
return total
for s, want in [("()", 1), ("(())", 2), ("()()", 2), ("(()(()))", 6)]:
assert score_of_parentheses(s) == want
assert score_counting(s) == want
Both time; the counting version is space, demonstrating that single-type parentheses often need only depth.
12. Exclusive Time of Functions (LeetCode 636) — Medium. From a log of start/end events with timestamps, compute each function's own (non-nested) time. Teaches the frame-stack model of a profiler.
Hint
On start, add elapsed time since the previous event to the function on top, then push. On end, pop and add elapsed + 1 to the popped function. Track prev_time carefully (end timestamps are inclusive).
13. Basic Calculator II (LeetCode 227) — Medium. + - * / without parentheses. Teaches the "apply the previous operator lazily" single-stack trick, and truncating division.
Hint
Keep a stack of signed terms. On +/- push the number (negated for -); on *// pop, combine with the current number, push. Sum the stack at the end.
14. Basic Calculator (LeetCode 224) — Hard. + - and parentheses with unary minus. Teaches sign-stack handling of nested negation.
Hint
Either run the two-stack evaluator from this page, or keep a stack of (result, sign) pairs: on ( push and reset; on ) pop and combine result = prev_result + prev_sign * inner.
15. Flatten Nested List Iterator (LeetCode 341) — Medium. Lazily iterate a nested list structure. Teaches recursion-to-stack conversion for iterators.
Hint
Stack of (list, index) frames. hasNext advances frames until the top points at an integer, pushing a new frame when it points at a list.
Going further: Basic Calculator III (LeetCode 772) (premium) adds * and / to the parenthesised calculator, and the canonical evaluator on this page solves it as-is; Longest Valid Parentheses (LeetCode 32) is the hard follow-up that stores indices on the stack with a −1 base.
Common mistakes & interview follow-ups
"What if the expression comes as a stream and you cannot see the whole thing?" Both shunting-yard and the two-stack evaluator are single-pass and online: they consume one token at a time and keep only the stacks. The result is available as soon as the stream ends. Nothing changes.
"Can you make getMin work for a queue?" Not with a stack trick. A queue removes from the opposite end to insertion, so the running-minimum column no longer works. The answer is a monotonic deque holding candidate minimums, which gives amortized getMin, or two min-stacks forming a queue (each dequeue takes the min of the two stacks' mins). Both are in the next two lessons.
"Your min-stack uses extra space. Can you do better?" The store-difference trick above uses extra space with a 64-bit caveat. If the interviewer pushes further: for comparison-based stacks, bits of information must be stored somewhere to answer getMin after arbitrary pops, so the difference trick is really encoding that information into the stored values, not eliminating it.
"How would you evaluate 2 ^ 3 ^ 2?" Right-associative: 512. Point out that this is a precedence-table decision, show where in the pop condition associativity enters, and mention that unary minus versus ^ is a design choice.
"The recursion depth is 10⁶. What do you do?" Convert to an explicit stack of frames (show the two-phase frame for post-order work), or in Python raise sys.setrecursionlimit and threading.stack_size (the limit alone will segfault), or in Java run the work on a Thread constructed with a large stack size. Explain that the explicit stack is heap-allocated and bounded only by memory.
"Why not java.util.Stack?" Synchronised Vector, legacy, iterates in the wrong order, permits random access that breaks the LIFO contract. The Javadoc recommends Deque.
"How does the JVM know how big to make the operand stack?" The compiler computes max_stack per method and stores it in the class file; the verifier checks that no bytecode path exceeds it.
"Implement a stack that also supports increment(k, val): add val to the bottom k elements." Lazy increments: keep a parallel array inc where inc[i] is added to element i and everything below when popped; on increment(k, val) do inc[min(k, size) − 1] += val; on pop, propagate inc[top] to inc[top − 1]. per operation.
"Why does the browser's forward stack get cleared when I navigate somewhere new?" Because history is linear; the undone branch has no place in a linear model. Emacs's undo ring shows the alternative: never clear, treat undo as an action, and accept a stranger user model.
Common mistakes seen in interviews: forgetting the final empty check in bracket matching; pop before isEmpty; using // in Python for truncating division; pushing values instead of indices when lengths or distances are needed; and declaring a problem "needs a stack" when a counter suffices (single bracket type), or "needs a counter" when it does not (mixed types).
Quick quiz
- Why does a single counter fail to validate
([)], and what does the stack store that the counter does not?
Answer
The counter sees one opener of each type and one closer of each type, never going negative and ending at zero. It has no memory of which opener is pending when ) arrives. The stack stores the identity of every unmatched opener in order, so when ) arrives it sees [ on top and rejects.
- In shunting-yard, when
/arrives and*is on top of the operator stack, what happens and why?
Answer
* and / have equal precedence and are left-associative, so * is popped to output before / is pushed. This makes a * b / c evaluate as (a * b) / c. If / were pushed without popping, the output would correspond to a * (b / c).
- In the store-difference min-stack, you pop and the stored value is negative. What was the popped element's value, and how do you restore the minimum?
Answer
A negative stored value means the popped element was the minimum at the time it was pushed, so its value is the current mn. The stored value is x − previous_mn = mn − previous_mn, hence previous_mn = mn − stored. Restore mn to that.
- A dequeue in the two-stack queue just moved 1,000 elements. What is the worst case for the next 1,000 operations?
Answer
Each of the 1,000 moved elements will be popped from outbox at most once, costing 1 each, and new enqueues cost 1 each. No further move can happen until outbox empties, and the elements moved then are exactly those enqueued since. The total over any sequence of operations is at most , so amortized .
- Why can a recursive-descent JSON parser be a denial-of-service vector, and what fixes it?
Answer
Each nesting level consumes a call-stack frame. Input like [[[[... 100,000 deep overflows the native stack and crashes the process. The fix is either an explicit depth limit (what most production parsers do) or an iterative parser with a heap-allocated stack.
Further reading / sources
- Sedgewick & Wayne, Algorithms, 4th ed., §1.3 "Bags, Queues, and Stacks" — the two-stack evaluator and resizing-array stack with amortized analysis.
- Knuth, The Art of Computer Programming, Vol. 1, §2.2.1 "Stacks, Queues, and Deques" and §2.3.1 on expression conversion.
- Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms, 4th ed., §10.1 "Simple array-based data structures: arrays, matrices, stacks, queues"; Chapter 16 "Amortized Analysis" for the two-stack queue.
- Aho, Lam, Sethi & Ullman, Compilers: Principles, Techniques, and Tools, 2nd ed., §4.4 (operator precedence) and §2.8 (intermediate code for expressions).
- E. W. Dijkstra, "Algol 60 translation", Mathematisch Centrum Report MR 34/61, 1961 — the shunting-yard algorithm. Wikipedia: Shunting yard algorithm.
- F. L. Bauer & K. Samelson, "Sequential formula translation", Communications of the ACM 3(2), 1960 — the Kellerprinzip.
- Y. Shi, K. Casey, M. A. Ertl & D. Gregg, "Virtual machine showdown: stack versus registers", VEE 2005 / ACM TACO 2008.
- The Java Virtual Machine Specification, SE 21, §2.6 "Frames" and §4.7.3 "The Code Attribute" (
max_stack). - WebAssembly Core Specification, §4 "Execution" — the stack machine model.
- PostgreSQL documentation,
ROLLBACK TO SAVEPOINT— savepoints as a stack. - Java
java.util.StackJavadoc — "A more complete and consistent set of LIFO stack operations is provided by the Deque interface".
Prev: Strings in Depth · Next: Queues, Deques & Circular Buffers
Related: Module 1 — Linear Data Structures · Monotonic Stack & Monotonic Deque · Recursion & Mathematical Induction · Complexity Analysis · Linked Lists · Trees · Backtracking & Recursion · Advanced Data Structures · DSA: Zero to Mastery