Queue

How It Works

A queue is a linear collection where elements are added at one end (the "back" or "tail") and removed from the other end (the "front" or "head"): First In, First Out (FIFO). Think of a checkout line: whoever joined first gets served first. This ordering guarantee is the entire point of a queue, and it's what makes it the natural fit for breadth-first traversal, task scheduling, rate limiters, and any "process things in the order they arrived" problem.

Conceptually a queue only needs two operations:

• Enqueue: add an element to the back. O(1).
• Dequeue: remove and return the element at the front. O(1) with the right implementation.
• Peek/front: look at the front element without removing it. O(1).

The catch is implementation. A plain JavaScript array's push is O(1) amortized, but shift() is O(n) because every remaining element has to be re-indexed after the first one is removed. For small queues this doesn't matter, but in a hot loop (like BFS over a large graph) repeated shift() calls can quietly turn an O(n) algorithm into O(n²). The fix is either a proper circular buffer, a doubly linked list with head/tail pointers, or, the pragmatic interview move, an index pointer that walks forward through an array instead of physically removing elements.

// Array-backed queue with an index pointer: avoids O(n) shift()
class Queue {
  constructor() {
    this.items = [];
    this.head = 0; // pointer to the current front
  }

  enqueue(value) {
    this.items.push(value); // O(1) amortized
  }

  dequeue() {
    if (this.isEmpty()) return undefined;
    const value = this.items[this.head];
    this.head++; // O(1): no re-indexing
    return value;
  }

  peek() {
    return this.isEmpty() ? undefined : this.items[this.head];
  }

  isEmpty() {
    return this.head >= this.items.length;
  }
}

// Classic use case: BFS over a graph
function bfs(graph, start) {
  const visited = new Set([start]);
  const order = [];
  const queue = new Queue();
  queue.enqueue(start);

  while (!queue.isEmpty()) {
    const node = queue.dequeue();
    order.push(node);

    for (const neighbor of graph[node] ?? []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.enqueue(neighbor);
      }
    }
  }

  return order;
}

Common Mistakes

• Using Array.prototype.shift() in a loop: it's O(n) per call, which silently degrades BFS or level-order traversal to O(n²) on large inputs.
• Forgetting to mark nodes visited at enqueue time (not dequeue time): in graph BFS, if you mark visited only when dequeuing, the same node can be enqueued multiple times before it's processed once.
• Confusing queue (FIFO) with stack (LIFO): a surprisingly common slip under interview pressure, especially when translating recursive DFS into an iterative version.
• Not handling the empty-queue case: calling dequeue() or peek() without checking isEmpty() first and getting undefined propagated silently into later logic.
• Growing the backing array unboundedly: the index-pointer approach above never shrinks items; for long-lived queues you'd periodically slice off the consumed prefix.

Pattern Summary

Reach for a queue whenever the problem cares about processing order layer-by-layer or in arrival order: level-order tree traversal, BFS shortest-path problems, sliding-window maximum (with a deque), and task/event scheduling all lean on FIFO semantics. The edge it gives you in interviews is a clean, predictable way to explore "nearest things first," which is exactly what distinguishes BFS-shaped problems from DFS-shaped ones.