Queue and Deque (FIFO)

1. The mental model

A queue is a checkout line: new work joins at the back and old work leaves from the front. Its invariant is the front is the oldest unfinished item.

A deque (double-ended queue) lets both ends change. That extra power is useful when one rule expires old items at the front while another rule removes useless candidates at the back.

2. Queue vs stack decides traversal order

The container changes the meaning of the same traversal:

• Queue → BFS: process everything one edge away, then two edges away, then three.
• Stack → iterative DFS: process the newest discovered neighbour immediately and go deep.

That is why tree level order and shortest path in an unweighted graph need a queue. The first time BFS reaches a node, it has used the fewest edges possible.

3. Templates

queue<int> q;
q.push(start);
while (!q.empty()) {
    int cur = q.front(); q.pop();
    for (int next : neighbours(cur)) q.push(next);
}

const queue = [start];
let head = 0;
while (head < queue.length) {
  const current = queue[head++];
  for (const next of neighbours(current)) queue.push(next);
}

For a C++ deque, use deque<T> with push_front, push_back, pop_front, and pop_back. JavaScript has no built-in deque with guaranteed O(1) front operations; for most interview BFS, an array plus head index is the cleanest answer.

4. The monotonic deque connection

Sliding Window Maximum uses indices whose values decrease from front to back:

1. Pop expired indices from the front.
2. Pop smaller values from the back because the new value dominates them.
3. Push the new index at the back.
4. Read the maximum at the front.

Each index enters once and leaves once, so the total is O(n), even with inner while loops.

5. Traps

1. Using shift() repeatedly in JS. It can turn O(n) BFS into O(n²).
2. Marking visited on dequeue. Mark on enqueue; otherwise several parents can enqueue the same graph node.
3. Losing level boundaries. For level-order traversal, capture levelSize = queue.length - head before processing the level.
4. Confusing a deque with two pointers. A deque stores candidate history; two pointers only mark boundaries.

6. Learning gate

Draw the same five-node tree. Write down the order produced by a queue and by a stack. If the BFS order is not grouped by depth, revisit the invariant before starting graph problems.