DSA Notes

Data Structures

Queue & Deque

First in, first out; a deque opens both ends.

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::queue cannot be iterated or indexed; use deque when you need to look inside.
  • Check empty() before front(), back() or a pop.
Watch it run

Try your own input

Practise on LeetCode