Queues

A queue is a line at a coffee shop. People join at the back and are served from the front — whoever waited longest goes first. This is First In, First Out (FIFO), the mirror image of a stack’s LIFO. Fairness is the mental model: nothing jumps the line.

Two operations run the show: enqueue adds to the back, dequeue removes from the front (with peek to read the front without removing). Both should be O(1). That "should" hides a classic trap — do it naively on a plain array and one of them becomes O(n).

The naive-array trap

If you back a queue with an array and dequeue by removing index 0, every remaining element shifts left by one — that’s O(n) per dequeue. The fix is to either use a linked list (with head and tail pointers) or a circular buffer that moves an index instead of shifting data.

The circular buffer

A circular buffer (ring buffer) gives you a fixed-size array where the front and back indices wrap around using modulo arithmetic. When the tail hits the end of the array, it loops back to index 0 — reusing freed slots instead of growing. This is how bounded queues, streaming buffers, and producer/consumer pipelines avoid endless allocation.

class CircularQueue {
  constructor(capacity) {
    this.buf = new Array(capacity)
    this.cap = capacity
    this.head = 0
    this.size = 0
  }
  enqueue(x) {
    if (this.size === this.cap) return false // full
    const tail = (this.head + this.size) % this.cap
    this.buf[tail] = x
    this.size++
    return true
  }
  dequeue() {
    if (this.size === 0) return undefined // empty
    const x = this.buf[this.head]
    this.head = (this.head + 1) % this.cap
    this.size--
    return x
  }
}

Queues power BFS

The reason queues matter for algorithms: breadth-first search is a queue in disguise. You explore a graph or tree level by level — enqueue a node’s unvisited neighbors, dequeue the next node to process. FIFO order guarantees you finish everything at distance k before touching distance k+1, which is exactly why BFS finds shortest paths in unweighted graphs.

function bfs(start, graph) {
  const visited = new Set([start])
  const queue = [start]
  const order = []
  while (queue.length) {
    const node = queue.shift() // dequeue (use a real queue in prod)
    order.push(node)
    for (const next of graph[node]) {
      if (!visited.has(next)) {
        visited.add(next)
        queue.push(next) // enqueue
      }
    }
  }
  return order
}

When to reach for a queue

• You need FIFO fairness — process items in the order they arrived.
• You’re running BFS or any level-order traversal.
• You’re buffering a stream between a fast producer and a slower consumer — a circular buffer bounds memory.
• You need both ends — a deque generalizes a queue and a stack, handy for sliding-window problems.