The idea
A queue adds at the back and removes from the front, both in O(1). It models anything served in arrival order: simulations, waiting lines, breadth-first search.
A deque can push and pop at both ends in O(1), and unlike queue it can be indexed.
A monotonic deque solves sliding-window minimum or maximum in O(n). New items pop worse items from the back; the front leaves when it slides out of the window; the front is always the answer.
Sample problem
239. Sliding Window Maximum ↗ Hard
A window of size k slides over an array from left to right, one position at a time. Return the maximum of each window.
nums = [1,3,-1,-3,5,3,6,7], k = 3 output = [3,3,5,5,6,7]
Why the solution works
Scanning each window is O(n·k). But when the window moves, only one number enters and one leaves.
An element that is smaller than a newer element is useless: the newer one is larger and stays in the window longer. Removing such elements from the back leaves a deque whose values decrease, so the front is always the maximum.
A deque is needed because both ends change: new indices push and pop at the back, and the front is removed when it slides out of the window.
Complexity: O(n) time, O(k) memory.
Watch out
- Keep positions in the deque, not values: you need them to know when the front has left the window.
std::queuecannot be iterated or indexed; usedequewhen you need to look inside.- Check
empty()beforefront(),back()or a pop.