Stacks

The shape behind Cmd+Z

Press Cmd+Z right now. The thing that just got undone wasn't the first edit you made today, or a random one — it was the most recent one. Press it again: the second-most recent. Editors do this because it matches how human attention works — you finish what you started most recently before going back to anything older. That discipline has a name. It's called a stack, and once you see the shape, you start spotting it everywhere — in browser back buttons, in compilers checking your brackets, in the CPU itself remembering which function called which.

The data structure is so simple it is almost not a data structure. The reason to learn it is the shape, not the code.

Three rules and you have built one

A stack supports three operations and one read.

push(value)   // add a value to the top
pop()         // remove and return the top
peek()        // read the top without removing

That is the entire interface. There is no get(i), no search, no way to ask "what is the third item from the bottom". A stack only has a top. Anything beneath the top is invisible to it until enough pops have peeled the column down to expose it.

The implementation is two lines on top of an array — arr.push and arr.pop are already the right shape — but the implementation is rarely the interesting part. The interesting part is recognising the shape in problems where it isn't already wearing the word "stack".

Walk an input, push, pop, repeat

Here is a problem the stack solves cleanly: given a string of brackets, decide whether they are balanced. The string ( [ ] ) is balanced. The string ( [ ) ] is not. Look at the second one closely — every opener has a closer of the same type, the totals balance, and yet it is unbalanced. The order is wrong.

Walk the string left to right. On every opener, push the matching closer onto a stack. On every closer, pop the top and check it equals the character you just read. If it does, keep going. If it doesn't, fail. At the end, the string is balanced if and only if the stack is empty.

const PAIRS: Record<string, string> = { "(": ")", "[": "]", "{": "}" };

function isBalanced(s: string): boolean {
  const stack: string[] = [];
  for (const ch of s) {
    if (ch in PAIRS) stack.push(PAIRS[ch]);
    else if (stack.pop() !== ch) return false;
  }
  return stack.length === 0;
}

That is the entire parser. Twelve lines. The visualizer below runs it on three inputs — one that succeeds, one that fails on a mismatch, one that fails on a non-empty stack at the end. Watch which characters trigger pushes and which trigger pops.

The thing to notice is that the stack never grows tall. At any point during a balanced parse it holds the closers we are still waiting for — which is exactly the depth of the deepest unclosed bracket. The stack is doing the bookkeeping for us; we are just reading characters.

The shape is "the most recent thing must be handled before any older thing". Cmd+Z, browser back, balanced brackets, and a function call all share that constraint. None of them feel similar at first. They all are.

push always touches the top. The bottom of the column never moves while the stack is alive. This is the one thing the stack is opinionated about — and it is the reason pop and push are both O(1) with no shifting.

Why a mismatch is caught in one comparison

The bracket parser does not have to keep a list of unclosed openers and search through it. The stack discipline guarantees something stronger: at any moment, the top of the stack is the closer for the most recent unclosed opener. If the next character is a closer, it has to match the top — there is no other valid possibility, because anything that could have made a different match would already have been popped.

That is what the stack is enforcing. Not the count, the order. A counter would catch (() (totals don't balance). A stack catches ( [ ) ] (totals do balance, but nesting is wrong). The price is a structure that holds at most one cell per unclosed opener; the payoff is that mismatches surface in a single equality check.

Walking left to right and dispatching push-or-pop on each character is the entire mechanic. There is no lookahead, no backtracking, no recovery — just a single pass over the input.

peek is read-only, and that matters

The visualizer drew peek deliberately differently from pop — peek glows the top cell amber and returns its value without lifting it off; pop turns it blue, lifts it, and lets it fade. The animations differ because the operations differ. peek is read-only. The stack after a peek is bit-for-bit identical to the stack before it.

This sounds like an obvious distinction until you see it confused in real code.

Most of the time the bug looks innocent. The peek function does eventually return the right value, after all. The problem is that the next caller — maybe a parser, maybe a recursion checker — finds the stack one shorter than it expected, and the bug only surfaces several frames later. That is the classic shape of a "looks fine in isolation, breaks in production" defect.

The fix is to never call pop inside peek. The whole point of peek is that the stack survives.

Array-backed or linked-list-backed?

A stack is one of those rare data structures where you have a real choice about the underlying storage. An array works — push appends, pop removes the last element. A singly linked list also works — push prepends a node, pop unlinks the head. Both keep the operations O(1).

The textbook answer is "they're the same big-O, pick whichever". The honest answer is that the array is faster on real hardware by a wide margin.

The reason is locality. The hot end of the stack — the few cells you are pushing and popping — stays in the L1 cache because every operation touches the same memory region. Sequential push and pop have near-perfect cache behaviour. The linked-list variant pays for a heap allocation and a pointer dereference on every single push, and the nodes scatter across the heap as you allocate them, so even reading the top is a cache miss.

The amortised resize cost on the array, which the textbook flags as a worst-case O(n), is irrelevant in practice. Doubling means it happens log₂(n) times across n pushes, the resize itself is a memcpy of contiguous memory which modern CPUs vectorise, and the per-push amortised cost rounds to zero. Java's ArrayDeque (the recommended stack), Python's list, C++ std::stack (default-backed by std::deque), and Go's append-based pattern all use contiguous storage for exactly this reason.

The linked-list variant earns its place in three narrow cases: kernel and embedded code where every allocation must be explicit, intrusive structures where the node lives inside the data it represents, and academic exercises. In application code, the array wins.

Where this shows up in real systems

Stacks are the data structure that often disappear into the language runtime, but they are doing as much work as any structure on this list.

Every function call your code has ever made has pushed a frame onto the CPU's call stack — return address, saved registers, locals — and every return has popped it. That stack is a fixed-size region of memory the OS hands you on thread creation; on Linux the default is 8 MB, on Windows 1 MB. Recursion that exceeds the depth blows the stack and segfaults; allocating a million-entry buffer inside a single function does the same thing. Languages like Python add a softer second limit (sys.setrecursionlimit, default 1000) so you get a friendly RecursionError before the OS-level crash.

The JVM goes one step further — its bytecode is itself a stack machine. Every method call in Java compiles to operations on an operand stack: iadd pops two integers and pushes their sum, aload_0 pushes a reference. Each method has its own operand stack sized at compile time. The JIT eventually flattens this into machine code, but the bytecode is stack-based all the way down.

You will also build stacks of your own. Every editor with an undo button keeps a stack of edit operations; redo is a parallel stack populated when you undo, and a new edit clears the redo stack (which is why "back, then click a link, lose forward" feels intuitive — it is the stack discipline at work). Every browser back button is the same shape. Every shift-reduce parser, every backtracking solver, every iterative DFS over a graph — they all maintain a stack. PostScript and Forth are entire languages whose execution model is stack-based; PostScript ran every laser printer in the 1990s.

The takeaway is the inverse of how most data structures get taught. Most structures are taught as "here's a thing you build when you need it". The stack is taught best as "here's a shape that already governs much of what you write — name it, and you start to see it".

What to learn next

• Queues — the same simple interface with the opposite discipline. Oldest first, newest last. The pair of stack and queue is the foundation for almost every traversal pattern.
• Monotonic stack — once you have stacks, the next big payoff is the monotonic-stack pattern, which solves a class of "next greater element" problems in linear time. It looks like dark magic until you have lived with stacks for a while.
• BFS and DFS — depth-first search written iteratively is a stack. Switching the stack for a queue gives you breadth-first search. Two algorithms, one structural difference.