Stacks and Queues
A stack of plates and the line at the coffee shop: last in, first out and first in, first out, where each runs at work (undo, the back button, print queues), and deques and ring buffers.
Updated
Stacks
- Undo the Last Thing First: Stacks (Apprentice): An editor has to take back its most recent change first, then the one before, after 10,000 edits as quickly as after 10. Find a structure that keeps undo instant, and learn why it does less than a list on purpose: the stack.
- Redo, the Back Button and Matching Brackets: Stacks at Work (Apprentice): Three everyday features need the most recent thing first: redo, a browser's back and forward buttons, and checking that brackets match. See why throwing things away, searching and counting fall short, and solve all three with stacks.
Queues
- First Come, First Served at Rush Hour: Queues (Apprentice): At 8 a.m. the coffee shop's order screen freezes: serving each order from the front of a list moves every order behind it. Find a way to join at the back and serve from the front in one step each, and meet the structure built for it: the queue.
- Cutting In, and Keeping Only the Last 100: Deques and Ring Buffers (Journeyman): A paid mobile order jumps to the front of the line, a customer at the back gives up and leaves, and a log must keep only its last 100 lines out of a million. Find the line that's cheap at both ends, and the fixed circle of slots that never moves or grows.
In Your Textbook
- In Your Textbook: Abstract Data Types (Journeyman): Textbooks separate what a structure does (an abstract data type, such as a stack) from how it's built (a data structure, such as an array or a linked list). In code, that line is an interface, and any class that keeps its promise can stand behind it.
Exercise: The Coffee Shop Order Line
- Exercise: The Coffee Shop Order Line (Apprentice): The coffee shop's order screen freezes at rush hour: make its line of orders fast without changing what it does, build the pile of clean mugs behind the counter, and serve a 400,000-order rush in under 2 seconds, each order in the mug on top.