Week 35: TAOCP 2.2.2 Sequential Allocation

Storing stacks and queues in contiguous memory, handling overflow, circular queues, and keeping several stacks in one shared region with a method for repacking memory when one stack runs out of room (Garwick's approach).

Time About 7 hours this week

Why it matters

Arrays beat linked structures for cache performance, so contiguous allocation and growth strategies are still very relevant. Think dynamic arrays, ring buffers and arena allocators.

Before you start

2.2.1 Stacks, Queues, and Deques

How to approach it

Implement a circular queue with an explicit full and empty test. Then implement two stacks growing toward each other in one array. The multi-stack repacking algorithm is worth tracing by hand once; the analysis can be read lightly.

Exercises

Work every exercise rated 10 to 20; most are about tracing the algorithm by hand or tweaking one step, which is exactly the skill you want. Pick one or two rated 20 to 25 that involve modifying the algorithm and implement your modification in a real language with tests. Skip HM exercises unless you enjoy calculus, and treat anything rated 40+ as a research problem, not homework.

Traps

The classic circular-queue bug: not being able to tell full from empty.
Off-by-one on the boundary when two stacks meet.