Foundations · Module 6
Stacks and queues
Last in first out and first in first out, the ring buffers behind them, and the call stack.
Stacks and queues restrict where you can add and remove items, and the restriction is what makes them fast and useful. This module builds a stack on an array, a queue on a ring buffer that never shifts an item, and a deque that does both, then uses a monotonic stack to turn quadratic scans into linear ones. It ends with the stack every program already uses: the call stack.
- 1Stacks and the LIFO ruleA stack only lets you touch its most recent item. That restriction makes it cheap to build on an array, and it is exactly what nested structure, undo and matching brackets need.12 min
- 2Queues and ring buffersA queue serves items in the order they arrived. Built on a ring buffer, a fixed array whose start and end wrap around, every operation is O(1) and no item ever moves.13 min
- 3Deques and monotonic stacksA deque works at both ends in O(1). A monotonic stack keeps its items in sorted order by popping everything a new item beats, which answers 'what is the next bigger value?' for every element in one pass.14 min
- 4The call stack is a stackEvery function call pushes a frame and every return pops one. That is why recursion works, why it has a depth limit, and how any recursive algorithm can be rewritten with a stack of your own.12 min