Queue

How a queue works

A queue tracks two ends: the front (where elements leave) and the rear (where new elements arrive). Operations:

• Enqueue — append to the rear.
• Dequeue — remove from the front and return it.
• Peek — read the front element without removing it.

The discipline of "always touch the same end for inserts, always the other end for removes" is what gives queues their FIFO property. The first thing in is the first thing out.

Three ways to implement a queue

	Linked list	Circular buffer (array)	Two stacks
Enqueue	O(1)	O(1)	O(1)
Dequeue	O(1)	O(1)	O(1) amortized
Memory layout	Scattered	Contiguous	Contiguous (×2)
Cache locality	Poor	Excellent	Excellent
Capacity	Unbounded	Fixed (without resize)	Unbounded
Best for	Variable size, simple impl	Fixed buffer (audio, packets)	Functional langs, interview Qs

Naive array queues — where you shift every element on dequeue — are O(n) per dequeue and the pattern in code reviews to flag. Don't use them. Either use a circular buffer (best for fixed-size) or a linked list (best for variable-size).

When to use a queue

• Breadth-first search. Any algorithm that processes "all level-N items before any level-(N+1) item" needs a queue. BFS, level-order tree traversal, shortest path on unweighted graphs.
• Message buffers. Producer-consumer patterns: producer enqueues messages as they arrive, consumer dequeues them in order. Network packets, log entries, OS interrupts.
• Task scheduling. Round-robin schedulers, print queues, request handlers. Whichever job arrived first runs first.
• Rate limiting and throttling. Sliding-window rate limiters use queues to track request timestamps.
• Streaming and pipelines. Each stage has an input queue; the previous stage enqueues, this stage dequeues. Backpressure is just "the queue filled up."

Pseudo-code (linked-list queue)

structure Queue:
    head = null
    tail = null

    enqueue(x):
        node = Node(x, next=null)
        if tail == null:
            head = tail = node
        else:
            tail.next = node
            tail = node

    dequeue():
        if head == null: error("empty")
        x = head.value
        head = head.next
        if head == null: tail = null
        return x

    peek():
        if head == null: error("empty")
        return head.value

JavaScript implementation (circular buffer)

class CircularQueue {
  constructor(capacity) {
    this.buf = new Array(capacity);
    this.cap = capacity;
    this.head = 0;
    this.tail = 0;
    this.size = 0;
  }
  enqueue(x) {
    if (this.size === this.cap) throw new Error('overflow');
    this.buf[this.tail] = x;
    this.tail = (this.tail + 1) % this.cap;
    this.size++;
  }
  dequeue() {
    if (this.size === 0) throw new Error('empty');
    const x = this.buf[this.head];
    this.buf[this.head] = undefined;
    this.head = (this.head + 1) % this.cap;
    this.size--;
    return x;
  }
  peek() { return this.size === 0 ? undefined : this.buf[this.head]; }
}

Python implementation

from collections import deque

# For 99% of Python code, just use deque — already a queue:
q = deque()
q.append(1)        # enqueue
q.append(2)
front = q.popleft()  # dequeue, returns 1

# Hand-rolled linked-list queue:
class Node:
    __slots__ = ('value', 'next')
    def __init__(self, v): self.value = v; self.next = None

class Queue:
    def __init__(self):
        self.head = self.tail = None
        self.size = 0
    def enqueue(self, x):
        node = Node(x)
        if self.tail: self.tail.next = node
        else:         self.head = node
        self.tail = node
        self.size += 1
    def dequeue(self):
        if not self.head: raise IndexError('empty')
        x = self.head.value
        self.head = self.head.next
        if not self.head: self.tail = None
        self.size -= 1
        return x

Famous queue problems

Queue using two stacks

class QueueFromStacks {
  constructor() { this.in = []; this.out = []; }
  enqueue(x) { this.in.push(x); }
  dequeue() {
    if (this.out.length === 0) {
      while (this.in.length) this.out.push(this.in.pop());
    }
    if (this.out.length === 0) throw new Error('empty');
    return this.out.pop();
  }
}

Each element is moved at most twice (in → out), so amortized O(1) per dequeue. A single dequeue can be O(n) if it triggers a transfer, but across n operations the total work is O(n).

Breadth-first search skeleton

function bfs(graph, start) {
  const visited = new Set([start]);
  const queue = [start];
  while (queue.length) {
    const node = queue.shift();  // dequeue
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);    // enqueue
      }
    }
  }
}

Note: Array.shift() is O(n) in JavaScript. For real production BFS on large graphs, use a deque or maintain a head index manually instead of shifting. The pattern is right; the implementation needs care.

Common bugs and edge cases

• Forgetting to update tail when the queue empties. If you dequeue the last element and don't reset tail = null, subsequent enqueues link onto a stale tail and the head/tail pointers diverge.
• Off-by-one in circular buffer modulo. Easy to confuse "size == cap" (full) with "head == tail" (empty or full?). Track size explicitly OR use head/tail with a one-slot-empty convention.
• O(n) dequeue from a naive array. If you implement dequeue as arr.shift(), every dequeue shifts every remaining element. The whole queue becomes O(n²) over n operations. Use a circular buffer or maintain a head index.
• Confusing queue and deque. A queue is FIFO; a deque is double-ended. If you find yourself wanting to insert at the front or remove from the back, you actually want a deque.
• Priority queue ≠ queue. Despite the name, a priority queue is a heap. Don't reach for it when you need FIFO — its ordering is by priority, not insertion time.