Stacks

What this chapter covers

A stack is the first structure in this book defined by what it won't let you do. It's a collection where you can only touch one end — you add to the top, you take from the top, and you can't reach anything underneath. That sounds like a limitation, and it is, on purpose: the restriction is exactly the shape of every problem that has to unwind in reverse order. This chapter builds a stack on top of the dynamic array from the last chapter, then uses it for the problem stacks were practically invented for — checking that brackets are matched.

A bit of history

The stack is one of the oldest control structures in computing. Alan Turing described the mechanism in 1946 for handling subroutine returns — his words for push and pop were "bury" and "unbury," which is a better mental image than the modern names. The structure was formalized and patented as a principle in 1957 by Friedrich Bauer and Klaus Samelson, who called it the Kellerprinzip (the "cellar principle") and used it to evaluate arithmetic expressions with nested parentheses — the exact problem in this chapter's animation. Their stack-based expression evaluation is still how compilers and calculators parse math today.

The intuition

Think of a stack of plates. You add a plate to the top; you take a plate from the top; you never pull one from the middle. The last plate you put down is the first one you pick up — last in, first out.

That single rule is what makes the stack useful. Any time you're in the middle of one thing and have to pause for a more urgent thing, finishing the newest first and coming back to the older ones, you're describing a stack. A function that calls another function, which calls another — each has to finish and return before the one that called it resumes. Opening brackets that each have to be closed before the ones around them. An undo history where Ctrl-Z reverses your most recent action first. All of these are stacks, whether or not anyone named them.

Complexity: how it scales

A stack is cheap because every operation happens at one known end. Building it on a dynamic array, push is an append and pop is a remove-from-the-end — both $O(1)$ (amortized for push, because of the array's occasional resize from the last chapter). Peek is a single read, $O(1)$. There's no searching and no shifting, ever. Space is $O(n)$ for n items.

There's no recurrence to unfold here — the interesting thing is that the cost doesn't grow. The chart below runs a long sequence of push/pop operations and times it; the line is straight, which means the per-operation cost is flat no matter how deep the stack gets:

What it's good at, what it isn't

A stack is the right tool whenever your access pattern is "most recent first" and you never need to reach past the top. Because every operation is a guaranteed $O(1)$ touch at one end, it's about as fast as a data structure gets, and the LIFO discipline makes code that uses it easy to reason about — you always know exactly which item comes out next.

What it isn't is a general container. You can't ask for the oldest item, or the third-from-top, or search it, without violating the very restriction that makes it a stack. If you find yourself wanting those, you've outgrown the stack and want a different structure — a queue for oldest-first, an array for indexing. And the two operations that can fail — popping or peeking an empty stack — will fail, so code that uses a stack has to check.

The data, or the inputs

Two kinds of input drive this chapter. The face-off feeds the stack a long, randomly generated sequence of valid push and pop operations — valid meaning it never pops below empty — so we can time it at scale. The animation uses a single short string of brackets, ([{}]), because the point there isn't speed, it's watching the stack grow and shrink as the scan matches each pair.

Build it, one function at a time

Push adds to the top, which on a dynamic-array backing store is just an append:

def push(self, value):
    """O(1) amortized: add to the top (the end of the backing array)."""
    self._items.append(value)

Pop removes and returns the top, and refuses to run on an empty stack — there's nothing to give back:

def pop(self):
    """O(1): remove and return the top. Errors on an empty stack — there's
    nothing to take."""
    if not self._items:
        raise IndexError("pop from empty stack")
    return self._items.pop()

Peek is the same look at the top without taking it, for when you need to inspect before deciding:

def peek(self):
    """O(1): read the top without removing it."""
    if not self._items:
        raise IndexError("peek at empty stack")
    return self._items[-1]

With those three, the bracket matcher writes itself. Push every opening bracket; on a closing bracket, the top of the stack must be its partner, so pop it. If the top is the wrong bracket, or the stack is empty when a close arrives, the string is unbalanced. It's balanced only if every close matched and the stack is empty at the end:

_PARTNER = {")": "(", "]": "[", "}": "{"}

def is_balanced(text, probe=None):
    """Are the brackets in `text` correctly nested and matched?

    The canonical stack problem. Push every opening bracket; on a closing
    bracket the top of the stack must be its partner, so pop it. The string is
    balanced iff every close finds its match and the stack is empty at the end —
    an unmatched open left on the stack means something never closed. Each step
    is appended to `probe` (when given) so the scan can be animated.
    """
    stack = Stack()
    for ch in text:
        if ch in "([{":
            stack.push(ch)
            action = f"'{ch}' opens — push it"
        elif ch in ")]}":
            if stack.is_empty() or stack.peek() != _PARTNER[ch]:
                if probe is not None:
                    probe.append({"stack": stack.snapshot(), "action": f"'{ch}' has no match — not balanced"})
                return False
            stack.pop()
            action = f"'{ch}' closes the top — pop it"
        else:
            action = f"'{ch}' is not a bracket — skip"
        if probe is not None:
            probe.append({"stack": stack.snapshot(), "action": action})
    return stack.is_empty()

Watch it work

Here's the matcher running on ([{}]). The top row is the input string with a cursor; the bottom row is the stack. Step through it: each opening bracket gets pushed (the stack grows), and each closing bracket pops the matching open off the top (the stack shrinks). The green cell is the top of the stack — the one a closing bracket has to match. By the last character the stack is empty, which is what "balanced" means. It took six steps and the stack never got deeper than three:

The complete code

Both versions in one place — flip between them. The from-scratch tab is our Stack plus the bracket matcher. The library tab is what you'd actually write: a Python list is already a stack (append is push, pop() is pop), and collections.deque is the same when you want to make the intent explicit.

"""A stack — last in, first out — built on a dynamic array, plus the classic
application that shows why stacks exist: matching nested brackets.

A stack only lets you touch one end. That restriction is the point: it's exactly
the right shape for anything that has to unwind in reverse order — undo history,
a function-call chain, the open brackets waiting to be closed.
"""


class Stack:
    def __init__(self):
        self._items = []          # a Python list used as the backing array

    # region: push
    def push(self, value):
        """O(1) amortized: add to the top (the end of the backing array)."""
        self._items.append(value)
    # endregion

    # region: pop
    def pop(self):
        """O(1): remove and return the top. Errors on an empty stack — there's
        nothing to take."""
        if not self._items:
            raise IndexError("pop from empty stack")
        return self._items.pop()
    # endregion

    # region: peek
    def peek(self):
        """O(1): read the top without removing it."""
        if not self._items:
            raise IndexError("peek at empty stack")
        return self._items[-1]
    # endregion

    def is_empty(self):
        return not self._items

    def __len__(self):
        return len(self._items)

    def snapshot(self):
        """Bottom-to-top copy of the contents — used to record the animation."""
        return list(self._items)


# region: balanced
_PARTNER = {")": "(", "]": "[", "}": "{"}

def is_balanced(text, probe=None):
    """Are the brackets in `text` correctly nested and matched?

    The canonical stack problem. Push every opening bracket; on a closing
    bracket the top of the stack must be its partner, so pop it. The string is
    balanced iff every close finds its match and the stack is empty at the end —
    an unmatched open left on the stack means something never closed. Each step
    is appended to `probe` (when given) so the scan can be animated.
    """
    stack = Stack()
    for ch in text:
        if ch in "([{":
            stack.push(ch)
            action = f"'{ch}' opens — push it"
        elif ch in ")]}":
            if stack.is_empty() or stack.peek() != _PARTNER[ch]:
                if probe is not None:
                    probe.append({"stack": stack.snapshot(), "action": f"'{ch}' has no match — not balanced"})
                return False
            stack.pop()
            action = f"'{ch}' closes the top — pop it"
        else:
            action = f"'{ch}' is not a bracket — skip"
        if probe is not None:
            probe.append({"stack": stack.snapshot(), "action": action})
    return stack.is_empty()
# endregion

"""A Python list is already a stack: `append` is push, `pop()` is pop, both O(1)
amortized at the end. When you want to make the intent explicit, `collections.deque`
is the other common choice — same O(1) at the end, and it can't be indexed into by
accident the way a list can.

So the face-off is our Stack against the two structures every Python programmer
actually reaches for, driven by the same sequence of push/pop operations.
"""
from collections import deque


# region: list_stack
def run_ops_list(ops):
    """Drive ('push', x) / ('pop',) operations on a plain list used as a stack."""
    stack = []
    popped = []
    for op in ops:
        if op[0] == "push":
            stack.append(op[1])
        else:
            popped.append(stack.pop())
    return popped
# endregion


# region: deque_stack
def run_ops_deque(ops):
    """Same operations on a deque — append/pop work on the right end."""
    stack = deque()
    popped = []
    for op in ops:
        if op[0] == "push":
            stack.append(op[1])
        else:
            popped.append(stack.pop())
    return popped
# endregion

Scratch vs library

Same structure, same O(1) operations, so the face-off is purely about the constant. The chart runs the identical push/pop sequence through our Stack, a list, and a deque:

All three lines are straight — every implementation is O(1) per operation, so the total is linear in the number of operations. At 400000 operations our Stack took about 14.4 ms against the list's 8.3 ms, roughly 1.7 times slower. That's a small gap, and it's the whole story: our Stack is a thin Python wrapper whose push calls list.append underneath, so it can only ever be a constant factor behind the raw list — the extra method call. This is why nobody writes a Stack class in Python: the built-in list already is one. The reason to build it is to see that "stack" is a set of promises about access order, not a new kind of storage.

Where you'll actually meet it

Stacks are everywhere once you know the shape. Every undo/redo feature is two stacks. Every compiler and calculator uses one to evaluate expressions and match brackets — the exact code above, scaled up. The back button in your browser is a stack of pages. Depth-first search, in the graph chapters, is breadth-first search with the queue swapped for a stack. And the call stack runs every program you've ever written. When you see "most recent first," or "unwind in reverse," or "balanced nesting," reach for a stack.

Takeaways

A stack is a collection restricted to one end: push, pop, and peek, all $O(1)$, all LIFO. That restriction isn't a weakness — it's a guarantee, and the guarantee is exactly what "handle the newest thing first, then unwind" problems need. Build it on a dynamic array and it inherits O(1) amortized append; in Python the list already gives you all of it.

Keep the shape in mind, because the next two chapters are its mirror image. A queue is the same idea with the opposite ordering — first in, first out, for when you need the oldest item next — and a stack plus a queue covers most of the "process things in a specific order" work you'll ever do. After that, the stack comes back as the engine behind recursion and depth-first search.