51The stack — last in, first out

In Chapter 50 we strung data together with pointers. Each 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, 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, 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 — LIFO, Last In, First Out. The tray you can currently touch is the top. Adding is push. Removing the top is pop. Looking at the top without removing it is peek.

Now the memory picture, and 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, no data block yet. A list of a million integers is 8,000,056 bytes, almost exactly 8 bytes per element. That's because the block stores only the reference; the integer object it points at lives elsewhere on the heap. So a stack is about as light as a container gets: 8 bytes of "plumbing" per item, plus a little overallocated slack on the end.

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 increments the length. It does not look at slot 0, or slot 3, or the million items underneath. It touches exactly one cell. Work that doesn't depend on how big the stack is means O(1). To pop, it reads the top cell, hands the reference back, and decrements the length — again one cell, O(1). To peek, it reads a[-1] and returns it without changing anything — O(1). Three operations, none of which ever walks the block.

There's one honest wrinkle. Every so often a push finds no free slot left, so 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 averaged over many pushes the cost 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 — a handful of copies across dozens of pushes, each one buying room for the next batch.

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. stack[-1] peeks — it reads the top without disturbing it, so the list still has three items. stack.pop() removes and returns the top, 'mi'. 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; the point is that 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. 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. 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."

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 — 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. Push makes a node and points it at the old top; pop follows next. That's 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 was about 0.20 s on a list versus 0.88 s on a node-per-item stack — same Big-O, 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__, against the list's flat 8 bytes per item.

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 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 the one that called it 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.

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, and 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's 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, and 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 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; 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. That's 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 is on top of the stack, so pop and check they're 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 — 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 — 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.

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, because 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; 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; 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; 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. →