Queue

Overview

A queue is a First-In-First-Out (FIFO) collection. Items are added at the back (enqueue) and removed from the front (dequeue). The oldest waiting item is always served next.

Queues model anything that waits its turn: tasks, requests, messages. In algorithms, the queue is the engine of breadth-first search, which explores nodes in order of distance and therefore finds shortest paths in unweighted graphs.

When to use it

• Items must be processed in arrival order.
• Breadth-first search, level-order traversal, shortest steps.
• Buffering between a producer and a consumer.
• Sliding time windows: count events in the last N seconds.

Problem patterns it solves

Where it is used in real software

Key terms

enqueue / offer

Add to the back. O(1).

dequeue / poll

Remove from the front. O(1) with a proper implementation.

front / peek

Read the front item without removing it.

FIFO

First in, first out.

Head index

An index into an array marking the logical front, avoiding O(n) shift.

Implementing a queue efficiently

1. 1
   Avoid array.shift() in JavaScript

   shift re-indexes every element, making each dequeue O(n).

2. 2
   Use a head index

   Store items in an array, keep head pointing at the front, and increment it on dequeue.

3. 3
   Compact occasionally

   When head passes half the array length, slice off consumed items to reclaim memory.

4. 4
   In Java, use ArrayDeque

   offer, poll, and peek are O(1). LinkedList also works but is slower.

5. 5
   For fixed capacity, use a circular buffer

   Wrap indexes with modulo so freed slots are reused.

Number of recent calls (window of 3000 ms)

ping(t) returns how many pings happened in [t - 3000, t]

Old timestamps leave from the front because they are the oldest. Each timestamp is enqueued and dequeued once, so the total work is O(n).

Implementation

1class Queue {2  constructor() {3    this.items = [];4    this.head = 0;5  }6  enqueue(x) { this.items.push(x); }7  dequeue() {8    if (this.isEmpty()) return undefined;9    const x = this.items[this.head++];10    if (this.head > 1024 && this.head * 2 > this.items.length) {11      this.items = this.items.slice(this.head); // reclaim memory occasionally12      this.head = 0;13    }14    return x;15  }16  peek() { return this.items[this.head]; }17  get size() { return this.items.length - this.head; }18  isEmpty() { return this.size === 0; }19}20 21class RecentCounter {22  constructor() { this.q = new Queue(); }23  ping(t) {24    this.q.enqueue(t);25    while (this.q.peek() < t - 3000) this.q.dequeue();26    return this.q.size;27  }28}29 30// Queue from two stacks: amortized O(1)31class MyQueue {32  constructor() { this.input = []; this.output = []; }33  push(x) { this.input.push(x); }34  #shift() {35    if (this.output.length === 0) {36      while (this.input.length) this.output.push(this.input.pop());37    }38  }39  pop() { this.#shift(); return this.output.pop(); }40  peek() { this.#shift(); return this.output.at(-1); }41  empty() { return !this.input.length && !this.output.length; }42}

Complexity and performance

Trade-offs

Variants and related techniques

Common mistakes

• Using shift() in JavaScript BFS on large graphs.

  Fix: Use a head index or a real queue class.

• Using a queue when only the latest item matters.

  Fix: That is a stack problem (LIFO).

• Reading queue.size inside the level loop.

  Fix: Store the size before the loop; it changes as children are added.

Interview questions

Practice problems