Module 10
Queue, Deque and Monotonic Queue
First in, first out: simulate lines, build circular buffers, and keep a window's maximum ready at the front of a monotonic deque.
A queue serves items in arrival order. It's the backbone of breadth-first search, task scheduling and rate limiting. A deque (double-ended queue) adds and removes at both ends, so it can act as a stack, a queue, or something cleverer.
The cleverer thing is the monotonic deque: by throwing away elements that can never be the answer, it keeps the maximum (or minimum) of a sliding window at its front, giving O(n) for problems that look like they need a heap.
Best after: Stack and Monotonic Stack, Sliding Window
Part 1
Learn the ideas
- 10.1Queues: First In, First OutAdd at the back with `offer`, remove from the front with `poll`, look with `peek`. All O(1) with ArrayDeque.10 min
- 10.2Circular BuffersA fixed array where the front and back indexes wrap around with `% capacity`, so no element ever has to shift.12 min
- 10.3Deques and the Monotonic DequeKeep window candidates in decreasing order: drop expired ones from the front and hopeless ones from the back. The front is always the window's maximum.16 min
Part 2
Solve the problems
In order of difficulty. Each one shows the pattern it teaches.
Simulate with a queue first, then notice the formula that skips the simulation.
Amortised analysis in action: two stacks reverse order lazily, so each element moves at most twice.
A queue as a sliding time window: add new events at the back, expire old ones from the front.
A fixed array with a head index and a size, wrapping with modulo: the structure inside ArrayDeque and ring buffers.
The monotonic deque gives each window's maximum in O(n) total, beating a heap's O(n log n).