vault

Stack

13 min read

Stack

A stack is a linear collection that grants access to only its most recently inserted element. Insertion (push) and removal (pop) both happen at the same end — conventionally called the top — and run in O(1) time. The discipline is LIFO: Last In, First Out, the inverse of a Queue. Stacks are the data-structure twin of recursion: every recursive algorithm can be rewritten with an explicit stack, and the language runtime itself uses one (the call stack) to manage function invocations. They are the right primitive whenever you need to remember the path back — balanced parentheses, expression evaluation, Depth-First Search, backtracking, and undo/redo all reduce to “push when you go in, pop when you come out.”

1. Intuition — The Cafeteria Tray Dispenser

Imagine the spring-loaded tray dispenser at a cafeteria. Clean trays are placed on top, pushing the column down; diners take trays from the top, releasing the spring up by one. The tray you put down most recently is the next one taken. Nobody reaches in to extract a tray from the middle — the dispenser physically prevents it. A stack is exactly that mechanism, abstracted: a vertical pile in which only the topmost item is accessible.

A second analogy useful for software contexts: the call stack. When function f calls g, the runtime pushes a stack frame for g on top of f’s frame; when g returns, its frame is popped and control resumes in f exactly where it left off. The “where it left off” — the return address, local variables, parameters — is precisely the state that needs to be set aside while a deeper computation runs and restored afterward. LIFO order is mandatory: you can only return to f after every function g called has itself returned, recursively.

The deep reason stacks appear so often: anytime you are exploring a structure with the option to back out — a maze, a syntax tree, a partial solution — you need to remember the choices you made on the way in so you can undo them on the way out. The most-recent choice is always the one to undo first. That is LIFO.

2. Tiny Worked Example — Balanced Parentheses

Given the string "({[]})", decide whether all brackets match. The stack-based solution:

StepcharStack (top right)Action
0([(]push opener
1{[(, {]push opener
2[[(, {, []push opener
3][(, {]top is [, matches ] → pop
4}[(]top is {, matches } → pop
5)[]top is (, matches ) → pop
end—emptybalanced ✅

The stack at any moment holds the currently open brackets in the order they were seen. A closer must match the most recently opened opener (top of stack); otherwise the string is malformed. "([)]" would fail at step 2 because the top is ( but the closer ) does not match the unmatched-yet [ underneath, and the algorithm pops ( while leaving [ orphaned — hence rejected.

This problem captures the essence of a stack: nested structure, where the innermost-opened thing must be the first thing closed.

3. Pseudocode

Stack ADT:
    push(x):       insert x on top              O(1)
    pop():         remove and return top         O(1), undefined if empty
    peek()/top():  return top without removing   O(1)
    is_empty():    true iff size == 0            O(1)
    size():        number of elements            O(1)

The minimal contract is push, pop, peek, is_empty. Everything else (search, iteration) is either an extension or breaks the abstraction.

4. Python Implementations

4.1 Idiomatic — Use a list

Python’s built-in list already supports stack operations with the right asymptotic behavior:

stack: list[int] = []
stack.append(3)        # push
stack.append(7)
stack.append(1)
top = stack[-1]        # peek → 1
x = stack.pop()        # pop → 1
empty = not stack      # is_empty → False

list.append and list.pop() (no index, so the default is the last element) are both amortized O(1). The amortized argument: the underlying CPython list is a dynamic array; when capacity is exceeded, it grows by a geometric factor (roughly 1.125× plus a constant — see CPython Objects/listobject.c for the exact growth law). Across any sequence of n pushes, the total reallocation work is O(n), so the cost amortizes to O(1) per push. Pops never reallocate downward in CPython by default (lists keep the over-allocated buffer until they’re shrunk explicitly), so pop() is true O(1).

The crucial detail is that list.pop() with no arguments is O(1) (removing the last element). list.pop(0) — removing the first — is O(n) because every other element must shift down. Stacks pop from the top, which is the end of a Python list, so the natural mapping is correct. This is the opposite of Queue, where the wrong end is the cheap one and you should use collections.deque instead.

4.2 Class Wrapper

When you want explicit push/pop/peek/is_empty API instead of relying on list conventions:

from typing import Generic, TypeVar
T = TypeVar("T")
 
class Stack(Generic[T]):
    def __init__(self) -> None:
        self._data: list[T] = []
 
    def push(self, x: T) -> None:
        self._data.append(x)
 
    def pop(self) -> T:
        if not self._data:
            raise IndexError("pop from empty stack")
        return self._data.pop()
 
    def peek(self) -> T:
        if not self._data:
            raise IndexError("peek on empty stack")
        return self._data[-1]
 
    def is_empty(self) -> bool:
        return not self._data
 
    def __len__(self) -> int:
        return len(self._data)

The class form is preferable in interview settings when you want the reader to see at a glance that you intend stack semantics — calling append/pop directly on a list is correct but obscures intent.

4.3 Thread-Safe — queue.LifoQueue

For multi-threaded producer/consumer scenarios, queue.LifoQueue provides a thread-safe LIFO with put/get semantics. The thread-safety is paid for in lock acquisition overhead, so don’t reach for it unless you actually have multiple threads.

4.4 Other Languages — Quick Reference

  • Java: ArrayDeque<T> is the official recommendation over the legacy Stack class. Use push, pop, peek. Stack<T> extends Vector<T> and is synchronized — slow and discouraged.
  • C++: std::stack<T> is a container adaptor. By default it sits on top of std::deque<T>; you can swap in std::vector<T> for cache-friendlier behavior at the cost of pointer stability.
  • Go: no built-in; idiom is a slice — s = append(s, x); top := s[len(s)-1]; s = s[:len(s)-1].

5. Implementations Under the Hood

5.1 Dynamic Array Backing (Python list, Java ArrayDeque, C++ vector)

Stores elements in a contiguous buffer; push writes to index size++, pop reads index --size. Geometric growth on overflow gives amortized O(1) push.

Pros. Excellent cache locality (adjacent pushes hit adjacent cache lines), low constant factors, minimal allocator pressure.

Cons. Occasional O(n) cost when the buffer is grown and copied. If pointer/reference stability is required (you need pointers to existing elements to remain valid across pushes), arrays violate it because growth relocates everything.

5.2 Linked List Backing

Each node holds a value and a next pointer to the previous top. push allocates a node and links it; pop unlinks the head and frees it. All operations are exactly O(1) — no amortization fudge.

Pros. Pointer stability — references to existing elements remain valid forever. Useful in functional/persistent contexts.

Cons. Allocator pressure (one allocation per push, one free per pop), worse cache locality (nodes scatter across the heap), per-node memory overhead (the next pointer plus allocation header — often 16–24 bytes per element on 64-bit systems for a tiny payload). In benchmarks, array-backed stacks routinely beat linked-list stacks by 5–10× on modern hardware because cache misses dominate over allocation cost in tight loops.

The takeaway: prefer the array-backed implementation by default. Reach for the linked-list version only when pointer stability matters or in immutable/persistent data structure contexts.

6. Complexity

OperationArray-backedLinked-list-backed
pushO(1) amortizedO(1) worst-case
popO(1)O(1)
peekO(1)O(1)
is_emptyO(1)O(1)

Space: O(n) for n elements stored, plus O(n) constant overhead in the linked-list case for next pointers.

The amortized-vs-worst-case distinction matters in real-time systems where any single operation must finish in bounded time (no growth-induced O(n) hiccup allowed). For interview problems and ordinary application code, amortized O(1) is what you want.

7. Use Cases

7.1 Function Call Stack

Every call/return in an imperative language pushes/pops a stack frame — return address, saved registers, local variables. Stack overflow is what happens when recursion (or unbounded local allocation) blows past the OS-allotted call-stack region (typically 1–8 MiB depending on platform and configuration).

7.2 Recursion-to-Iteration Conversion

The “every recursive algorithm can be rewritten with an explicit stack” claim is precise: any recursive function can be transformed into an iterative loop maintaining a manually-managed stack of continuations (the work remaining at each level). This is essential when:

  • The implicit call stack would overflow (deep recursion, e.g., a 10⁶-node degenerate tree).
  • You want an iterative DFS for fine-grained control.
  • You’re emitting bytecode for a stack-based VM (JVM, .NET CLR, WebAssembly all evaluate expressions on a stack).

7.3 Expression Evaluation — Shunting-Yard, RPN

Edsger Dijkstra’s shunting-yard algorithm (1961) converts infix arithmetic (3 + 4 * 2) to postfix Reverse Polish Notation (3 4 2 * +) using two stacks: an operator stack and an output queue. Postfix expressions are then evaluated by a single stack: push numbers, on operator pop two operands and push the result. LeetCode 224 (Basic Calculator), LC 227, LC 772, LC 150 all variants of this pattern.

Depth-First Search is the stack-driven graph traversal. Recursive DFS uses the call stack implicitly; iterative DFS uses an explicit stack of nodes (or, more precisely, of frontier states). The LIFO order is what creates the “go deep before going wide” behavior — push a node’s neighbors and pop the most-recently-pushed first, which is the deeper path.

7.5 Backtracking

Generic backtracking algorithms (N-Queens, subset enumeration, Sudoku solver) push the current partial solution onto a stack, recurse, and pop on failure. The stack is the trail of choices to undo.

7.6 Undo/Redo

Text editors and command-pattern UIs maintain two stacks: an undo stack of past operations and a redo stack for operations that were undone. Issuing a new command pushes onto undo; pressing Ctrl-Z pops from undo and pushes onto redo; Ctrl-Y pops from redo back to undo. Issuing a new command after some undos clears the redo stack — capturing the “branch divergence” of editing history.

7.7 Browser Back Button

Each visited URL pushes onto a stack; “Back” pops. Forward maintains the parallel stack. Same dual-stack pattern as undo/redo.

7.8 Monotonic Stacks — A Specialized Pattern

A Monotonic Stack maintains elements in monotonically increasing or decreasing order, popping when a new element would violate the invariant. Used for “next greater element” / “next smaller element” problems and the histogram-largest-rectangle classic. See its dedicated note.

7.9 Min Stack

A stack that also supports getMin() in O(1). Implemented either by augmenting each frame with the running minimum, or with a parallel auxiliary stack that records minima. LeetCode 155 is the canonical problem.

8. Pitfalls

8.1 Confusing Stack with Queue

LIFO vs FIFO is a one-bit decision but determines algorithm behavior. DFS uses a stack; Breadth-First Search uses a Queue. Swapping them silently gives a different traversal — sometimes correct, often not, and easy to miss because the data structure interfaces look similar.

8.2 Empty-Stack Peek/Pop

pop() and peek() on an empty stack are undefined; in most languages they raise (IndexError in Python, EmptyStackException in Java). Always guard with if stack: (Python truthiness on lists is False for empty, True otherwise) or maintain an explicit invariant.

8.3 Stack Overflow in Recursive Algorithms

Python’s default recursion limit is 1000 (raise via sys.setrecursionlimit, but this only changes the Python-level limit — the C stack still has its own). On highly skewed inputs (a 10⁶-node linked list represented as a tree), recursive tree traversal will overflow. Convert to an explicit stack to handle large inputs.

8.4 Using list.pop(0) When You Meant a Stack

list.pop() (no argument) is O(1) — correct for stack. list.pop(0) is O(n) — that would be queue dequeue, and even there it’s the wrong tool (use collections.deque). Don’t write pop(0) thinking it’s symmetric with pop(); it isn’t.

8.5 Mutating While Iterating

Iterating a stack typically means popping until empty. If you for x in stack: stack.pop() you’ll get either silent skips, exceptions, or undefined behavior depending on language. Always use a while not stack.is_empty(): loop.

8.6 Forgetting That Stack<T> in Java Is Synchronized

java.util.Stack (the legacy class) extends Vector and synchronizes every method, paying lock overhead even in single-threaded code. Use ArrayDeque instead, which the Oracle documentation explicitly recommends.

8.7 Misjudging “Stackness”

Some problems seem stack-shaped (you process the input left to right and want to look back) but are actually Sliding Window or Two Pointers problems in disguise. The signature for stack: you need the most recent unfinished work, possibly going arbitrarily deep. The signature for sliding window: you need a contiguous range and the boundaries move only forward.

9. Diagram — Push and Pop Trace

flowchart TD
    A["empty\n[]"] -->|push 3| B["[3]"]
    B -->|push 7| C["[3, 7]"]
    C -->|push 1| D["[3, 7, 1]\n← top"]
    D -->|pop → 1| E["[3, 7]\n← top"]
    E -->|peek → 7| F["[3, 7]\n← top"]
    F -->|pop → 7| G["[3]\n← top"]
    G -->|pop → 3| H["empty\n[]"]

What this diagram shows. A linear timeline of stack states under the operation sequence push 3, push 7, push 1, pop, peek, pop, pop. Each box labels the stack contents with the rightmost element being the top. Notice that the values come out in the reverse order they went in — 1 first, then 7, then 3 — which is precisely the LIFO property. The peek between two pops returns the current top without changing the stack: peek is non-destructive, pop is destructive.

10. Common Interview Problems

#ProblemStack Role
LC 20Valid ParenthesesMatch opener/closer pairs
LC 155Min StackAugmented stack with O(1) min
LC 224Basic CalculatorOperator/operand stacks for infix eval
LC 227Basic Calculator IISingle-stack precedence trick
LC 232Implement Queue using StacksTwo stacks emulate FIFO
LC 150Evaluate Reverse Polish NotationSingle-stack postfix eval
LC 71Simplify PathStack of path components, .. pops
LC 394Decode StringNested encoding, push count + builder
LC 1003Check Valid String After SubstitutionsStack of insertion sites
LC 84Largest Rectangle in HistogramMonotonic Stack (dedicated note)
LC 42Trapping Rain WaterMonotonic Stack
LC 739Daily TemperaturesMonotonic Stack
LC 856Score of ParenthesesStack of scores
LC 173BST IteratorStack-based in-order traversal

11. Open Questions

  • Are there practical persistent (immutable) stack libraries in Python beyond toy implementations? Cons-list semantics work, but performance at scale?
  • In real allocators, how much does the per-node header cost dominate linked-list-stack performance vs the array-backed alternative? The numbers vary across jemalloc, mimalloc, and glibc malloc.
  • When does the synchronized java.util.Stack performance hit actually matter for typical applications? Microbenchmarks suggest 5–10× overhead, but real applications usually have other bottlenecks.

12. See Also

Graph View

Backlinks