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

  1. 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.
  2. 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

  1. 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.
  2. 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

  1. 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

  1. 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.