Queues

If a stack is "last-in-first-out", a queue is the polite, fair-minded sibling: first-in-first-out. The first element you put in is the first one out. Every time you've waited in a line, queued a print job, or watched a video buffer, you've used a queue. In code, queues power level-by-level traversal, BFS for shortest paths, task schedulers, and producer-consumer pipelines.

What a Queue Actually Is

A queue has two ends. New elements enter at the rear (also called *tail*); old elements leave from the front (also called *head*).

\\\` enqueue(1), enqueue(2), enqueue(3) front [1, 2, 3] rear

dequeue() → 1 front [2, 3] rear enqueue(4) front [2, 3, 4] rear \\\`

Three core operations:

• \enqueue(x)\ — add x to the rear.
• \dequeue()\ — remove and return the front element.
• \peek()\ / \front()\ — look at the front without removing.

Real Analogies

• Tickets / supermarket checkout — first person in line is served first.
• Print queue — pages print in submission order.
• Streaming video buffer — the bytes that arrived first play first.
• OS task / message queues — Kafka, RabbitMQ, web request queues, OS I/O scheduling.
• CPU round-robin scheduling — each process waits its turn fairly.

Implementing a Queue (and the Trap)

The naive array approach almost works:

\\\`js class BadQueue { constructor() { this.data = []; } enqueue(x) { this.data.push(x); } dequeue() { return this.data.shift(); } // O(n) — shifts everything! } \\\`

\Array.shift()\ is O(n) because it slides every remaining element one index to the left. For 10 enqueues + 10 dequeues this is fine; for 10⁶ it's a disaster. Two real fixes:

1. Linked-list-backed queue — head pointer for dequeue, tail pointer for enqueue. Both O(1).

2. Circular array (the production choice) — keep a fixed array, track \front\ and \rear\ indices that wrap around using \% capacity\. Both O(1), and cache-friendly.

\\\`js class CircularQueue { constructor(cap) { this.arr = new Array(cap); this.cap = cap; this.front = 0; this.rear = 0; this.size = 0; } enqueue(x) { if (this.size === this.cap) throw new Error('full'); this.arr[this.rear] = x; this.rear = (this.rear + 1) % this.cap; this.size++; } dequeue() { if (this.size === 0) throw new Error('empty'); const v = this.arr[this.front]; this.front = (this.front + 1) % this.cap; this.size--; return v; } } \\\`

Visualised:

\\\` [ _ _ 3 4 5 _ _ ] capacity 7 ↑ ↑ front rear \\\`

After many enqueues, \rear\ wraps around and might be *behind* \front\ in the array — that's the whole point of "circular".

Daily Operations and Costs

Operation	Time
---	:---:
\enqueue\	O(1)
\dequeue\	O(1)
\front\ / \peek\	O(1)
\isEmpty\ / \size\	O(1)
search	O(n)

Beginner Mistakes to Skip

1. Using \Array.shift()\ in JS for dequeue. Looks O(1), is actually O(n). Use a custom queue or a head index. 2. Using Python \list.pop(0)\. Same problem — O(n). Always use \collections.deque\ (\popleft()\ is O(1)). 3. Confusing front and rear. Enqueue at rear, dequeue from front. Always. 4. Forgetting to handle empty. \dequeue\ on an empty queue should error or return a sentinel — never silently corrupt state. 5. Treating queue like a stack for BFS. If you pop from the *back*, you've written DFS by accident. 6. Reinventing it from scratch in production. Java has \ArrayDeque\, Python has \collections.deque\, C++ has \std::queue\. Use them.

Intermediate: BFS Is Just a Queue Loop

Breadth-First Search is the canonical reason queues exist in algorithm code. The skeleton:

\\\`js function bfs(start, neighbors) { const visited = new Set([start]); const queue = [start]; // pretend O(1) shift while (queue.length) { const node = queue.shift(); process(node); for (const n of neighbors(node)) { if (!visited.has(n)) { visited.add(n); queue.push(n); } } } } \\\`

This single loop solves:

• Shortest path in unweighted graphs — first time you reach the target is the shortest.
• Level-order traversal of a tree.
• "Number of islands" in a grid (BFS from each land cell).
• "Rotting oranges" / multi-source BFS — push *all* sources in initially.
• Topological sort via Kahn's algorithm.

The deep reason BFS finds shortest paths in unweighted graphs: the queue guarantees you finish all distance-d nodes before starting any distance-(d+1) node.

Intermediate: Level-Order Tree Traversal

To process a tree level by level, snapshot the queue size at the start of each iteration:

\\\`js function levelOrder(root) { if (!root) return []; const out = []; const q = [root]; while (q.length) { const levelSize = q.length; const level = []; for (let i = 0; i < levelSize; i++) { const node = q.shift(); level.push(node.val); if (node.left) q.push(node.left); if (node.right) q.push(node.right); } out.push(level); } return out; } \\\`

This single trick — *grab \q.length\ before the inner loop* — is the difference between "BFS" and "level-aware BFS".

Intermediate: Deque (Double-Ended Queue)

A deque lets you add and remove from either end in O(1). It's a generalisation that subsumes both stack and queue.

Operation	Time
---	:---:
\addFirst\ / \addLast\	O(1)
\removeFirst\ / \removeLast\	O(1)
\peekFirst\ / \peekLast\	O(1)	In Java that's \ArrayDeque\, in Python \collections.deque\, in C++ \std::deque\. Use it when you need a queue *and* might also want stack-like access on the other side. Intermediate: Priority Queue Is Not Really a Queue A priority queue dequeues by priority, not arrival order. The standard implementation is a binary heap (covered in its own topic):	Implementation	Insert	Extract-min	Peek
---	:---:	:---:	:---:
Unsorted array	O(1)	O(n)	O(n)
Sorted array	O(n)	O(1)	O(1)
Binary heap	O(log n)	O(log n)	O(1)

In Java: \PriorityQueue\. In Python: \heapq\. In C++: \std::priority_queue\. The name "queue" is misleading — internally it's a heap, semantically it's "extract-best". Don't use it when you actually want FIFO order.

Advanced: Queue from Two Stacks

Classic interview puzzle: implement a queue using only stacks. Use \inStack\ for enqueue and \outStack\ for dequeue:

• Enqueue: push to \inStack\ — O(1).
• Dequeue: if \outStack\ is empty, pop everything from \inStack\ and push into \outStack\ (this reverses the order). Then pop from \outStack\.

Each element moves at most twice → amortised O(1).

Advanced: Monotonic Deque for Sliding Window

The pattern that turns a "for each window of size k, find the max" problem from O(n × k) into O(n).

\\\`js function maxSlidingWindow(arr, k) { const dq = []; // stores indices, values strictly decreasing const out = []; for (let i = 0; i < arr.length; i++) { while (dq.length && dq[0] <= i - k) dq.shift(); // drop expired while (dq.length && arr[dq[dq.length-1]] <= arr[i]) dq.pop(); // drop weaker dq.push(i); if (i >= k - 1) out.push(arr[dq[0]]); } return out; } \\\`

The deque always has the current candidates for the window's max, in decreasing order. Each index is pushed and popped at most once → linear total.

This same skeleton solves: "sliding window minimum", "first negative integer in every window", and many "shortest subarray with sum at least k" variants.

Advanced: Producer-Consumer Pattern

Queues are the backbone of concurrent systems:

\\\` [Producer] → enqueue → [Buffer Queue] → dequeue → [Consumer] \\\`

The queue decouples the rate at which producers create work from the rate at which consumers process it. Crucial for:

• Web servers — incoming requests queue up while workers handle them.
• Message brokers — Kafka, RabbitMQ, SQS, Redis Streams.
• Thread pools — pending tasks in a shared queue.
• OS I/O scheduling — disk read requests in a queue.

When your queue is unbounded and producers are faster than consumers, you eventually run out of memory. That's why production queues are usually bounded with a backpressure policy (block, drop, or fail-fast).

Advanced: When NOT to Use a Queue

Situation	Better choice
LIFO order needed	stack
Random access by index	array
Sorted insertion	balanced BST / skiplist
Top-k by priority	heap / priority queue
Many delete-from-middle	doubly linked list
Set membership ("seen this?")	hash set (often *with* a queue, not instead)

Practice Path

1. Implement a queue with O(1) enqueue and O(1) dequeue using either a circular array or a linked list with head + tail pointers. 2. Solve Implement Queue using Stacks (LC 232). Verify the amortised O(1) dequeue. 3. Solve Number of Islands (LC 200) using BFS and a queue. Compare with a DFS solution. 4. Solve Sliding Window Maximum (LC 239) with a monotonic deque. Trace it on \[1,3,-1,-3,5,3,6,7]\ with k = 3.