TAOCP Vol 1: Fundamental Algorithms · Week 34
TAOCP 2.2.1 Stacks, Queues, and Deques: reading guide
The three classic linear structures defined by where you insert and delete. Knuth uses railway-switching pictures to explore which output orders a stack or deque can produce from a given input order.
Time About 5 hours this week
Why it matters
Stacks and queues are the backbone of parsers, schedulers and graph search. The question of which permutations a stack can produce is a classic interview-style puzzle with a beautiful answer.
Before you start
- 2.1 Introduction
How to approach it
Draw the railway diagrams and push cars through them by hand. Then write a quick program that lists all permutations of 1..4 a stack can produce and count them. Compare with the Catalan numbers.
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
- Confusing an input-restricted deque with an output-restricted one.