51The stack — last in, first out

In Chapter 50 we strung data together with pointers. Every node reached across the heap to the next, so the list could grow wherever memory had room. Here we do almost the opposite. We take one plain list, hold it to a single promise, and out falls the most useful container in all of computing. A stack is the simplest deal you can strike with memory. You agree to add and remove items at one end only, the top, so the last thing in is the first thing out. Here's the plan. We'll watch that one rule, Last In, First Out, and make push, pop, and peek all cost O(1). Then we'll find the exact same shape hiding under function calls, undo, the browser Back button, and matching brackets. The whole way through we keep asking the one question that matters. When is the next thing I need always the thing I added most recently? By the end you'll see the stack that runs underneath every program you've ever written. You'll write a bracket-matcher from scratch, and recognise a LIFO access pattern on sight.

01One end, and the world's simplest rule

Let's start with something you've physically used a hundred times: a spring-loaded stack of cafeteria trays. You can do exactly two things with it — drop a tray on top, or lift the top tray off. You can't slide one out of the middle, and you can't reach the bottom tray until every tray above it is gone. Watch what that one constraint forces: whatever went on last comes off first. That's the whole idea, and it has a name. We call it LIFO, for Last In, First Out. The tray you can currently touch is the top. Adding a tray is push, taking the top one off is pop, and looking at the top without removing it is peek.

Watch the reversal happen with real values. Say you push three browser pages in order: the search results, then an article, then a photo. The photo went on last, so it sits on top. Hit Back once and you pop the photo, landing back on the article. Hit Back again and you pop the article, landing back on the search results. The pages come off in the exact reverse of the order they went on. That mirror-image order is the whole personality of a stack, and it falls straight out of touching one end only. Nothing else about the trays or the pages matters.

This reversal isn't just a side effect — it's a tool you'll reach for on purpose. Feed a stack the letters of 'cat' one at a time, and it holds c, then a, then t, with t on top. Now empty it: pop hands back t, then a, then c, spelling 'tac'. Push a sequence in, pop it back out, and it comes out reversed every single time, with no extra bookkeeping. That falls straight out of Last In, First Out, and it's why a stack is the natural tool whenever the order you need is the order you saw things, backwards.

Now the memory picture — because here's the surprise: a stack is not some exotic new object. You already own it. A Python list, as we saw back in Volume 1, is a contiguous block of 8-byte references with some spare slots on the end (Vol 1, ch 6). A stack is just that list with a promise: I will only ever touch the far end. Push is append; pop is .pop(); peek is a[-1]. There's no separate "top pointer" stored anywhere — CPython keeps the list's length in its header, so the top is simply the last index, len − 1. Let's look at the block sitting in RAM before we touch a single line of code.

What does one item cost? I measured it on CPython 3.12. An empty list is 56 bytes, a bare header with no data block yet. A list of a million integers is 8,000,056 bytes. That works out to almost exactly 8 bytes per element. The block stores only the reference, and the integer object it points at lives elsewhere on the heap. A stack is therefore about as light as a container gets: 8 bytes of "plumbing" per item, plus a little overallocated slack on the end.

Let's check that 8 bytes is exact, not just close. Take the million-integer list at 8,000,056 bytes and subtract the 56-byte header: that leaves 8,000,000 bytes of pure data block. Divide by the 1,000,000 references it holds and you land on exactly 8 bytes each — one 64-bit pointer per slot, not a byte more. The header is a fixed toll you pay once, and every element after it costs the same flat 8 bytes of plumbing. That predictable per-item cost is a big part of why a stack is so easy to reason about.

Here's what that 8 bytes per element really buys you. The slot never holds the item itself. It holds an address, a pointer to where the real object lives on the heap. Push the integer 42 and the slot holds its address. Push the string 'titanium' and the slot holds an address too, the same 8 bytes, even though the string itself is far larger. So a stack of a million tiny numbers and a stack of a million long strings have the same block size. The weight of the values always lives elsewhere. The stack itself only ever pays for the plumbing.

If only the top ever moves, how expensive can any operation possibly be? Let's derive the cost from the layout instead of taking it on faith. →

02Why push, pop, and peek are all O(1)

Reason straight from the block. To push, CPython looks at the length, finds the next free slot right after the last item, writes one reference into it, and bumps the length by one. It does not look at slot 0, or slot 3, or the million items underneath. It touches exactly one cell. Work that stays the same no matter how big the stack is means O(1). To pop, it reads the top cell, hands the reference back, and drops the length by one. That is again one cell, so O(1). To peek, it reads a[-1] and returns it without changing anything, which is also O(1). Three operations, none of which ever walks the block.

It's worth naming what a stack can't do cheaply, because the speed comes from a real trade. Want the item three down from the top? A stack won't hand it to you without popping the two above it first. Want to search for a value somewhere in the middle? That's a full O(n) walk, no better than any ordinary list. The stack buys its blazing O(1) at the top by giving up cheap access to everything else. That bargain is exactly why you reach for it only when the next thing you need is always the most recent one. Match the structure to the access pattern, and the O(1) is free.

There's a boundary worth meeting head-on: what happens when you pop an empty stack? There's nothing to hand back, so CPython refuses. [].pop() raises IndexError: pop from empty list, and [][-1] raises one too. This is stack underflow, the mirror image of the overflow we'll meet later. So a careful stack routine asks is there anything here? before it reaches for the top. Keep that check in mind — it's exactly the not stack guard we lean on when the bracket-matcher meets a closer with nothing open.

There's one honest wrinkle. Every so often a push finds no free slot left. When that happens, CPython allocates a bigger block and copies the references over. That single push is O(n). But it happens rarely, and the growth is geometric. So if you average the cost over many pushes, it comes out to a constant. This is amortized O(1) (Vol 3, ch 3), the same accounting that makes list.append cheap. I watched the block grow in jumps. Pushing onto a fresh list, getsizeof stepped 56 → 88 → 120 → 184 → 248 → 312 → 376…, reallocating at sizes 1, 5, 9, 17, 25, 33. That is a handful of copies across dozens of pushes, each copy buying room for the next batch.

Let me show you why the average holds, because "it works out to a constant" sounds like hand-waving until you count it. Take the simplest growth to reason about: the block doubles each time it fills, making room for 1, then 2, then 4, then 8, on up to n. The copies you pay for across all those reallocations are 1 + 2 + 4 + … + n. That sum is always a little under 2n, because the final doubling alone copies more than everything before it combined. So across n pushes you copy fewer than 2n references in total. Spread over those n pushes, that is under 2 copies each, a flat constant. CPython actually grows by a smaller factor than doubling, but any fixed growth ratio gives the same constant average. That is what amortized O(1) really means.

Put a number on it. Say the stack grows to hold 8 items. Doubling from a single slot, the block reallocates at capacities 1, 2, 4, and 8, copying 1, then 2, then 4, then 8 references along the way. Add those up: 1 + 2 + 4 + 8 = 15, a hair under 2 × 8 = 16. And notice the last copy of 8 alone outweighs the 7 copies before it combined. That's the whole trick — the newest, biggest copy dominates the bill, so the running total stays pinned under 2n no matter how large n grows.

stack = []
stack.append('do')      # push   O(1)  -> ['do']
stack.append('re')      # push   O(1)  -> ['do', 're']
stack.append('mi')      # push   O(1)  -> ['do', 're', 'mi']
top = stack[-1]         # peek   O(1)  -> 'mi'   (stack unchanged)
gone = stack.pop()      # pop    O(1)  -> 'mi'   (stack is ['do', 're'])

Line by line: three appends push onto the far end, each dropping a reference into the next slot. Then stack[-1] peeks, reading the top without disturbing it, so the list still holds all three items. Next, stack.pop() removes and returns the top, 'mi', so the last thing pushed is the first thing out — LIFO made literal. Timed at a million operations each, a push averaged about 26 nanoseconds and a pop about 24 nanoseconds on my machine. Wall-clock time varies by hardware, but the point holds either way: neither grows with the stack's size.

So a stack is a list you agreed to touch at one end. But hold on — Python never made you declare a "Stack". Where is the stack, exactly? →

03A stack is not a type — it's a discipline

Here is the reframe that trips almost everyone up. In many languages a stack is a class you import and instantiate, but in Python a stack is not a data type at all. It's a rule you impose on a list. The moment you promise yourself "I will only ever append and pop(), never index into the middle, never pop(0)," that ordinary list is a stack. The structure isn't in the object. It's in the discipline, and nothing in the runtime enforces it. The LIFO-ness is a contract you keep with yourself, and its whole payoff is that every operation stays O(1) and the code reads as "a stack."

INPUTstack = []
stack.append('do')                 # push
stack.append('re')
stack.append('mi')
print(stack, "top =", stack[-1])   # peek: reads, never removes
print("pop ->", stack.pop(), "| now", stack)
print("pop ->", stack.pop(), "| now", stack)
print("pop ->", stack.pop(), "| now", stack)
print("empty?", not stack)
try:
    stack[-1]
except IndexError as e:
    print("peek on empty:", type(e).__name__ + ":", e)
try:
    stack.pop()
except IndexError as e:
    print("pop  on empty:", type(e).__name__ + ":", e)

OUTPUT['do', 're', 'mi'] top = mi
pop -> mi | now ['do', 're']
pop -> re | now ['do']
pop -> do | now []
empty? True
peek on empty: IndexError: list index out of range
pop  on empty: IndexError: pop from empty list

You do have choices for the backing, and they matter for reasons Volume 3 made physical. A list keeps its references contiguous. So a run of pushes and pops streams through the same cache lines, and the CPU prefetcher loves it. The textbook alternative is a linked stack: one small node per item, each holding a value and a next pointer. To push you make a node and point it at the old top. To pop you follow next. This is correct and also O(1). But every node is a separate heap allocation scattered across RAM. So pushing and popping means allocation plus pointer-chasing, and each hop risks a cache miss (Vol 3, ch 2). I measured the gap. Pushing and popping 2,000,000 items took about 0.20 s on a list versus 0.88 s on a node-per-item stack. That is the same Big-O, but roughly 4× slower on the metal. The node is heavier too. A minimal two-field node with __slots__ is 48 bytes each, ballooning to ~344 bytes if it carries an ordinary __dict__. Compare that to the list's flat 8 bytes per item.

So when does the linked stack ever earn its keep? Two honest cases. First, it never needs one giant contiguous block, and it never pays that rare O(n) copy on growth, so every push is a flat, spike-free O(1). That matters in a hard real-time system, where a single reallocation pause could blow a deadline. Second, because pushing only adds a node and never disturbs the old ones, several versions of the stack can share the same tail — the basis of the persistent, immutable stacks functional languages lean on. Outside those two cases, reach for the list.

You've been imposing this discipline by hand. Now meet the stack you never declared — the one the interpreter has been running under your feet this whole time. →

04The stack you're already standing on

Every time one function calls another, the machine has to remember two things: where to come back to, and what the caller's local variables were. It stores that in a frame, a little record holding a call's local names and its return address (Vol 1, ch 9). And it keeps those frames in exactly one arrangement: a stack. When a calls b calls c, three frames are pushed. When c returns, its frame is popped and control resumes in b. It must be LIFO, because the function that started most recently is the one that has to finish first before its caller can continue. This is the call stack, and it is the most important stack you will ever use. You use it in every program without ever typing push.

Make it concrete with a number: call factorial(3). It needs factorial(2), which needs factorial(1), so three frames push on top of each other, the deepest call on top. Now they unwind. factorial(1) returns 1 and pops, and back in factorial(2) that becomes 2 × 1 = 2, which returns and pops. Back in factorial(3) that becomes 3 × 2 = 6. The frames came off in the exact reverse of the order they went on, and each one waited, half-finished, for the call above it to hand back an answer. Step the walkthrough above and watch the frames stack up and drain.

You can see it directly. CPython links each frame to its caller through f_back, so walking that chain from the running function outward is reading the stack top-to-bottom.

import sys

def show_frames():
    f = sys._getframe()             # the frame running right now (top of the stack)
    names = []
    while f:                        # walk f_back all the way down
        names.append(f.f_code.co_name)
        f = f.f_back                # step to the caller's frame
    print(" -> ".join(names))

def a(): b()
def b(): c()
def c(): show_frames()
a()                                 # show_frames -> c -> b -> a -> <module>

Reading it: sys._getframe() hands back the frame on top, the one for show_frames itself. The while loop follows f_back link by link. Each link is the frame that called this one, so we climb down the stack recording names. The real output was show_frames -> c -> b -> a -> <module>. That is the exact push order read back in reverse, which is what "popping" would give you.

This is also why recursion costs memory and why it can crash. Each recursive call pushes another frame. The frames only start popping when a base case lets calls return. Recur without a base case and you push frames forever, until the stack runs out of room. Python guards against blowing the real, finite C stack underneath by capping its own depth. sys.getrecursionlimit() is 1000 by default, and an unbounded recursion raised RecursionError at a depth of about 999 when I ran it. That crash has a famous name.

The name is stack overflow, the call stack literally overflowing the room reserved for it. It's the same failure a C program hits when infinite recursion runs past the operating system's stack limit, except there the guard is the raw memory page and the program simply segfaults with no explanation. Python's 1000-frame cap is a friendlier fence. It stops you with a clean RecursionError well before the real C stack underneath gives way. And yes, the world's most-visited programming question-and-answer site took its name from exactly this crash. Every engineer meets it eventually, usually the hard way.

You might wonder: can't I just raise the fence? You can — sys.setrecursionlimit(n) lifts the cap to whatever n you name. But be careful, because the 1000 default is deliberately conservative. Python's limit guards the real, finite C stack underneath, and that stack has its own hard ceiling set by the operating system. Set n too high and a deep recursion sails past Python's friendly RecursionError straight into the raw segfault the cap existed to prevent. The honest fix for genuinely deep work is usually to rewrite the recursion as a loop with your own explicit stack.

The call stack matches nested function calls for a living — open a, open b, close b, close a. That's the same shape as nested brackets. Let's make a stack check them by hand. →

05Matching brackets — a stack's party trick

Is ([{}]) balanced? Is ([)]? A human eyes it, but a stack proves it in one pass. The rule that makes brackets legal is simple: the one you opened most recently must be the one you close first, which is LIFO exactly. So scan left to right. Every time you meet an opener, push it. Every time you meet a closer, the thing it must match is whatever sits on top of the stack, so pop the top and check the two are a pair. If they don't match, or the stack is empty when you need something to pop, it's broken. If you reach the end with an empty stack, every opener found its partner and the string is balanced.

def balanced(s):
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for ch in s:
        if ch in '([{':                       # an opener → push it
            stack.append(ch)
        elif ch in ')]}':                      # a closer → the top must be its partner
            if not stack or stack.pop() != pairs[ch]:
                return False                   # nothing to match, or a mismatch
    return not stack                           # balanced only if nothing is left open

for t in ['()', '([])', '([)]', '(((', '{[()]}', '](']:
    print(repr(t), '->', balanced(t))

Walk it: pairs maps each closer to the opener it needs. For an opener we append, which is push. For a closer we check two failure modes at once: not stack (a closer with nothing open) and stack.pop() != pairs[ch] (the most recent opener is the wrong kind). Reach the end and not stack asks "is everything closed?" I ran it, and it returns exactly what your eye does: '()' -> True, '([])' -> True, '([)]' -> False (the ) tries to close a [), '(((' -> False (three left open), '{[()]}' -> True, and ']( ' -> False. Twelve lines, and it's the beating heart of every compiler, JSON parser, and the rainbow-bracket highlighter in your editor.

Trace the tricky one by hand so the machinery is concrete. Take ([)] and scan left to right. The ( is an opener, so push it — the stack is ['(']. The [ is an opener too, so push again — the stack is ['(', '[']. Now comes ), a closer that needs pairs[')'] == '('. We pop the top and out comes '[', not '(' — the innermost open bracket is the wrong kind. Mismatch, so the answer is False, exactly as your eye said. The [ and ) interleave instead of nesting, and the stack catches it the instant they cross.

Notice why the top of the stack is always the bracket that must close next. Each opener you push sits inside all the openers still waiting beneath it, so the most recent one is the innermost one. Innermost must close first, and that is just nesting. Nesting is LIFO wearing different clothes. It's the very same shape as the call stack from two sections back. There, the most recent call had to finish first. Here, the most recent bracket has to close first. Once you spot that a problem has "most recent must resolve first" built into it, you already know the data structure to reach for.

PAIRS = {')': '(', ']': '[', '}': '{'}

def check(s):
    # Return (True, '') or (False, why) - naming WHICH failure and WHERE.
    stack = []                                  # holds (bracket, index)
    for i, ch in enumerate(s):
        if ch in '([{':
            stack.append((ch, i))
        elif ch in ')]}':
            if not stack:                       # failure 1: closed what was never opened
                return False, f"stray {ch!r} at index {i} - nothing was open"
            opener, at = stack.pop()
            if opener != PAIRS[ch]:             # failure 1b: closed the wrong one
                return False, f"{ch!r} at index {i} closes {opener!r} opened at index {at}"
    if stack:                                   # failure 2: ran out of string, not of openers
        opener, at = stack[-1]
        return False, f"{opener!r} at index {at} was never closed"
    return True, "balanced"

for s in ['([{}])', '()', '([)]', '(((', ')(', '{[()]}', '']:
    ok, why = check(s)
    print(f"{s!r:10} {str(ok):5} {why}")

# '([{}])'   True  balanced
# '()'       True  balanced
# '([)]'     False ')' at index 2 closes '[' opened at index 1
# '((('      False '(' at index 2 was never closed
# ')('       False stray ')' at index 0 - nothing was open
# '{[()]}'   True  balanced
# ''         True  balanced

# WHAT THE TUPLE BOUGHT YOU. The bare-character version knew the nesting;
# this one knows the nesting AND the address of every promise still open.
# Read the '(((' line: it reports index 2, the LAST opener, because that is
# what stack[-1] holds -- the innermost thing still waiting. Swap it for
# stack[0] and you report index 0, the outermost. Both are defensible; your
# editor underlines the innermost, because that is the one you just typed.
# Note also where each failure is detected: an early close is caught mid-scan
# and returns immediately, while unclosed leftovers cannot be known until the
# loop ends. Same stack, two verdicts, two different moments.

Push to remember, pop to go back. That "go back" is not a toy — it's the mechanism behind undo, the browser Back button, and depth-first search. →

06The Back button of everything

Once you can see LIFO, you start finding it everywhere. A huge class of features is really one wish: "take me back to the thing I was just at." That is a pop. Undo is a stack of past states. Every action you take pushes a way to reverse it, and Ctrl-Z pops the most recent and applies it. Add a second stack for the ones you undo and you get redo: undo pops from one stack and pushes onto the other. Your browser's Back button is a stack of pages. Each link you follow pushes the current page, and Back pops it and returns you. Depth-first search (Vol 3, ch 13) explores a maze by pushing each junction and popping back to the last one when it hits a dead end. Recursion does this on the call stack, or you carry an explicit stack to do it yourself. Even a calculator evaluating 3 + 4 × 2 leans on a stack to hold operands. You press Back without a thought, and you were popping a stack.

That's the stack's mirror image: the queue, First In, First Out — the structure of every line you've ever stood in, every print job, and the OS scheduler deciding who runs next. It's cheap at both ends for a reason we'll build from memory up. →