Chapter 10 — Queues & Deques
Chapter 10 — Queues & Deques
Hey everyone! Welcome back to Namaste DSA!
If a stack is a pile of plates, a queue is a line at a ticket counter: First In, First Out (FIFO). The first person to join is the first served. Queues are the engine behind BFS, task scheduling, and printer spools. We'll also meet the deque — a double-ended power tool.
What we will cover:
- FIFO and the core operations
- Why a naive array queue is slow (and the fix)
- Circular queue
- Deque — double-ended queue
- Queue as the engine of BFS
- Sliding window maximum (monotonic deque)
- Interview Questions
1. FIFO — First In, First Out
┌─────────────────────────────────────────────────────────────┐ │ QUEUE (line at a counter) │ ├─────────────────────────────────────────────────────────────┤ │ │ │ dequeue ← ┌───┬───┬───┬───┐ ← enqueue │ │ (front) │ A │ B │ C │ D │ (rear) │ │ └───┴───┴───┴───┘ │ │ ▲ ▲ │ │ front rear │ │ │ │ enqueue → add at rear dequeue → remove from front │ └─────────────────────────────────────────────────────────────┘
2. The Naive Array Queue Problem
Using a JS array: push to enqueue is O(1), but shift to dequeue is O(n) — it shifts every element left! For a fast queue, avoid shift.
┌─────────────────────────────────────────────────────────────┐ │ arr.push(x) → enqueue → O(1) ✔ │ │ arr.shift() → dequeue → O(n) ✗ (every element shifts) │ ├─────────────────────────────────────────────────────────────┤ │ FIX 1: use a linked list (head=front, tail=rear) → O(1) │ │ FIX 2: use a "head index" pointer instead of shifting │ └─────────────────────────────────────────────────────────────┘
// O(1) dequeue using a moving head index
class Queue {
constructor() { this.items = []; this.head = 0; }
enqueue(x) { this.items.push(x); }
dequeue() {
const x = this.items[this.head];
this.head++; // don't shift — just advance
return x;
}
isEmpty() { return this.head >= this.items.length; }
}
3. Circular Queue
A fixed-size queue that wraps around, reusing freed slots at the front. The rear index loops back to 0 using modulo.
capacity 5, after some enqueue/dequeue:
┌───┬───┬───┬───┬───┐
│ │ │ C │ D │ E │ rear wraps: (rear + 1) % capacity
└───┴───┴───┴───┴───┘
▲ ▲
rear front ← rear looped back to index 0/1
Modulo arithmetic (% capacity) is what makes the indices wrap without moving data — great for fixed-memory buffers.
4. Deque — Double-Ended Queue
A deque lets you add and remove from both ends in O(1). It's a stack and a queue at the same time.
addFront ← ┌───┬───┬───┐ → addRear
removeFront │ A │ B │ C │ removeRear
└───┴───┴───┘
All four operations O(1).
5. Queue as the Engine of BFS
Breadth-First Search explores level by level — and a queue is exactly what enforces that order. (Full BFS in Chapter 18; here's the shape.)
function bfsLevelOrder(start, getNeighbors) {
const queue = [start];
const visited = new Set([start]);
while (queue.length) {
const node = queue.shift(); // front
for (const n of getNeighbors(node)) {
if (!visited.has(n)) {
visited.add(n);
queue.push(n); // rear
}
}
}
}
6. Sliding Window Maximum (Monotonic Deque)
Find the max in every window of size k, in O(n). A monotonic deque stores indices in decreasing value order, so the front is always the current max.
function maxSlidingWindow(arr, k) {
const dq = []; // stores indices, values decreasing
const res = [];
for (let i = 0; i < arr.length; i++) {
// drop indices that left the window
if (dq.length && dq[0] <= i - k) dq.shift();
// drop smaller values from the back — they're useless
while (dq.length && arr[dq[dq.length - 1]] < arr[i]) dq.pop();
dq.push(i);
if (i >= k - 1) res.push(arr[dq[0]]); // front = max
}
return res;
}
// O(n) — each index enters and leaves the deque once.
Interview Questions — Quick Fire!
Q: What's the difference between a stack and a queue?
"A stack is LIFO — last in, first out, add and remove from the same end. A queue is FIFO — first in, first out, add at the rear and remove from the front. Stacks suit undo and DFS; queues suit scheduling and BFS."
Q: Why shouldn't you use array.shift() for a queue?
"Because shift() removes from the front by moving every remaining element one slot left, which is O(n). For an efficient queue, use a linked list or keep a head index that you increment instead of shifting — both give O(1) dequeue."
Q: What is a circular queue and why use one?
"A fixed-size queue where the rear index wraps back to the start using modulo, reusing slots freed by dequeues. It avoids wasted space and shifting, which is ideal for bounded buffers like streaming or hardware queues."
Q: What is a deque?
"A double-ended queue that supports O(1) insertion and removal at both the front and the back. It generalizes both stacks and queues, and a monotonic deque solves sliding-window-maximum in O(n)."
Q: Why does BFS use a queue?
"Because BFS must visit nodes in the order they were discovered, level by level. A FIFO queue naturally enforces that — you dequeue the earliest-discovered node before any discovered later."
Quick Recap
| Concept | Key Takeaway |
|---|---|
| FIFO | First in, first out. |
| enqueue/dequeue | Add rear, remove front. |
| Avoid shift() | O(n); use head index or linked list. |
| Circular queue | Wrap with modulo, reuse slots. |
| Deque | O(1) both ends. |
| BFS engine | Queue enforces level order. |
What's Next?
That completes Season 2 — Patterns! Next is Season 3 — Searching & Sorting, starting with Chapter 11: Binary Search — the O(log n) superpower (plus the advanced "binary search on the answer" trick).
Keep coding, keep grinding! See you in the next one!
Post a Comment