Queue
Core Concepts
Queue — a First-In-First-Out (FIFO) abstract data type where elements are inserted at the rear and removed from the front. O(1) enqueue and dequeue.
FIFO — the element that has been waiting longest is always removed first. The defining invariant of a queue.
Front — the end from which elements are removed (dequeued).
Rear / Back — the end to which elements are added (enqueued).
Deque (double-ended queue) — a generalization that supports O(1) push and pop at both ends. A standard queue and a stack are both specializations of a deque.
Monotonic deque — a deque maintained under a monotonicity constraint so that the front always holds the current window maximum or minimum. The canonical technique for sliding-window extremum problems.
Circular queue — a fixed-capacity queue backed by an array where head and tail wrap around using modular arithmetic, avoiding wasted space after dequeues.
Priority queue — an ordered queue where the element with the highest (or lowest) priority is dequeued first, regardless of insertion order. Implemented via a heap.
See hash-table.md for LRU cache, which combines a deque with a hash map. Priority queue full coverage is in a separate heap file.
Structural Invariants
| Invariant | What it guarantees | What breaks if violated |
|---|---|---|
| Insertion at rear only | FIFO ordering is preserved end-to-end | Inserting mid-queue produces incorrect service order |
| Removal at front only | The longest-waiting element is always next | Removing from the rear produces LIFO (stack) behavior |
Circular queue: size < capacity before enqueue | Array slot at tail is unoccupied | Writing to an occupied slot silently corrupts data |
| Monotonic deque: elements maintain monotone order front→back | Front always holds the window extremum | A non-monotone front gives wrong maximum/minimum answers |
| Monotonic deque: indices in deque fall within the current window | Stale extrema are never returned | Returning an out-of-window index produces wrong results |
Internal Representation
Linked-list-based — a singly linked list with a head pointer (front) and a tail pointer (rear). Enqueue appends a new node via tail; dequeue removes head. True O(1) worst-case with no capacity limit. Higher constant due to per-node heap allocation and pointer chasing.
Circular array — fixed-size array with head and tail integer indices. Enqueue: array[tail] = x; tail = (tail + 1) % capacity. Dequeue: x = array[head]; head = (head + 1) % capacity. O(1) operations, cache-friendly, zero allocation overhead. Capacity must be known upfront.
Two-stack simulation — one stack receives all enqueues; the other drives dequeues. When the dequeue stack empties, pour the enqueue stack into it (reversing order). Amortized O(1) per operation. Each element moves at most twice total. Used in the classic "implement queue using stacks" problem.
collections.deque (Python) — a doubly-linked list of fixed-size blocks. O(1) worst-case appendleft, append, popleft, pop. The correct choice for all queue and deque problems in Python; list pop(0) is O(n).
ArrayDeque (Java) — resizable circular array. Preferred over LinkedList for queue/deque use (better cache behavior) and over the legacy Queue/Stack wrappers.
Types / Variants
| Variant | What it is | When to use | Key property |
|---|---|---|---|
| Standard queue | FIFO with enqueue/dequeue/peek | BFS, task scheduling, any order-preserving buffer | O(1) all ops |
| Circular queue | Fixed-capacity array-backed queue | When capacity is bounded and allocation cost matters | Wrapping indices eliminate O(n) shift |
| Deque | Push/pop at both ends | Sliding window, palindrome checking, deque-based BFS | O(1) all four endpoint ops |
| Monotonic deque | Deque maintained monotone for window extrema | Sliding window maximum/minimum | Front = current window max/min; O(n) total across all windows |
| Priority queue | Heap-backed; dequeues by priority | Dijkstra, Prim, k-th largest, task scheduling by weight | O(log n) enqueue/dequeue, O(1) peek |
Topic-Specific Operations
enqueue(x) — O(1)
Add x to the rear. Linked list: allocate node, set tail.next = node, advance tail. Circular array: array[tail] = x; tail = (tail + 1) % cap; size += 1. For a deque, append (rear) or appendleft (front).
dequeue() — O(1)
Remove from the front. Linked list: save head.val, advance head. Circular array: val = array[head]; head = (head + 1) % cap; size -= 1. Guard against underflow (empty queue).
peek() / front() — O(1)
Read the front element without removing. Circular array: array[head]. Linked list: head.val. Must confirm non-empty before calling.
Monotonic deque — push(x, i) and prune(window_left)
Push: while the deque's back holds an index with value ≤ x (for a max-deque), pop it — x dominates those elements for all future windows. Then append index i.
Prune: while deque[0] < window_left, pop from the front — that index has expired.
Front of deque always holds the index of the current window maximum.
# max-deque maintenance inside a loop (i = current index, nums[i] = current value)
while dq and nums[dq[-1]] <= nums[i]:
dq.pop()
dq.append(i)
if dq[0] < i - k + 1:
dq.popleft()
Two-stack queue — enqueue / dequeue
Enqueue: push onto inbox. Dequeue: if outbox is empty, pour all of inbox into outbox (reversing order); pop from outbox.
Key Algorithms
Breadth-First Search (BFS)
Explores a graph level by level by enqueuing all neighbors of the current node before moving deeper. Guarantees shortest path in unweighted graphs because nodes are processed in non-decreasing distance order. O(V + E) time, O(V) space (queue holds at most one level at a time in trees; up to O(V) in dense graphs).
See breadth-first-search.md for full BFS coverage.
Sliding Window Maximum (Monotonic Deque)
Maintain a max-deque of indices over a window of size k. For each new element: pop all back-indices with smaller values (they can never be the window max), append the new index, pop the front if it's outside the window. Front always holds the current window maximum. O(n) total — each index enters and leaves the deque exactly once.
Two-Stack Queue Simulation
Amortized O(1) per operation. The key insight: reversing a stack gives FIFO order. The outbox stack is a lazy reversal of inbox; it is only refilled when it empties, so each element is moved at most once.
Level-Order Tree Traversal
BFS on a binary tree where you track level boundaries. Enqueue the root; at each level, dequeue exactly len(queue) nodes (snapshot the size before the inner loop), process them, enqueue their children. Produces a list of lists grouped by depth. O(n) time, O(n) space (last level can hold n/2 nodes).
Advanced Techniques
Monotonic Deque for Window Queries
What it solves: any sliding-window problem asking for the extremum (max, min, or a function thereof) over every window of size k in O(n).
Core mechanism: maintain a deque of indices in decreasing order of their values (for max). The back of the deque holds index i only if no later index j > i with nums[j] >= nums[i] has been added yet. When a new element arrives it evicts all dominated back-elements. The front is pruned of out-of-window indices. Front = window max at every step.
When to use over alternatives: use when the window size is fixed and you need every window's extremum. A segment tree or sparse table also gives O(1) per query but costs O(n log n) preprocessing and more code. Monotonic deque is O(n) end-to-end and simpler for fixed-size sliding windows. Do not use for variable-length windows where the shrink condition depends on the sum or count — sliding window with two pointers handles those.
Complexity: O(n) time, O(k) space.
Deque-Based BFS Variants (0-1 BFS)
What it solves: shortest path on graphs where edge weights are 0 or 1, without the O((V+E) log V) cost of Dijkstra.
Core mechanism: use a deque instead of a plain queue. When relaxing a neighbor via a 0-weight edge, push to the front (it belongs to the current level). When relaxing via a 1-weight edge, push to the back. This preserves the invariant that the deque is always sorted by tentative distance.
When to use over alternatives: use when edge weights are exclusively 0 or 1, and you need O(V + E) instead of O((V+E) log V). For arbitrary non-negative weights, use Dijkstra.
Complexity: O(V + E) time, O(V) space.
Problem Taxonomy
By Problem Category
| Problem type | What it asks | Key technique |
|---|---|---|
| BFS shortest path | Minimum steps/moves in an unweighted graph or grid | Standard BFS with visited set |
| Level-order grouping | Process nodes level by level, return per-level results | BFS with level-size snapshot |
| Sliding window extremum | Max or min over every window of size k | Monotonic deque |
| Design: queue from stacks | Implement FIFO using only stack operations | Two-stack simulation |
| Design: circular buffer | Fixed-capacity queue with O(1) ops | Circular array with head/tail indices |
| Task scheduling / ordering | Process tasks respecting dependencies or cooldowns | Queue + simulation; sometimes priority queue |
| Stream median / k-th element | Maintain order statistics on a stream | Two heaps (not plain queue) |
| Multi-source BFS | Shortest distance from any of multiple starting points | Initialize queue with all sources simultaneously |
Problem Signal → Technique
| Signal in problem | Likely technique |
|---|---|
| "minimum steps", "shortest path", unweighted grid | BFS |
| "level by level", "return nodes at each depth" | BFS with level-size snapshot |
| "sliding window of size k", "maximum in every window" | Monotonic deque |
| "implement queue using stacks" | Two-stack simulation |
| "design circular queue" | Circular array |
| "rotten oranges", "walls and gates", "nearest X" | Multi-source BFS |
| "cooldown", "task scheduler", "CPU scheduling" | Queue + frequency map simulation |
| "01 matrix", "distance to nearest 0" | Multi-source BFS |
| "minimum knight moves", "jump game" with grid | BFS |
Common Patterns
| Pattern | When it applies | Mechanism |
|---|---|---|
| Multi-source BFS | Multiple start points; want distance from nearest source | Enqueue all sources at distance 0 before the BFS loop begins |
| Level-size snapshot | Need to group output by BFS depth | Capture n = len(queue) at start of each outer loop iteration; inner loop runs exactly n times |
| Visited set before enqueue | Avoid re-processing nodes in BFS | Mark and add to visited when enqueuing, not when dequeuing; prevents duplicates in queue |
| Deque as both-ends buffer | Need to cheaply add to front and back | Use collections.deque; never use list with insert(0,...) (O(n)) |
| Lazy reversal (two stacks) | Amortized O(1) queue from two stacks | Pour inbox into outbox only when outbox is empty; cost is amortized over all operations |
| State encoding in BFS | Visited set for complex states (grids with keys, etc.) | Encode full state as a tuple; use a set of tuples for visited |
Edge Cases & Pitfalls
-
Marking visited on dequeue instead of enqueue — the same node can be enqueued multiple times before being processed, causing redundant work or incorrect shortest-path counts. Mark visited immediately when enqueuing.
-
list.pop(0)in Python — O(n) because all elements shift left. Usecollections.dequewithpopleft()for O(1). This is a silent O(n²) bottleneck in BFS on large inputs. -
Circular queue off-by-one — distinguishing a full queue (
size == capacity) from an empty one (size == 0) when head == tail. Tracksizeexplicitly or leave one slot unused as a sentinel; do not rely solely on thehead == tailcondition. -
Monotonic deque: forgetting to prune expired front — after advancing the window, the front index may be outside
[i - k + 1, i]. Not pruning returns a stale maximum. Checkdq[0] < i - k + 1each step. -
Monotonic deque: strict vs. non-strict inequality on eviction — using
<instead of<=leaves duplicate values in the deque, which is harmless for correctness but allows unnecessary elements. For lexicographically smallest results, the choice matters. -
Forgetting to handle the empty-queue case in two-stack simulation — dequeue should pour only when
outboxis empty, not on every call; pouring into a non-emptyoutboxcorrupts FIFO order. -
BFS on a grid: re-visiting cells — adding
(r, c)to visited only when popping allows the same cell to be enqueued multiple times, inflating the queue and giving wrong distances. Add to visited when pushing. -
Integer overflow in circular queue index arithmetic — in languages without arbitrary-precision integers,
(tail + 1) % capacityis safe, but computinghead + sizewithout modular reduction can overflow for large capacity values.
Implementation Notes
- Python
collections.dequeis the correct queue type;queue.Queueis thread-safe but has synchronization overhead — avoid it in single-threaded LeetCode solutions. - Java: prefer
ArrayDequeoverLinkedListas a queue;LinkedListallocates per-node and has worse cache behavior. - Java:
ArrayDequedoes not allownullelements — store sentinel values instead. - Python
deque(maxlen=k)automatically evicts from the opposite end when the deque is full — useful for fixed-size windows but dangerous for monotonic-deque logic where eviction must be conditional. - Recursion depth limit does not affect queue-based BFS (iterative by nature), unlike DFS.
- For 0-1 BFS, a plain
dequesuffices; do not reach forheapqwhen all weights are 0 or 1.
Cross-Topic Relations
| Related topic | Specific connection |
|---|---|
| Stack | Two-stack simulation of a queue; deque generalizes both. Monotonic stack solves "next greater element"; monotonic deque solves sliding-window extremum |
| BFS / Graph traversal | Queue is the core data structure driving BFS; BFS correctness depends on FIFO order |
| Trees | Level-order traversal is BFS on a tree using a queue |
| Heap / Priority Queue | Priority queue replaces plain queue when processing order depends on weight, not arrival time (Dijkstra, Prim) |
| Sliding Window | Two-pointer sliding window handles sum/count conditions; monotonic deque handles extremum conditions — know which to reach for |
| Hash Table | LRU cache combines a deque (or doubly-linked list) with a hash map for O(1) access and O(1) eviction |
| Dynamic Programming | BFS on a DAG of DP states can be framed as topological-order processing via a queue (Kahn's algorithm) |
Interview Reference
Must-Know Problems
BFS / Shortest Path
- Number of Islands (medium) — multi-source flood fill
- Rotting Oranges (medium) — multi-source BFS with time simulation
- 01 Matrix (medium) — multi-source BFS from all zeros
- Word Ladder (hard) — BFS on implicit graph of word states
- Minimum Knight Moves (medium) — BFS on grid with symmetry optimization
Level-Order Traversal
- Binary Tree Level Order Traversal (medium) — canonical level-snapshot BFS
- Binary Tree Zigzag Level Order Traversal (medium) — alternate direction per level
- Populating Next Right Pointers (medium) — BFS with O(1) space using existing pointers
Sliding Window with Deque
- Sliding Window Maximum (hard) — monotonic deque template problem
- Jump Game VI (medium) — DP + monotonic deque on window of size k
- Constrained Subsequence Sum (hard) — DP + deque with variable window
Design
- Design Circular Queue (medium) — circular array implementation
- Implement Queue using Stacks (easy) — two-stack simulation
- Design Hit Counter (medium) — sliding-window queue over timestamps
Clarification Questions to Ask
- "Is the graph/grid guaranteed to be connected, or can there be unreachable nodes?"
- "Should I return the path itself or just its length?"
- "For sliding window max: what should I return when the array length is less than k?"
- "For circular queue: what should enqueue return when the queue is full — false or throw?"
- "Are there negative edge weights?" — if yes, BFS does not give shortest paths; need Dijkstra or Bellman-Ford.
Common Interview Mistakes
- Using a
listinstead ofdequefor BFS in Python, producing O(n²) due topop(0). - Marking nodes visited on dequeue rather than enqueue, causing duplicate queue entries and inflated distances.
- Initializing the BFS queue with only one source when the problem has multiple starting points (Rotting Oranges, 01 Matrix).
- Forgetting to prune the monotonic deque's front for out-of-window indices, returning stale extrema.
- Building a circular queue with
head == tailas the only empty/full discriminator, making the two states indistinguishable. - Pouring the inbox stack into a non-empty outbox in the two-stack queue, corrupting FIFO order.
Typical Follow-Up Escalations
- "Now find the shortest path and return it (not just its length)." — Track parent pointers during BFS; backtrack from target to source.
- "The grid has weighted edges (0 or 1)." — Switch from plain BFS to 0-1 BFS with a deque.
- "Now do this in O(1) extra space." — For trees, use the existing
nextpointers (Populating Next Right Pointers II); for BFS this is generally infeasible. - "What if k changes per query?" — Static sparse table or segment tree beats repeated monotonic deque construction.
- "Make the queue thread-safe." — Add a mutex around enqueue/dequeue; or use Python
queue.Queue/ JavaBlockingQueue.
Read Next
Start reading to get personalized recommendations
Explore Unread
Great job! You've read all available articles