Chapter 4 — Reps

Conditioning, not grading. Stacks, queues, deques — built by hand, in Python.

Ground rules:

1. Type every line yourself. No copy-paste from the chapter or the code/ folder. The point is the motion in your fingers, not the file on disk.
2. Run everything. After each rep, run it. When a rep says “measure,” actually measure — time.perf_counter() around the loop, real numbers on your screen.
3. AI stays OFF. Phase 1. You cannot reason about the cost of a queue you have never built and never paid for. Build all four backings yourself, by hand.
4. Raise on empty. Every pop/dequeue/peek on an empty collection must raise IndexError, not return None. Build the habit now.

Python toolchain setup (a real local Python 3, your editor, git) lives in Appendix A. Everything here assumes you can run python3 your_file.py from a terminal.

Reps 1–3: The Stack, Both Backings

Rep 1 — A List Is a Stack

Open a Python REPL (python3). Using only a plain list, drive it as a stack:

s = []
s.append("a"); s.append("b"); s.append("c")
print(s[-1])      # peek -> 'c'
print(s.pop())    # 'c'
print(s.pop())    # 'b'
print(s)          # ['a']

Say out loud, before you run each line, what it will print. Then run it. The whole rep is predict, then confirm — the Chapter 1 muscle, applied to a stack. Confirm that the item you get back is always the last one you pushed.

Rep 2 — ArrayStack Behind an Interface

Write an abstract base class Stack(ABC) with @abstractmethod signatures for push, pop, peek, is_empty, __len__. Then write class ArrayStack(Stack) backed by a list, working at the end of the list.

Requirements:

• pop and peek raise IndexError on empty.
• __len__ returns the count.

Prove it: s = ArrayStack(); push 1, 2, 3; assert pop() == 3, 2, 1 in that order. Then try: Stack() and confirm Python raises TypeError — you cannot instantiate the bare interface. That TypeError is the abstract base class doing its job.

Rep 3 — LinkedStack, Same Interface

Write class LinkedStack(Stack) backed by a singly linked list of _Node objects (give _Node __slots__ = ("value", "next") to trim its memory — callback to Chapter 3). Push and pop at the head.

Now write a single function:

def exercise_stack(make_stack):
    s = make_stack()
    s.push(1); s.push(2); s.push(3)
    assert s.pop() == 3 and s.pop() == 2 and s.pop() == 1
    print(f"{type(s).__name__} is LIFO-correct.")

Call it with both ArrayStack and LinkedStack. One test function, two backings, both pass. That is the ADT idea in your own hands.

Reps 4–6: The Queue and the O(n) Trap

Rep 4 — Build the Trap, Then Measure It

Write NaiveArrayQueue with enqueue = list.append and dequeue = list.pop(0). Confirm it is FIFO-correct (enqueue a,b,c; dequeue -> a,b,c).

Now measure the trap. Write a function that enqueues n items then dequeues all n, timed with time.perf_counter(). Run it at n = 10_000, 20_000, 40_000, 80_000 and print a table.

Look at your numbers. Each time n doubles, the time should roughly quadruple. Write one sentence in a comment explaining why — what does list.pop(0) do to the other elements?

Rep 5 — LinkedQueue With Head and Tail

Write LinkedQueue backed by a singly linked list that keeps both a _head and a _tail pointer. Enqueue at the tail, dequeue at the head — both O(1).

The bug to avoid: when you dequeue the last item, you must reset _tail to None as well (otherwise _tail dangles at a node that’s no longer in the list). Write a test that enqueues two items, dequeues both, then enqueues a third, and confirm you get the third back correctly. That test catches the dangling-tail bug.

Rep 6 — collections.deque as a Queue

Rewrite the queue using collections.deque: append to enqueue, popleft to dequeue. Re-run your timing harness from Rep 4 against it.

Compare the two tables. The deque version should scale linearly — double n, roughly double the time. Write one sentence: which would you ship, and why? (The answer should mention both cost and not reinventing a C-level wheel.)

Reps 7–9: The Ring Buffer

Rep 7 — Implement the Ring

Write RingQueue(capacity) backed by a fixed-size list [None] * capacity, with a _head index and a _size count. Enqueue at (head + size) % capacity; dequeue by reading head, setting that slot to None, then head = (head + 1) % capacity.

For now, raise IndexError if you try to enqueue past capacity (no growth yet). Test it:

• Fill to capacity, dequeue two, enqueue two more — confirm the indices wrap around the end of the buffer and the FIFO order is still correct.
• Print self._buf and self._head after each operation so you can see the wrap happen.

The whole rep is to watch data stay put while only the indices move. No element ever shifts. That is the fix to Rep 4’s trap.

Rep 8 — Make the Ring Grow

Add a _grow method so the ring doubles its capacity when full (amortized O(1) enqueue, exactly like the dynamic array in Chapter 2). The subtlety: when you copy into the bigger buffer, copy the elements out in logical order starting from _head, so the new buffer starts unwrapped at index 0:

def _grow(self):
    old = self._buf
    new = [None] * (len(old) * 2)
    for i in range(self._size):
        new[i] = old[(self._head + i) % len(old)]
    self._buf = new
    self._head = 0

Test: start with capacity=2, enqueue 5 items, dequeue all 5, confirm FIFO order survived the growth. If you copy in physical order instead of logical order, this test fails — that’s the bug this rep is teaching you to avoid.

Rep 9 — The Two-Stack Queue

Build a queue out of two lists-as-stacks (_in and _out). Enqueue pushes onto _in. Dequeue: if _out is empty, pour all of _in into _out (reversing it), then pop _out.

Test FIFO correctness with an interleaved workload: enqueue a, b; dequeue (→ a); enqueue c; dequeue (→ b); dequeue (→ c). The interleaving is the real test — it forces the pour-and-reverse to happen mid-stream. Confirm each item is moved across at most once (add a print inside the pour loop and count).

Reps 10–11: The Structures at Work

Rep 10 — Balanced Brackets

Write is_balanced(text) using a list as a stack (the algorithm is in §4.3 — write it from memory, then check). Handle (), [], {}, and ignore all non-bracket characters so it works on real code.

Test these, asserting each:

The ([)] case is the one a non-stack solution gets wrong. Make sure yours catches it.

Rep 11 — Level-Order, Then Flip It to DFS

Build a small tree of TreeNode(value, children) objects (use the one in §4.5, or your own). Write level_order(root) using a deque as a FIFO queue — popleft to take the oldest discovered node, append children to the back. Print each node with its level number.

Now make one change: replace the FIFO popleft() with LIFO pop(). Run it again. Observe that the same code now produces depth-first order instead of breadth-first. Write one sentence explaining why swapping the queue for a stack changed the traversal — this is the ADT idea paying off.

Done? One Last Thing.

From scratch, no looking — in one file:

1. Write Stack(ABC) and Queue(ABC) interfaces.
2. Write ArrayStack, LinkedStack, RingQueue (growable), and LinkedQueue — all four behind the interfaces.
3. Write one test_stack(make) and one test_queue(make), and run each against every matching backing. All four green.
4. Use your stack for is_balanced("([{}])") and your queue for level-order of a 7-node tree.

If you can produce all four backings, one shared test suite, and both worked problems — cold, from memory, AI off — you have the week. That is exactly Project 4’s Normal tier, and you just did it as a warm-up.

Up next: Project 4 — Project 4: Choose Your Backing Store.