Overview
A queue serves elements in arrival order: enqueue at the back, dequeue from the front. That makes it the natural structure for anything processed in rounds — breadth-first search explores a graph level by level with a queue, and simulations of waiting lines, task schedulers and rate limiters all use one.
A deque (double-ended queue) allows O(1) pushes and pops at both ends. Its star application is the monotonic deque: keep indices whose values are in decreasing order, drop indices that slide out of the window from the front, and the front is always the window's maximum. Sliding-window maximum goes from O(n·k) to O(n).
Key concepts
Tick a concept once you can explain it in your own words without notes.
Complexity cheat sheet
| Operation | Cost |
|---|---|
| Enqueue / dequeue (deque) | O(1) |
| Python list.pop(0) | O(n) — avoid |
| Sliding window max with deque | O(n) total |
Patterns to recognise
Level-by-level processing
Use it for: BFS, level order traversal, rotting oranges.
Record len(queue) at the start of a level and process exactly that many.
Monotonic deque
Use it for: Sliding window maximum/minimum, shortest subarray with sum ≥ k.
Keep the deque sorted; front is the answer for the current window.
Round-based simulation
Use it for: Recent calls counter, Dota2 senate, task scheduling.
Push items back with updated state; pop expired items from the front.
Code template
from collections import deque
def max_sliding_window(nums, k):
dq, out = deque(), [] # indices, values decreasing
for i, x in enumerate(nums):
while dq and nums[dq[-1]] <= x:
dq.pop() # smaller values can never be a max again
dq.append(i)
if dq[0] <= i - k:
dq.popleft() # front index left the window
if i >= k - 1:
out.append(nums[dq[0]])
return out
vector<int> maxSlidingWindow(const vector<int>& nums, int k) {
deque<int> dq; // indices, values decreasing
vector<int> out;
for (int i = 0; i < (int)nums.size(); ++i) {
while (!dq.empty() && nums[dq.back()] <= nums[i]) dq.pop_back();
dq.push_back(i);
if (dq.front() <= i - k) dq.pop_front();
if (i >= k - 1) out.push_back(nums[dq.front()]);
}
return out;
}
Common mistakes
- Using a list as a queue in Python and paying O(n) per dequeue.
- Forgetting to expire indices that have left the window.
- Reading the front of an empty queue.
Quick check
Three questions on Queues. Get all three right to earn +15 XP.
-
Which traversal naturally uses a queue?
BFS processes nodes in the order they were discovered: first in, first out.
-
Why is list.pop(0) a poor way to dequeue in Python?
collections.deque gives O(1) popleft instead.
-
In the sliding-window maximum, the monotonic deque keeps:
The front is always the current maximum; smaller values behind a larger newcomer are dropped.
Challenges
Ordered from easiest to hardest. Solve them on LeetCode, then tick them off here. Know every concept and solve 3 to clear the level.
- Implement Queue using StacksLeetCode Easy +20
- Number of Recent CallsLeetCode Easy +20
- First Unique Character in a StringLeetCode Easy +20
- Design Circular QueueLeetCode Medium +40
- Dota2 SenateLeetCode Medium +40
- Sliding Window MaximumLeetCode Hard +70
- Shortest Subarray with Sum at Least KLeetCode Hard +70
Stuck on Queues?Ask Orbi for a hint, a fresh explanation or a review of your code.
Ask the tutor