Chapter 3 of 10All chapters
Chapter 3 of 10
Stacks and queues
Order of service.
The two disciplines
A stack returns the most recent item, which suits undo, parsing and depth-first traversal. A queue returns the oldest, which suits scheduling and breadth-first traversal.
- Function calls are a stack, which is why deep recursion overflows one.
- A deque allows both ends and covers either case.
Priority queues
A heap always gives the smallest or largest item next, in logarithmic time. It powers scheduling, shortest path algorithms and any top-n problem over a stream.