Chapter 4 — Stacks, Queues, and Deques

“Abstraction is selective ignorance. The art of abstraction is choosing what to ignore — so that what remains is exactly what you need to reason about, and nothing more.” — Andrew Koenig

“But all things should be done decently and in order.” — 1 Corinthians 14:40

Why This Matters

For three weeks you have been building storage. Arrays — contiguous, random-access, O(1) to index. Linked lists — scattered, pointer-chained, O(1) to splice if you already hold the node. You measured both. You watched the linked list lose footraces it was “supposed” to win, because the array’s cache locality beat the linked list’s asymptotic bragging. That was the cost lesson, and you earned it.

This week the question changes. Until now you asked how is the data stored? This week you ask how is the data allowed to be used? — and you will discover that those are two completely different questions, and that keeping them separate is one of the most important ideas in all of software.

Here is the idea, stated plainly. A stack is not a thing. A queue is not a thing. They are promises. A stack is the promise: “the last item I gave you is the first one you’ll give back.” A queue is the promise: “the first item I gave you is the first one you’ll give back.” Neither promise says one word about how you keep it. You can keep the stack’s promise with an array. You can keep it with a linked list. The caller — the code using your stack — cannot tell which, and should not be able to tell, and that is exactly the point.

That separation has a name you must own by the end of this chapter: the abstract data type, or ADT. The ADT is the interface — the operations and the promises about how they behave. The implementation is the backing — the actual array or linked list underneath that delivers on the promise. One interface can sit on many backings. And choosing the backing for a given interface, under a given constraint, is the right-tool decision of this whole book, shrunk down to its smallest, clearest scale. If you can choose between an array-backed queue and a linked-backed queue for a real workload, you can — later, in Phase 2 — choose between SQLite and Postgres for a real application. It is the same muscle. We are training it on the small weights first.

There is also a trap waiting in this chapter, and it is one of the most common performance bugs in working Python. A queue seems trivial: append to the back, remove from the front. So a beginner writes a list and uses list.pop(0) to dequeue. It works. The tests pass. And it is O(n) per dequeue — quietly quadratic over a full drain — because removing the front of a Python list shifts every other element down one slot. You will see this fail in measured time, and you will learn the three standard fixes: a circular buffer (a ring), a two-stack queue, or — in real code — collections.deque. The lesson is the lesson of the whole course: the interface hid a cost, and the architect is the one who knows it’s there.

The Christian question for the week is what does it mean to wait your turn? A queue is order made mechanical: first come, first served, no cutting, no favorites. Paul tells the chaotic Corinthian assembly that all things should be done decently and in order — not because order is sterile, but because order is how a body of many members serves all of them fairly. And there is the deeper paradox to sit with: the kingdom inverts the queue. “So the last will be first, and the first last” (Matthew 20:16). The world runs on stacks of privilege — last in, first served. The kingdom runs on a queue that God Himself is free to reorder by grace. Hold both pictures. You are about to build the machinery of order; it is worth asking what order is for.

4.1 — Abstract Data Type vs. Implementation

Let us nail the central idea down before any code, because everything else hangs on it.

An abstract data type (ADT) is a specification of:

1. What operations exist — the method names and their parameters.
2. What each operation promises — its behavior, including the order in which things come back out.

That is all an ADT is. It says nothing about memory, nothing about pointers, nothing about arrays. It is a contract — the Coding 2 word, and exactly the Coding 2 idea. Here, for example, is the entire ADT of a stack:

• push(x) — add x to the collection.
• pop() — remove and return the most recently pushed item not yet removed.
• peek() — return that same item without removing it.
• is_empty() — true iff there are no items.

Read pop’s promise again: the most recently pushed item not yet removed. That single phrase — Last In, First Out — is the stack. Any code that honors it is a stack. Any code that violates it is not, no matter what it’s named.

An implementation (we will say backing) is the concrete data structure that delivers on the contract. For the stack ADT, an array can do it (push/pop at the end of the array) and a linked list can do it (push/pop at the head). Two backings, one interface, identical observable behavior.

In Python the cleanest way to write an interface is an abstract base class — a class with method signatures but no bodies, marked so Python refuses to let you instantiate it directly. You met abstract in Java in Coding 1; this is the same idea:

from abc import ABC, abstractmethod

class Stack(ABC):
    @abstractmethod
    def push(self, x): ...
    @abstractmethod
    def pop(self): ...
    @abstractmethod
    def peek(self): ...
    @abstractmethod
    def is_empty(self): ...

Stack declares the contract and nothing else. You cannot create a bare Stack() — Python raises TypeError. You can create an ArrayStack() or a LinkedStack() that each class ArrayStack(Stack): inherit from it and fill in every method. That is the ADT made real in code: one named promise, many concrete keepers of it.

Coach’s Note — “ADT vs. implementation” sounds like academic vocabulary, and it is — but it is also the single most practical idea in the chapter. Every time you reach for a Python list to “use as a stack,” you are choosing a backing for an ADT in your head. The professional difference is doing it on purpose — knowing the interface you want, knowing what each backing costs, and picking. The amateur grabs whatever is closest. The architect chooses the backing the constraint demands.

4.2 — The Stack (LIFO): Operations and Real Uses

A stack is Last In, First Out. Picture a stack of plates: you add to the top, you take from the top, and the plate you grab is always the last one you set down. You never reach into the middle. That restriction is not a weakness — it is the whole value. By forbidding access to the middle, the stack makes both of its operations O(1) and makes its behavior trivial to reason about.

stack = []                 # a Python list, used as a stack
stack.append("a")          # push  -> ['a']
stack.append("b")          # push  -> ['a', 'b']
stack.append("c")          # push  -> ['a', 'b', 'c']
top = stack[-1]            # peek   -> 'c'  (does NOT remove)
x = stack.pop()            # pop    -> 'c', list is now ['a', 'b']

The stack is everywhere in computing, often invisibly:

• The call stack. This is the big one, and it is a direct callback to recursion in Coding 2, Chapter 7. Every time a function calls another function, the machine pushes a stack frame — the local variables, the return address — onto the call stack. When the function returns, the frame is popped. Recursion works because the call stack is a stack: the most recently called function is the first to finish and return. When you got a RecursionError (“maximum recursion depth exceeded”) in Coding 2, that was a literal stack overflowing. The data structure you are studying this week is the one your own programs have been running on the entire time.
• Undo. Every undo feature in every editor is a stack. Each action you take gets pushed; “undo” pops the most recent one and reverses it. Last action in, first action undone.
• Depth-first search (DFS). Exploring a tree or graph by going as deep as possible before backing up is a stack-driven walk — either an explicit stack or the call stack via recursion. (Forward reference: graphs, Chapter 7.)
• Balanced-bracket checking. Compilers and editors use a stack to verify that every (, [, { is properly closed in the reverse order it opened. We build this in §4.3.
• Expression evaluation. Converting and evaluating arithmetic (infix to postfix, the “shunting yard”) is classic stack work.

Coach’s Note — When you see a problem where the most recent thing must be handled first — the deepest call returns first, the last edit undoes first, the innermost bracket closes first — your hand should already be reaching for a stack. Recognizing “this is LIFO-shaped” is the skill. The implementation is the easy part.

4.3 — Worked Example: Balanced-Bracket Checking

Here is the canonical stack problem, fully worked. The job: given a string of source code, decide whether every bracket is correctly matched and nested. ([{}]) is balanced. ([)] is not — the brackets cross.

Why is this a stack? Because of the word nested. When you open ( then [, the [ must close before the ( can. The most recently opened bracket is always the next one that must close. Last opened, first closed — LIFO, exactly.

The algorithm:

1. Walk the string one character at a time.
2. On an opener ((, [, {), push it.
3. On a closer (), ], }), the top of the stack must be the matching opener. Pop it and check. If the stack is empty (a closer with nothing open) or the popped opener doesn’t match, the string is unbalanced.
4. At the end, the stack must be empty. Any leftover opener never got closed.

PAIRS = {")": "(", "]": "[", "}": "{"}   # closer -> matching opener
OPENERS = set(PAIRS.values())

def is_balanced(text):
    stack = []
    for ch in text:
        if ch in OPENERS:
            stack.append(ch)                 # remember we owe a closer
        elif ch in PAIRS:                    # it's a closer
            if not stack:
                return False                 # closer with nothing open
            if stack.pop() != PAIRS[ch]:
                return False                 # wrong kind of closer
    return len(stack) == 0                   # leftover openers -> unbalanced

Trace ([)] by hand, because the trace is where the understanding lives:

The ) wanted to match the most recent opener, which was [, not (. The crossing is caught the instant it happens. That is the stack doing exactly one job — remembering what is still open, in the order it was opened — and doing it in O(n) time and O(n) space.

The runnable version, with a full test battery including real source code, is in code/bracket_checker.py. Run it.

4.4 — The Queue (FIFO): Operations and Real Uses

A queue is First In, First Out. Picture a line at a counter: you join at the back, you’re served from the front, and the person served is always the one who has waited longest. No cutting. This is the data structure of fairness — and the data structure of order, which is why it carries this week’s Scripture.

The two operations:

• enqueue(x) — add x to the back of the line.
• dequeue() — remove and return the item at the front (the one that has waited longest).

Plus the usual peek() (front without removing) and is_empty().

Real uses, everywhere systems must serve requests in a fair, predictable order:

• Breadth-first search (BFS). Exploring a tree or graph level by level — all the neighbors first, then their neighbors — is queue-driven. Discovered nodes go to the back of the queue; you process from the front, so you always process in discovery order. (Forward reference: graph BFS, Chapter 7. We do a tree version in §4.5.)
• Scheduling. An operating system’s run queue, a print queue, a task queue — jobs waiting their turn, served in order.
• Buffering. Data arriving faster than it can be processed gets queued: keystrokes, network packets, log lines. The producer enqueues, the consumer dequeues. (Forward reference: this is the exact shape of the Week 8 producer/consumer midterm.)
• Request handling. A web server with more incoming requests than worker threads queues the overflow. First request in, first request served.

Coach’s Note — Stack and queue differ in exactly one decision: which end you remove from. Remove from the same end you added (the back) and you have a stack. Remove from the opposite end (the front) and you have a queue. That one bit — same end or opposite end — is the entire difference between LIFO and FIFO. Everything else this chapter teaches is about making both ends cheap.

4.5 — Worked Example: Level-Order Numbering with a Queue

Here is the queue’s canonical problem, the mirror of the bracket checker. Given a tree, visit its nodes level by level — the root, then everything one step down, then everything two steps down — and number them in that order. This is breadth-first traversal, and it is a queue problem for the same reason brackets are a stack problem: the order the structure demands is exactly the order the ADT delivers.

Why a queue? Because BFS must finish an entire level before starting the next. When you visit a node, you discover its children — but you must not visit them yet; the rest of the current level comes first. So you put the children at the back of a queue and keep serving from the front. First discovered, first visited. FIFO.

from collections import deque   # we'll meet deque properly in §4.7

class TreeNode:
    def __init__(self, value, children=None):
        self.value = value
        self.children = children or []

def level_order(root):
    order = []
    q = deque([(root, 0)])             # queue of (node, depth) pairs
    while q:
        node, level = q.popleft()      # FIFO: take the OLDEST discovered node
        order.append((node.value, level))
        for child in node.children:
            q.append((child, level + 1))   # newly discovered -> back of the line
    return order

For a tree whose root has children a, b, c, and where a has children d, e, the queue produces: root (level 0), then a, b, c (level 1), then d, e (level 2). Every node on a level is numbered before any node on the next level — and that ordering is a free consequence of FIFO. You did not sort anything. The queue’s discipline produced the order for you.

Now swap the queue for a stack — replace q.popleft() with stack.pop() — and the very same code produces depth-first order instead. Same algorithm skeleton, one structure swapped, completely different traversal. That is the ADT idea paying off: the behavior you get is decided by the promise of the structure you chose, not by the loop around it.

The runnable version is in code/deque_and_bfs.py.

4.6 — The Backings: Array vs. Linked, and the O(n) Dequeue Trap

Now we make good on the chapter’s spine: one interface, two backings, and the costs that decide between them.

Stack: both backings are cheap

The stack is the easy case, because a stack only ever touches one end. Put that end where the backing is fast and everything is O(1).

# Array-backed stack: work at the END of the list (the cheap end).
class ArrayStack:
    def __init__(self):           self._items = []
    def push(self, x):            self._items.append(x)     # amortized O(1)
    def pop(self):                return self._items.pop()  # O(1): last elem
    def peek(self):               return self._items[-1]    # O(1)
    def __len__(self):            return len(self._items)

# Linked-backed stack: work at the HEAD of the list (the cheap end).
class LinkedStack:
    def __init__(self):
        self._head = None
        self._size = 0
    def push(self, x):
        self._head = _Node(x, self._head)   # O(1): new node points at old head
        self._size += 1
    def pop(self):
        node = self._head
        self._head = node.next               # O(1): unlink the head
        self._size -= 1
        return node.value
    def __len__(self):
        return self._size

Both push and pop are O(1) on both backings. The array gets there by working at the back (no shifting, amortized doubling — Chapter 2’s lesson). The linked list gets there by working at the head (no traversal, just one pointer swing — Chapter 3’s lesson). The full runnable pair is in code/stack_demo.py.

Queue: here is where it gets interesting

A queue touches both ends — add at the back, remove from the front. That is the whole problem. On a plain Python list, one of those ends is expensive:

# THE WRONG WAY. Works. Passes tests. Is quietly O(n) per dequeue.
class NaiveArrayQueue:
    def __init__(self):     self._items = []
    def enqueue(self, x):   self._items.append(x)   # O(1) amortized — fine
    def dequeue(self):      return self._items.pop(0)  # O(n)! shifts everything

list.pop(0) removes the first element — and then every other element must slide down one slot to fill the gap, because an array is contiguous and its first element must live at index 0. That is O(n) work for a single dequeue. Drain a queue of n items and you pay O(n²) total. The interface looked symmetric — append, pop — but the costs are wildly asymmetric, and the asymmetry is invisible until you measure it.

So measure it. code/queue_ring.py enqueues n items and dequeues them all, timing each approach:

      n |   naive O(n^2) |  ring O(n) | 2-stack O(n)
------------------------------------------------------
  10000 |        0.00515 |    0.00437 |      0.00190
  20000 |        0.02048 |    0.00857 |      0.00368
  40000 |        0.09318 |    0.01684 |      0.00733
  80000 |        0.38553 |    0.03582 |      0.01549

Read the naive column down. Double n and the time roughly quadruples — 0.005 → 0.02 → 0.09 → 0.38. That is the signature of O(n²) in the wild. The ring and two-stack columns roughly double when n doubles — the signature of O(n) total. At n = 80,000 the naive queue is already an order of magnitude slower, and the gap only widens.

Coach’s Note — This is the most important paragraph in the chapter, so slow down. list.pop(0) is not a typo or an exotic mistake. It is the natural, obvious thing a competent programmer writes when they need a queue and don’t know better. The tests pass. The demo runs. It ships. And then at scale it falls off a cliff, and someone spends a frustrating afternoon discovering that “the queue” was quadratic the whole time. The architect’s job is to know the cost is there before it bites — to know that removing the front of an array shifts the array, and to reach for the right backing on purpose. That is what this whole course is for.

Fix 1: the circular buffer (a ring)

The trap exists because we insisted the front lives at index 0. So stop insisting. Keep a fixed-size array and two indices: head (where the front currently is) and a count of how many slots are in use. Dequeue by advancing head instead of shifting the array. When an index runs off the end, it wraps around to the start using modulo — hence circular. The data never moves; only the indices move.

class RingQueue:
    def __init__(self, capacity=8):
        self._buf = [None] * capacity   # fixed storage, raw slots
        self._head = 0                  # index of the front element
        self._size = 0
    def enqueue(self, x):
        if self._size == len(self._buf):
            self._grow()                # amortized O(1), like a dynamic array
        tail = (self._head + self._size) % len(self._buf)   # wrap with modulo
        self._buf[tail] = x
        self._size += 1
    def dequeue(self):
        x = self._buf[self._head]
        self._buf[self._head] = None                 # release the reference
        self._head = (self._head + 1) % len(self._buf)   # advance, wrapping
        self._size -= 1
        return x
    def __len__(self):
        return self._size

The modulo % len(self._buf) is the whole trick: it makes index capacity wrap back to 0, so the array behaves like a circle with no ends. Enqueue and dequeue are now both O(1) (amortized, because the buffer still doubles when full — Chapter 2 again). No element ever shifts. This is how real bounded queues — OS buffers, network rings, audio buffers — are built. The complete version, including the _grow that copies the wrapped data out in logical order, is in code/queue_ring.py.

Fix 2: the two-stack queue

A different, beautiful fix: build a queue out of two stacks. Push new items onto an in stack. To dequeue, serve from an out stack — and when out is empty, pour the entire in stack into it, which reverses the order, turning LIFO into FIFO. Each item is moved across exactly once in its lifetime, so although a single dequeue can occasionally do O(k) work, the cost amortizes to O(1) per item — the same amortization argument as the dynamic array’s doubling.

class TwoStackQueue:
    def __init__(self):
        self._in = []
        self._out = []
    def enqueue(self, x):
        self._in.append(x)            # O(1)
    def dequeue(self):
        if not self._out:
            while self._in:           # pour-and-reverse, amortized
                self._out.append(self._in.pop())
        return self._out.pop()        # O(1)

Two stacks, one queue. It is worth building once just to feel the amortization happen.

Fix 3 (the real-world answer): use collections.deque

In production Python you would not hand-roll any of this. You would write from collections import deque and use it — append for enqueue, popleft for dequeue, both O(1). We build the ring by hand in the project to learn what deque costs; we use deque in real code because we learned it. That order matters. The next section is what deque actually is.

4.7 — The Deque: Both Ends, O(1)

A deque (pronounced “deck,” short for double-ended queue) is the generalization that makes the whole problem go away: it supports O(1) insertion and removal at both ends. It is a stack and a queue at the same time, and more.

Python’s standard library ships one: collections.deque.

from collections import deque
dq = deque()
dq.append("b")          # right:  ['b']
dq.append("c")          # right:  ['b', 'c']
dq.appendleft("a")      # left:   ['a', 'b', 'c']   -- O(1); list.insert(0,..) is O(n)
dq.pop()                # 'c'                          -- O(1)
dq.popleft()            # 'a'                          -- O(1)

Use it as a stack: append + pop. Use it as a queue: append + popleft. One structure, both ADTs, every operation O(1). This is why “just use collections.deque” is the correct professional answer to “how do I make a queue in Python.”

What is it built on? Not a plain dynamic array (that would make appendleft O(n), the very trap we’re escaping). CPython’s deque is a doubly linked list of fixed-size blocks — each block a small array of slots, the blocks chained with pointers. That hybrid is deliberate engineering: the pointers between blocks make both ends cheap to extend (Chapter 3’s linked-list strength), while the arrays inside each block recover some of the cache locality a pure linked list throws away (Chapter 2’s array strength). It is the right-tool thesis inside a single data structure — a designer who knew both backings’ costs and built a hybrid to get the best of each.

The one thing deque is not good at: indexing the middle. dq[n // 2] is O(n), because you have to walk the blocks to find it. A deque is for the ends, not the middle. If you need random access, you want a list. Right tool, again.

Coach’s Note — Notice the pattern across this chapter. The array is great at one end (the back). The linked list is great at one end (the head). The deque is great at both ends but bad in the middle. The plain array is good in the middle (random access) but bad at the front. There is no structure that is good at everything — if there were, this course would be one week long. Every structure trades. The architect’s whole job is knowing which trade each structure makes, so the one you pick trades away what you don’t need and keeps what you do.

4.8 — Which Backing for Which Constraint

Here is the decision table this whole chapter exists to earn — the right-tool thesis at its smallest scale. You now have the knowledge to read every cell and know why it holds.

Cost of the core operations, by backing:

And the decision, by constraint:

Notice that there is no single “best.” There is only best for this constraint. A ring buffer is the wrong tool when the size is unbounded and unpredictable; a linked backing is the wrong tool when memory is tight and you do many traversals (the pointer-chasing kills your cache, as you measured in Chapter 3). The architect does not have a favorite structure. The architect has a constraint, and the constraint chooses the structure.

4.9 — Common Bugs

Bug: Using list.pop(0) (or list.insert(0, x)) to build a queue. It works and it is O(n) per call — quietly quadratic over a full drain. Example: def dequeue(self): return self._items.pop(0) Fix: Use collections.deque (popleft), or a ring buffer, or a two-stack queue. Removing the front of a contiguous array always shifts every other element.

Bug: Off-by-one in the ring buffer’s wrap. Forgetting the modulo, or applying it to the wrong index, so the tail or head walks off the end of the array. Example: tail = self._head + self._size (no % len(self._buf)) → IndexError once you wrap. Fix: Every index advance in a ring must be (index + step) % capacity. The modulo is not optional; it is the ring.

Bug: A linked-backed queue that keeps only a head pointer. Enqueue then has to walk the whole list to find the tail — O(n) per enqueue. Example: enqueue loops while node.next: node = node.next to append. Fix: Keep both a head and a tail pointer. Enqueue at the tail, dequeue at the head, both O(1). And remember to set tail = None when the last item is dequeued.

Bug: pop/dequeue on an empty collection silently returns None instead of signaling. Callers then can’t tell “the value was None” from “the collection was empty.” Example: def pop(self): return self._items.pop() if self._items else None Fix: Raise IndexError (or a custom Empty) on empty. An empty pop is a programming error; make it loud. This is the Coding 2 “fail at the door” discipline.

Bug: Treating collections.deque as random-access. dq[i] for a middle i is O(n), and a loop of such accesses is silently O(n²). Example: for i in range(len(dq)): process(dq[i]) Fix: Iterate a deque (for item in dq:) — that is O(n) total. If you genuinely need random access by index, you wanted a list, not a deque.

Bug: Reusing one shared stack/queue across “independent” units of work without clearing it, so state leaks between them. Example: A module-level stack = [] reused by every call to a checker function. Fix: Create a fresh stack/queue per logical operation (local variable inside the function), exactly as is_balanced does in §4.3. State that should be local must be local.

4.10 — Reps

Open the exercises for the full set. This week’s reps build the interface-and-backings muscle directly toward the project: you will implement stacks and queues on both backings, hit the O(n) dequeue trap on purpose and fix it with a ring, and use a stack and a queue to solve the two canonical problems (brackets and level-order).

A preview:

• Rep 1 — Use a plain list as a stack; verify LIFO by hand.
• Rep 4 — Build the NaiveArrayQueue, measure its O(n²) drain, then fix it.
• Rep 7 — Implement the ring buffer’s wrap-around and prove no element ever shifts.
• Rep 11 — Solve level-order numbering with a queue, then change one line to get DFS.

AI is OFF — this is Phase 1. You cannot reason about a queue’s cost you have never paid yourself. Build all four backings by hand.

4.11 — This Week’s Project

You’re ready for Project 4 — Choose Your Backing Store, in Project 4.

You will implement Stack and Queue as interfaces, each with two backings (array-backed and linked-list-backed), and write one shared test suite that runs against all four — proving the ADT idea in code: the same tests pass no matter what’s underneath. Then you’ll put the structures to work: your stack solves balanced-bracket checking, your queue does level-order numbering of a small tree. The Medium tier adds a Deque and makes you fix the O(n) dequeue with a real ring buffer. The Hard tier is the memo that is the soul of the week: for each of your four implementations, name a workload and a constraint (memory-tight, append-heavy, fixed-size, unknown-size) under which it is the right choice — the right-tool thesis at the smallest scale, in your own words, backed by your own code.

Like every Phase 1 project, it ends in a written tradeoff deliverable. The code proves you can build it. The memo proves you know when to. The second is the architect’s skill.

A starter is provided: code/p4_starter.py.

4.12 — Coach’s Final Word for Week 4

This week you learned the difference between a thing and a promise. A stack is not a list and not a chain of nodes — it is the promise “last in, first out,” and you can keep that promise with either backing. A queue is the promise “first in, first out,” and how you keep it determines whether your program is fast or quietly quadratic. You saw the pop(0) trap fall off a cliff in measured time, and you learned the three ways out: the ring, the two stacks, and the one you’ll actually use, collections.deque.

You also took your first real step into the central skill of the whole book: choosing a backing for an interface under a constraint. There is no best backing. There is only the right backing for this workload, this memory budget, this access pattern. The table in §4.8 is not a thing to memorize. It is a thing to derive, every cell, from what you now understand about arrays and pointers and caches.

If the amortized O(1) of the ring feels slippery: that’s the gap. Build it in the project, watch the buffer double, watch head wrap around, and the argument will become something you can feel. Close it.

All things should be done decently and in order. You built the machinery of order this week — the queue that serves fairly, first come first served, no cutting. Hold on to the harder word too: the last shall be first. The kingdom is free to reorder the line by grace. The queue is a good servant and a poor master. Build it well; remember Who is at the front.

See you on Monday.

Up next: Read the exercises and complete every rep. Then open Project 4 and build all four backings. After that, Chapter 5 — hash tables, the magic and the fine print, where “average O(1) lookup” feels like magic until you read what it costs.

Previously: Chapter 3 — linked lists and the cost of pointers, where the array’s O(n) middle met its challenger.