EasyHigh Frequency20 min
Queue & Deque
Queue patterns including sliding window maximum using a monotonic deque.
Queue = FIFO. Use it for BFS, level-order traversal, scheduling, and sliding window maximum.
Queue — FIFO Structure
Operation Complexities
Operation
Time
Note
offer(x) / enqueue
O(1)
Add to rear
poll() / dequeue
O(1)
Remove from front
peek()
O(1)
View front without removing
BFS traversal
O(V+E)
Visit each node and edge once
Sliding window max
O(n)
Amortized via monotonic deque
Operations — Step by Step
BFS Level-Order
O(V+E)Capture queue.size() before the inner loop — it changes as children are enqueuedStep-by-step1 / 4
Processing order
Enqueue root (1)
Start: queue=[1]. Level 0 = root.