Queues

Lesson 1 of 2

Two ends, one direction

A queue uses both ends but each for one job only: enqueue adds at the back, dequeue removes from the front. That is FIFO, first in, first out, and it is the structure of fairness. Whoever waited longest goes next.

The distinction from a stack is not academic. Breadth-first search explores a graph level by level precisely because it uses a queue; swap in a stack and the same code becomes depth-first search, diving down one branch instead. Same algorithm skeleton, different structure, completely different traversal order.

Interactive lab

Queue operations

Enqueue and dequeue with the front and back markers tracked at every step.

Queue: first in, first out

enqueue / dequeue O(1)

value

frontback

1 / 2

Start

Peek reads the front item without removing it.

Continue

Lesson 2 of 2

The circular queue

The obvious array implementation is wrong in an interesting way. If dequeue removes index 0 and shifts everything left, the operation is O(n) and the queue's main selling point is gone. Move a front index forward instead and dequeue becomes O(1), but now the space at the start of the array is abandoned: after a few thousand operations the queue occupies the far end of a mostly empty block.

A circular queue fixes this by letting both indexes wrap around with modulo arithmetic. When back reaches the end of the array it continues at index 0, reusing the slots that dequeue freed. The array is never resized and nothing ever shifts, which is why fixed-capacity ring buffers are the standard choice in audio pipelines, network drivers and any embedded system where allocation during operation is unacceptable.

One detail is worth knowing before you implement one. When front equals back, the queue is either completely empty or completely full, and the indexes alone cannot tell you which. Implementations resolve this by tracking a count, or by deliberately leaving one slot empty so that full and empty look different.

Continue

Worked examples

Read the code, then change it

Copy any example into the playground and break it on purpose. That is the fastest way to learn what each line is holding up.

A queue without shiftingJavaScript

class Queue {
  constructor() {
    this.items = new Map();
    this.front = 0;
    this.back = 0;
  }
  enqueue(value) {
    this.items.set(this.back++, value);
  }
  dequeue() {
    if (this.front === this.back) return undefined;
    const value = this.items.get(this.front);
    this.items.delete(this.front++);
    return value; // O(1) -- no elements shift
  }
}

const q = new Queue();
q.enqueue('a'); q.enqueue('b');
console.log(q.dequeue(), q.dequeue());

Two ends, one direction

The circular queue

Read the code, then change it

Work these out yourself

Check your understanding

Finished this topic?