Project 4 — Choose Your Backing Store

“So the last will be first, and the first last.” — Matthew 20:16

Chapter: 4 — Stacks, Queues, and Deques Due: End of Week 4 Submit: A link to your code — a public GitHub repo URL — containing your source files, the shared test suite, your memo, and README.txt. See Appendix A for the local toolchain + git workflow. Allowed tools: Python 3, your editor, pytest or the standard unittest, the textbook. AI policy: Phase 1 (wk 1–8): AI is OFF. No assistants, no completions, no “explain this.” You cannot reason about the cost of a backing you have never built yourself — and the whole point of this project is to feel that cost so that, in Phase 2, you can direct an agent to choose well. Build it by hand.

The Setup

A small ministry runs a check-in kiosk for its Sunday programs. Two things happen at that kiosk, and they are shaped differently.

First, the kiosk validates the structured forms volunteers fill out — nested sections with brackets that must open and close in order. A malformed form should be rejected at the door with a clear answer, not stored half-broken. That is a stack problem: the most recently opened section must close first.

Second, the kiosk serves families in the order they arrive — first come, first served, no cutting, no favorites. A family that has waited longest is called next, and the children are numbered by group in arrival order. That is a queue problem: first in, first out.

The ministry’s old kiosk software “worked” — until a busy Christmas Eve service when the line backed up and the kiosk crawled to a halt with two hundred families queued. The volunteer who wrote it had built the queue with list.pop(0). It was quietly quadratic. It fell over exactly when it was needed most.

You are the engineer they hired to do it right. You will build a stack and a queue as proper interfaces, each with two backing stores, prove all four correct with one shared test suite, and put them to work on the two real problems. And — because the architect’s real deliverable is judgment, not just code — you will write the memo that says which backing belongs where, and why.

Learning Targets

By completing this project, you will demonstrate that you can:

• Separate an abstract data type (the interface and its promises) from its implementation (the backing store).
• Implement a stack and a queue on both an array backing and a linked backing.
• Write one test suite that runs against multiple implementations of the same interface.
• Recognize and fix the O(n) dequeue trap with a real circular buffer.
• Use a stack to solve balanced-bracket checking and a queue to solve level-order numbering.
• Choose a backing store from a constraint — and defend the choice in writing. (The thesis.)

Normal Tier

Goal: Stack and Queue, each as an interface with two backings, one shared test suite over all four, plus the two worked problems.

Required features

1. Interfaces. An abstract base class Stack (operations: push, pop, peek, is_empty, __len__) and Queue (operations: enqueue, dequeue, peek, is_empty, __len__). Use abc.ABC + @abstractmethod. Instantiating a bare interface must raise TypeError.
2. Four implementations, each subclassing the right interface:
   • ArrayStack — list-backed, working at the back end.
   • LinkedStack — singly-linked, working at the head.
   • ArrayQueue — list-backed. (Normal tier may use the naive pop(0); you must document in a comment that it is O(n) and that Medium fixes it. Knowing the cost is the requirement.)
   • LinkedQueue — singly-linked with both head and tail pointers, O(1) at each end.
3. Correct empty behavior. Every pop, dequeue, and peek raises IndexError on an empty collection. No silent None.
4. One shared test suite. A test_stack(make_stack) and a test_queue(make_queue) that take a factory and run the full battery (LIFO/FIFO order, length tracking, peek-doesn’t-remove, empty raises IndexError). Run each against every matching backing. The identical tests passing on both backings is the proof of the ADT idea — and it’s graded as such.
5. Worked problem A — balanced brackets. A function is_balanced(text) that uses your Stack (either backing) to verify (), [], {} are matched and nested in arbitrary text, ignoring non-bracket characters. Must correctly reject the crossing case ([)].
6. Worked problem B — level-order numbering. A function level_order(root) that uses your Queue (either backing) to number the nodes of a small tree breadth-first, returning (value, level) in BFS order.
7. Decomposition. Interfaces, implementations, the two problems, and the tests live in clearly separated files (e.g. adts.py, problems.py, test_adts.py). Not one giant file.

Example of expected output

Running your test suite and demos should produce something like:

ArrayStack     passes the shared Stack suite.
LinkedStack    passes the shared Stack suite.
ArrayQueue     passes the shared Queue suite.
LinkedQueue    passes the shared Queue suite.

is_balanced('([{}])')  -> True
is_balanced('([)]')    -> False

level-order of sample tree:
  #1 (level 0) root
  #2 (level 1) a
  #3 (level 1) b
  #4 (level 1) c
  #5 (level 2) d
  #6 (level 2) e
  #7 (level 2) f

Normal-tier rubric (out of 100)

Medium Tier (+up to 25% extra credit)

M1. The Deque

Implement a Deque interface (push_front, push_back, pop_front, pop_back, peek_front, peek_back, is_empty, __len__) on a doubly linked list of your own (each node has prev and next), with every operation O(1). Add it to your shared-test approach with a test_deque(make_deque) battery. Then show — in a one-paragraph comment or your README — that your Deque can act as both a stack and a queue, and which methods you’d use for each.

M2. Fix the O(n) dequeue with a ring

Build a RingQueue — a real circular buffer with a _head index, a _size count, modulo wrap-around, and amortized-O(1) growth (double when full, copying out in logical order). Make it pass the same test_queue suite as the other queue backings.

Then measure the fix. Write a timing harness that enqueues n items and dequeues all n, for the naive ArrayQueue and the RingQueue, at n = 10_000, 20_000, 40_000, 80_000. Produce a table. Confirm the naive column roughly quadruples per doubling (O(n²) total) while the ring roughly doubles (O(n) total). Include the table in your README.

M3. Property test the ADT

Write a single test that, for any backing, runs a randomized sequence of operations against your implementation and against a trusted reference (Python’s list for the stack, collections.deque for the queue), asserting they stay in lockstep. Run it on every backing. A property test like this catches order bugs a hand-written example test misses.

Hard Tier (+up to 25% additional extra credit)

H1. The right-tool memo (this is the point of the week)

Write MEMO.docx. For each of your stack/queue/deque implementations, give:

• The workload it is best for (e.g. “append-heavy, drain-rarely,” “bounded fixed-size buffer,” “frequent both-end churn”).
• The constraint that selects it: one of memory-tight, append-heavy, fixed-size, or unknown/varying-size — and say why that constraint points here in terms of the actual costs (pointer overhead, cache locality, resize copies, shift cost).
• The wrong choice for that workload and the concrete symptom it would produce (cite the Christmas-Eve kiosk: which backing caused it, and which would have prevented it).

This is the right-tool thesis at the smallest scale. It must reference your own measured numbers from M2 where relevant. A memo that only restates the chapter’s table earns little; a memo that reasons from your own code and measurements to a defensible recommendation earns full marks. This is the deliverable an agent cannot write for you — it requires judgment about a specific workload, and the judgment is the assignment.

H2. A bounded ring with back-pressure

Add a fixed-capacity mode to your RingQueue (no growth). When full, instead of crashing, enqueue returns False (or raises a Full exception — your choice, documented) so the caller can apply back-pressure. Model the kiosk: simulate families arriving faster than they’re served, and show your bounded queue refusing new arrivals gracefully rather than consuming unbounded memory. Explain in the memo when a bounded queue is the right tool and an unbounded one is the wrong one — a forward link to buffering and the Week 8 producer/consumer midterm.

H3. Measure the linked vs. array tradeoff for yourself

For one ADT (stack or queue), benchmark your array backing against your linked backing on a large workload (hundreds of thousands of operations). Report wall-clock times. You will likely find the array backing wins even where the asymptotics tie — because of cache locality and per-node allocation overhead (Chapter 3’s lesson, paid again here). Document the result and explain why the “same Big-O” structures are not the same speed. Fold this into the memo.

Submission

Submit one URL — a public GitHub repo.

What the repo must contain

1. adts.py — the Stack / Queue (and Medium: Deque) interfaces and all backing implementations.
2. problems.py — is_balanced and level_order, each using your ADTs.
3. test_adts.py — the shared test suite (and M3’s property test), runnable with pytest or python3 -m unittest.
4. bench.py (Medium/Hard) — the timing harness and its printed table.
5. MEMO.docx (Hard) — the right-tool memo.
6. README.txt — your reflection:

# Project 4 — Choose Your Backing Store

**Tier targeted:**  Normal / Medium / Hard
**Backings built:**  (list them)
**Shared test suite:**  how to run it; confirm all backings pass
**O(n) dequeue:**  did you hit it / measure it / fix it? where?
**Right-tool summary:**  one sentence per backing — which constraint it wins under
**What I learned:**  (one paragraph)
**What I'd change:**  (one sentence)
**AI usage:**  NONE — Phase 1.  Signed: <your name>

7. A reflection comment block at the top of adts.py — condensed version of the README fields.
8. The repo left runnable — python3 -m pytest (or unittest) passes; python3 problems.py (or equivalent) shows the two worked problems.

Hints (Read Before You Begin)

• Start from the starter. code/p4_starter.py already has the interfaces, the four class skeletons, and the shared test suite. Fill the TODOs and watch the suite go green one backing at a time. You may split it into the separate files the rubric wants once it works.
• Stack first — it’s the easy one. A stack only touches one end, so both backings are pure O(1) with no traps. Get both stacks green before you touch a queue.
• The queue is where the lesson lives. Build LinkedQueue with head and tail, and remember to null the tail when the last item leaves. Build ArrayQueue naive on purpose so you can measure it before you fix it. The fix (RingQueue) is Medium, but understanding why it’s needed is Normal.
• The ring is two indices and a modulo. Don’t shift anything, ever. Advance head on dequeue; compute the tail as (head + size) % capacity on enqueue. The modulo is the ring. Print the buffer after each op while you’re debugging the wrap.
• One test, many backings — pass a factory. test_queue(LinkedQueue), test_queue(RingQueue). The function takes the class, makes a fresh instance, and runs the battery. That’s the whole ADT idea in one parameter.
• Measure, don’t guess. When the project says O(n) vs O(n²), prove it with time.perf_counter() and a table. Phase 1 is the cost course; a claim without a measurement is a guess.

What Mastery Looks Like (Beyond the Rubric)

A great Project 4 has a test file you can read top to bottom and understand the contract of a stack and a queue from the tests alone — the tests are a specification, the Coding 2 skill in a new key. The same test_queue runs against the naive array, the linked list, the ring, and (Medium) a collections.deque adapter, and they all pass, because they all keep the same promise. When a grader swaps in a fifth backing, your test suite tests it for free.

A great Project 4’s MEMO.docx reads like an architect wrote it. It does not say “linked lists are O(1) to insert.” It says “for this kiosk, families arrive in unpredictable bursts and the buffer must not grow without bound on a busy night, so I chose a bounded ring; a linked queue would have served correctly but spent memory I couldn’t predict, and the naive array — the one that crashed last Christmas Eve — would have been O(n) per dequeue and died under exactly the load the kiosk exists to handle.” That is reasoning from a real constraint to a defended choice. That is the job.

A great Project 4 ships the ring even on a day no one will overflow it — because it is the right shape and you ship right shapes.

Coach’s Note — Students sometimes treat the four backings as busywork: “why build the same thing four times?” Because the four-times is the lesson. The day you internalize that one interface can rest on many backings, and that the choice among them is a real, costed decision, is the day you start thinking like an architect instead of a coder. You will make this exact move in Phase 2 — one API interface, three possible databases underneath — and you will make it well because you built four queues by hand in Week 4 and felt the difference.

When You’re Done

1. Run the full test suite. Confirm every backing is green.
2. Run the bench (Medium). Confirm the naive queue’s quadratic curve and the ring’s linear one.
3. Read your own MEMO.docx (Hard) as if you were the ministry’s tech-savvy elder. Does each recommendation follow from a stated constraint and your own numbers? If not, revise.
4. Push to GitHub. Confirm the repo is public and runnable.
5. Read Chapter 5. Hash tables next — where “average O(1) lookup” feels like magic until you read the fine print.

A theological footnote. A queue is order made fair: first come, first served, the longest-waiting called next. “But all things should be done decently and in order” (1 Cor. 14:40) — Paul to a church that had forgotten how to wait for one another. Yet the kingdom keeps a stranger ledger: “the last will be first, and the first last” (Matt. 20:16). The world runs on stacks of privilege — last in, first served. Grace runs a queue God is free to reorder, where the latecomer to the vineyard is paid the same as the dawn laborer. Build the queue well; serve fairly; and remember that the One at the front of the line came to be last of all and servant of all. The structure is a good servant. It makes a poor god.

See you next week.