Stacks

The 10-second versionCopy Anchor Link

A stack is a container with a single opening. You add things to the top and you remove things from the top — and nothing else can reach into the middle. That rule, last in, first out (LIFO), sounds limiting until you notice how often the most recent thing is also the most relevant thing: the last place you were, the last ( you opened, the last edit you made. Three operations do everything: push (add to the top), pop (remove the top), and peek (look at the top without removing it). All three cost O(1).

Why this existedCopy Anchor Link

Before "the stack" had a name, there was a bug hiding in every program with subroutines. You call a helper, the helper finishes, and the CPU has to jump back to exactly the spot that called it. Fine for one call. But what if the helper calls another helper, which calls another? Each level needs to remember its own return spot — and they can't all share one address.

• 1946 — Alan Turing sketches his Automatic Computing Engine (ACE) and thinks hard about subroutine linkage: how a machine returns to a caller while calls nest.
• 1949 — in his lectures on the ACE, Turing explains nesting with a running staircase of return addresses — an early, explicit statement of the idea we now call a stack.
• 1957 — Friedrich Bauer (with Klaus Samelson) files a patent on the push-down store: a dedicated memory for exactly this job. This is the origin of the hardware and software stack.
• 1958–1960 — the ALGOL reports use the term "stack" for the mechanism, and the name sticks for good.

Why it mattered then: it turned the messy business of nested control flow into a single, provable rule. Once you have a stack, "return to the caller" is automatic — you pop. That is the machinery that made high-level languages, and recursion itself, possible.

Inside the inventor's headCopy Anchor Link

Start with the naive idea. You're writing an assembler in the 1940s. A subroutine needs a return address, so you keep one slot for it:

That's the pivot. The problem was never "store an address" — it was "store a stack of addresses and recover them in exactly the reverse order you saved them in." The last call is the first to return. LIFO isn't a quirk; it's the shape of nesting.

The same insight lets you replace recursion with an explicit stack — handy when the hidden call stack would overflow. Watch the two attempts side by side:

// Naive: recursion reuses the hidden call stack, one frame per character.function reverseNaive(chars, lo = 0, hi = chars.length - 1) {  if (lo >= hi) return chars;  [chars[lo], chars[hi]] = [chars[hi], chars[lo]];  return reverseNaive(chars, lo + 1, hi - 1);}

function reverseStack(s) {  const stack = [];  for (const ch of s) stack.push(ch);      // push every char  let out = "";  while (stack.length) out += stack.pop(); // pop them, reversed  return out;}

Both reverse the string. The difference is who owns the pile: the first version hides it in the runtime, the second keeps it in your own hands — which is why you can grow it, inspect it, or throw it away.

The final approachCopy Anchor Link

The memory pictureCopy Anchor Link

A stack is dead simple: a top pointer and the slots below it.

The algorithm is a pair of tiny routines:

The invariantsCopy Anchor Link

Two rules keep it correct, and both are worth saying out loud:

• The top is always at index size - 1. size is the count of live elements; slots below 0 and above size - 1 don't exist.
• pop reverses push exactly. Whatever you pushed last is what you pop next — the mirror-image guarantee that makes nesting and backtracking work.

It in codeCopy Anchor Link

class Stack {  #data = [];  push(x) { this.#data.push(x); }                    // O(1)  pop()   { return this.#data.pop(); }               // undefined if empty  peek()  { return this.#data[this.#data.length - 1]; }  get size() { return this.#data.length; }}

Array vs linked: an array-backed stack is the default — it's cache-friendly and O(1) per operation. A linked stack (push/pop at the head of a list) gives you the same O(1) without ever needing to resize, at the cost of a pointer per element and scattered memory. Same interface, different trade on locality versus flexibility.

A worked trace: are the brackets balanced?Copy Anchor Link

The classic interview warm-up. Scan left to right, and let the stack remember what's still open:

End with an empty stack → balanced. A closing bracket that pops the wrong opener, or an empty stack when a closer arrives, means unbalanced. The stack is doing all the work: it remembers openers in the exact reverse order their closers will show up. That's LIFO earning its keep.

ComplexityCopy Anchor Link

Space is O(n) — one slot per element. That's it. The whole structure is a pointer and a rule.

Where you meet it todayCopy Anchor Link

• The call stack. Every function call pushes a frame (locals, arguments, return address) and pops it on return. That's why infinite recursion ends in a stack overflow — the pile literally ran out of room.
• Undo and redo. A text editor keeps a stack of edits; Ctrl+Z pops the last one, and a second stack holds what you undid so Ctrl+Y can push it back.
• Browser back/forward. One stack of visited pages, one of forward pages — pressing back pops the first and pushes onto the second.
• Bracket matching & expression evaluation. Compilers balance ()/[]/{} with a stack, and evaluate arithmetic from a b +-style notation with one too.

function isBalanced(s) {  const pairs = { ")": "(", "]": "[" };  const stack = [];  for (const c of s) {    if (c === "(" || c === "[") stack.push(c);           // push    else if (c in pairs) {      if (stack.pop() !== pairs[c]) return false;        // must match, LIFO    }  }  return stack.length === 0;                             // all closed?}

RecapCopy Anchor Link

• A stack is LIFO: push, pop, peek, all O(1).
• It's an array (or linked list) with one end you're allowed to touch — a top pointer is the whole trick.
• It exists because nesting needs reverse-order memory: Turing's return addresses, and every function call since.
• The killer apps are recursion, undo, browser history, and bracket matching — anything where "the most recent thing" is what you need next.

Next up: Queues & Deques — the opposite discipline, first in, first out, and the circular-buffer trick that keeps it cheap.