The Stack Abstraction

The LIFO Idea

Imagine a tray dispenser at a cafeteria, the kind with a spring-loaded base. Trays go in at the top; the top tray comes out first. Or stack a deck of plates: you can only put a plate on the top of the pile, and you can only take a plate off the top. The plate at the bottom of the pile—the one you put down first—is the last one you'll get back.

That single rule—last in, first out, abbreviated LIFO—is the whole story of a stack. Every operation, every algorithm, every weird kernel data structure built on top of a stack derives from this one constraint. It sounds restrictive, and it is. The restriction is exactly what makes stacks powerful: it forces a particular discipline of access that mirrors how humans (and compilers, and CPUs) handle nested things.

Why this matters: When you nest something inside something else—a function call inside another, a subexpression inside a bigger expression, a folder inside a folder, a parenthesis inside another parenthesis—you need to finish the inner thing before you can finish the outer thing. That discipline is exactly what a stack enforces. If you can recognize nesting, you have spotted a stack.

Stack as an Abstract Data Type

A stack is an abstract data type (ADT): we specify it by what it does, not by how it's built. Three core operations and two auxiliary ones:

Notice what is not on this list: there is no stack[k], no find(x), no insert_at(i, x). A stack does not let you reach inside. The only element addressable from the outside is the top. If you want anything below the top, you must pop everything above it first.

The Algebraic Axioms of a Stack

We can pin down the meaning of “LIFO” with four equations. Let $s$ be any stack and $x$ any element. Then:

1. $\text{pop}(\text{push}(s, x)) = (x, s)$ — pushing then popping returns exactly $x$ and leaves the original $s$ behind.
2. $\text{peek}(\text{push}(s, x)) = x$ — the top of a freshly pushed stack is the thing we just pushed.
3. $\text{is\_empty}(\text{empty}) = \text{true}$ — the empty stack reports itself as empty.
4. $\text{is\_empty}(\text{push}(s, x)) = \text{false}$ — any push makes the stack non-empty.

These four lines fully specify a stack. Given any sequence of pushes and pops, you can derive its final state and the value returned by every pop using only these rewrite rules. That's why it's called an algebraic specification: the equations behave like algebra, and any implementation that respects them is a correct stack—regardless of whether it's built from arrays, linked nodes, or carrier pigeons.

Cost of Every Operation

A well-implemented stack hits the same complexity table regardless of whether the underlying buffer is a dynamic array or a singly linked list. The only operation in the public surface area is “touch the top,” and the top is always one pointer/index away.

Interactive: Stack Visualizer

Below is a live stack. Cells stack vertically—the bottom cell was pushed first, the top cell was pushed last. Use push, pop, and peek to feel the rhythm. Watch what happens when you try to pop an empty stack, or push onto a full one.

Three things to notice as you play:

• The top is always at the same end. No matter how many elements are on the stack, every operation happens at the very top. We never reach down.
• Order is total. If you push A, B, C, you will pop C, B, A. There is no “skip the middle” primitive—and that constraint is exactly what makes the structure useful for nested problems.
• Pop on empty fails. A stack with no elements has no top. Some libraries return a sentinel; others raise. Both choices are defensible, but every robust stack does something predictable in this case.

A Stack in Python

With the contract clear, the implementation is short. Python's built-in list is already a perfect underlying buffer—append and pop at the tail are amortized O(1). We wrap a list in a class not because we need to, but because the wrapper enforces the LIFO discipline and gives our stack a name in the type system.

self._data = []   # contiguous heap buffer with spare slots

_data = [7, 3, 9]   ->   pop returns 9, _data becomes [7, 3]

_data = [7, 3, 9]   ->   peek returns 9, _data unchanged

1class Stack:
2    def __init__(self):
3        self._data: list = []
4
5    def push(self, x) -> None:
6        self._data.append(x)
7
8    def pop(self):
9        if not self._data:
10            raise IndexError("pop from empty stack")
11        return self._data.pop()
12
13    def peek(self):
14        if not self._data:
15            raise IndexError("peek on empty stack")
16        return self._data[-1]
17
18    def is_empty(self) -> bool:
19        return len(self._data) == 0
20
21    def __len__(self) -> int:
22        return len(self._data)
23
24# Usage
25s = Stack()
26s.push(7)
27s.push(3)
28s.push(9)
29print(s.peek())   # 9
30print(s.pop())    # 9
31print(len(s))     # 2

The Same Stack in TypeScript

Translating the same ADT into TypeScript shows where the language differences matter. The algorithm is identical; the type system does more work for us at compile time.

1class Stack<T> {
2  private data: T[] = [];
3
4  push(x: T): void {
5    this.data.push(x);
6  }
7
8  pop(): T {
9    const x = this.data.pop();
10    if (x === undefined) throw new Error("pop from empty stack");
11    return x;
12  }
13
14  peek(): T {
15    if (this.data.length === 0) throw new Error("peek on empty stack");
16    return this.data[this.data.length - 1];
17  }
18
19  isEmpty(): boolean {
20    return this.data.length === 0;
21  }
22
23  get size(): number {
24    return this.data.length;
25  }
26}
27
28const s = new Stack<number>();
29s.push(7);
30s.push(3);
31s.push(9);
32console.log(s.peek());   // 9
33console.log(s.pop());    // 9
34console.log(s.size);     // 2

The same shape works in Java with ArrayDeque<T> (the standard recommends it over the legacy java.util.Stack), in Go with a slice and append/slice-trimming, and in Rust with Vec<T> (push/pop already part of the standard library). Stacks are universal.

First Application: Balanced Brackets

The single most common stack interview question, and not by accident—every compiler, JSON parser, XML parser, and IDE bracket-highlighter runs essentially this algorithm. Given a string like (a + [b * {c - d}]), decide whether every opening bracket has a matching closer in the right order.

The insight: the most-recently-opened bracket is the next one that needs to close. That phrase— “most recently opened”—is the LIFO contract in disguise.

pairs[")"] == "("
pairs["]"] == "["
pairs["}"] == "{"

1def is_balanced(expr: str) -> bool:
2    pairs = {")": "(", "]": "[", "}": "{"}
3    openers = set("([{")
4    stack: list = []
5
6    for ch in expr:
7        if ch in openers:
8            stack.append(ch)                    # push opener
9        elif ch in pairs:
10            if not stack or stack[-1] != pairs[ch]:
11                return False                    # mismatch or empty
12            stack.pop()                         # match — remove opener
13    return not stack                            # all openers consumed?

Two consequences worth carrying forward:

• The stack's height equals the current nesting depth. If you push an opener and pop on a matching closer, the stack's peak height during the walk is the maximum nesting depth of the input. Compilers report this as the “maximum bracket depth” statistic.
• This generalizes. Replace “openers and closers” with “function entry and return” and you have the call stack. Replace it with “BEGIN and END tags” and you have an XML parser. The algorithm is the same; only the alphabet changes.

The Deep Connection to Recursion

Recursion and stacks are the same idea, viewed from two angles. Every recursive function call in any modern programming language pushes a stack frame onto the call stack: the frame holds the function's parameters, locals, and the return address. When the function returns, its frame is popped. The chain of currently-executing functions, from main down to the deepest active call, is literally a stack.

That observation has a stronger form: any recursive algorithm can be rewritten iteratively using an explicit stack, and vice versa. The two are interchangeable in expressive power; they differ only in who manages the stack—the language runtime, or you.

Converting Recursion to Iteration

Pre-order tree traversal is the canonical example. The recursive form:

1def preorder(node):
2    if node is None:
3        return
4    print(node.value)
5    preorder(node.left)
6    preorder(node.right)

becomes, with an explicit stack:

1def preorder_iter(root):
2    if root is None:
3        return
4    stack = [root]
5    while stack:
6        node = stack.pop()
7        print(node.value)
8        # Push right FIRST so left is processed next (LIFO)
9        if node.right is not None: stack.append(node.right)
10        if node.left  is not None: stack.append(node.left)

Where Stacks Live in Real Systems

Stacks are everywhere—often invisibly. Once you know to look, you stop seeing applications and start seeing stacks-in-disguise.

Two observations from this list. First, hardware-level stacks predate software-level ones: the CPU stack pointer is older than most programming languages, and the entire calling convention of every modern operating system is built on it. Second, “stack-based” languages like PostScript and Forth show that you can build an entire programming model around the structure—not just use it as an internal data structure.

When NOT to Use a Stack

The LIFO discipline is a feature when you need it and a straitjacket when you don't. Reach for something else when:

• You need fairness or first-come-first-served ordering. Print queues, request queues, BFS—these are FIFO and want a queue (Chapter 8).
• You need random access by index. Use an array. arr[k] is $O(1)$; reaching the $k$-th-from-top element of a stack is $O(k)$ and destroys the stack to do it.
• You need to retrieve the smallest/largest element. Use a heap / priority queue (Chapter 14). A stack returns the most-recently-pushed element regardless of value.
• You need fast membership checks. x in stack is $O(n)$. Use a set or hash table.
• The access pattern is unconstrained. If you genuinely need to read or modify any element on demand, you're reaching for a list, deque, or array, and the stack discipline buys you nothing.

Pitfalls and Edge Cases

• pop on empty. Pick a policy and document it: raise (Python list, Java Deque), return a sentinel like None / undefined (JS Array, Go slice trim), or return an Option/Maybe (Rust, Haskell). The wrong choice is silently doing nothing—that hides bugs.
• Stack overflow from deep recursion. A program that recurses 100,000 levels deep on a tree will crash with stack overflow on Linux's default 8 MB stack (~250 KB/frame for Python). Three fixes, in order of preference: (1) iterate, (2) use an explicit stack, (3) raise the OS limit with sys.setrecursionlimit / ulimit -s unlimited.
• Bounded stacks must check for overflow. Embedded code often uses a fixed-size array stack: int stk[64]. Pushing the 65th element silently corrupts adjacent memory unless you guard with if (top >= 64) error().
• Do not iterate a stack non-destructively in client code. Looping while not s.is_empty(): print(s.pop()) drains the stack as a side effect of printing. If you needed it intact, you've lost it. Either expose a debug-only iterator on the implementation, or copy first.
• Concurrent access. A naive Python or C stack is not thread-safe. Two threads pushing simultaneously can write the same buffer slot. Wrap with a lock, or use a concurrent data structure like Java's ConcurrentLinkedDeque.

Quick Checks

With the abstraction nailed down, the next step is concrete: how do we actually build this thing? Section 7.2 implements the stack two ways—over a dynamic array and over a singly linked list—and compares the constants, the failure modes, and the cache behavior. Section 7.3 pulls back the curtain on the call stack itself, and from there the remaining sections turn the stack loose on expression evaluation, parentheses checking, monotonic-stack tricks, and the algorithms that hide a stack inside their state.