Queues

Think of it like this

Imagine the line at a coffee shop. The first person in line gets served first. New people join at the back. Nobody cuts the line. This is FIFO: First In, First Out.

← dequeue (served)        enqueue (joins) →
 
[person A][person B][person C][person D]
   FRONT                         REAR

Contrast with a stack (last in, first out — like cutting the line). A queue is the "fair" version.

Variants

Variant	Description	Use case
Simple Queue	FIFO, unlimited size	BFS, task processing
Circular Queue	Fixed-size ring buffer, head wraps around	Audio buffers, sliding windows
Deque (Double-Ended)	Insert/delete at both ends	Sliding window maximum, undo/redo
Priority Queue	Dequeue returns highest priority item	Dijkstra, task scheduling (→ uses a Heap)

Circular Queue — Why It Matters

A naive array queue is wasteful: dequeue shifts everything left (O(n)). A circular buffer fixes this with two pointers (head, tail) that wrap around:

Initial:  [_, _, _, _, _]   head=0, tail=0
Enqueue A: [A, _, _, _, _]  head=0, tail=1
Enqueue B: [A, B, _, _, _]  head=0, tail=2
Dequeue → A: [_, B, _, _, _]  head=1, tail=2  ← no shifting!
Enqueue C: [_, B, C, _, _]  head=1, tail=3
Enqueue D,E: [_, B, C, D, E]  head=1, tail=0  ← wrapped around!

class CircularQueue {
  constructor(capacity) {
    this.data = new Array(capacity + 1);
    this.head = 0;
    this.tail = 0;
    this.cap = capacity + 1; // +1 sentinel to distinguish full vs empty
  }
 
  enqueue(val) {
    if (this.isFull()) throw new Error('Queue full');
    this.data[this.tail] = val;
    this.tail = (this.tail + 1) % this.cap;
  }
 
  dequeue() {
    if (this.isEmpty()) throw new Error('Queue empty');
    const val = this.data[this.head];
    this.head = (this.head + 1) % this.cap;
    return val;
  }
 
  peek()     { return this.isEmpty() ? null : this.data[this.head]; }
  isEmpty()  { return this.head === this.tail; }
  isFull()   { return (this.tail + 1) % this.cap === this.head; }
  size()     { return (this.tail - this.head + this.cap) % this.cap; }
}

Time Complexity

Operation	Naive Array	Circular Buffer	Linked List
Enqueue	O(1) amortized	O(1)	O(1)
Dequeue	O(n) (shift!)	O(1)	O(1)
Peek front	O(1)	O(1)	O(1)

Key insight: Array.prototype.shift() in JavaScript is O(n) because it moves all remaining elements. For real queue usage, either use a linked list or a circular buffer.

Simple Linked-List Queue

class Queue {
  #head = null;
  #tail = null;
  #size = 0;
 
  enqueue(val) {
    const node = { val, next: null };
    if (this.#tail) this.#tail.next = node;
    else this.#head = node;
    this.#tail = node;
    this.#size++;
  }
 
  dequeue() {
    if (!this.#head) return null;
    const val = this.#head.val;
    this.#head = this.#head.next;
    if (!this.#head) this.#tail = null;
    this.#size--;
    return val;
  }
 
  peek()    { return this.#head?.val ?? null; }
  isEmpty() { return this.#size === 0; }
  size()    { return this.#size; }
}

Queue (Task Processing)

1 / 3

Task1

[0]

↑ FRONT

Task2

[1]

Task3

[2]

↑ REAR

A simple queue of async tasks. Elements are dequeued from the FRONT and enqueued at the REAR.

Core Patterns

Pattern 1 — BFS (Breadth-First Search)

BFS explores nodes level by level, using a queue to remember which nodes to visit next. This is how you find the shortest path in an unweighted graph.

Graph:  A ─── B ─── D
        │     │
        C ─── E
 
BFS from A:
Level 0: [A]         → visit A, enqueue B, C
Level 1: [B, C]      → visit B, enqueue D, E;  visit C (E already queued)
Level 2: [D, E]      → visit D; visit E
 
Order: A → B → C → D → E
Shortest path to D: A → B → D (2 steps)

function bfs(graph, start) {
  const visited = new Set([start]);
  const queue = [start];
  const dist = { [start]: 0 };
 
  while (queue.length) {
    const node = queue.shift(); // ← dequeue from front
    for (const neighbor of (graph[node] ?? [])) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        dist[neighbor] = dist[node] + 1;
        queue.push(neighbor); // ← enqueue at back
      }
    }
  }
  return dist;
}

Pattern 2 — Multi-Source BFS

Start BFS from multiple sources simultaneously. All sources are enqueued at level 0. Used for problems like "rotting oranges" (multiple rot sources spread simultaneously) or "walls and gates" (multiple gates flood-fill simultaneously).

function wallsAndGates(rooms) {
  const GATE = 0, EMPTY = Infinity;
  const queue = [];
  // Enqueue all gates simultaneously
  for (let r = 0; r < rooms.length; r++)
    for (let c = 0; c < rooms[0].length; c++)
      if (rooms[r][c] === GATE) queue.push([r, c]);
 
  const dirs = [[0,1],[0,-1],[1,0],[-1,0]];
  while (queue.length) {
    const [r, c] = queue.shift();
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nr >= rooms.length || nc < 0 || nc >= rooms[0].length
          || rooms[nr][nc] !== EMPTY) continue;
      rooms[nr][nc] = rooms[r][c] + 1; // dist from nearest gate
      queue.push([nr, nc]);
    }
  }
}

Pattern 3 — Monotonic Deque (Sliding Window Maximum)

A deque (double-ended queue) maintains indices in decreasing order of their values. For each new element, remove indices from the back that are smaller (they'll never be the max while this element is in the window). Remove indices from the front that left the window.

arr=[3,1,2,5,1], k=3
 
Window [3,1,2]: deque=[0(val3), 2(val2)] → max=arr[0]=3
Window [1,2,5]: deque=[3(val5)]           → max=arr[3]=5
Window [2,5,1]: deque=[3(val5), 4(val1)] → max=arr[3]=5
 
Result: [3, 5, 5]

function maxSlidingWindow(nums, k) {
  const deque = []; // stores indices
  const result = [];
 
  for (let i = 0; i < nums.length; i++) {
    // Remove indices outside the window
    while (deque.length && deque[0] < i - k + 1) deque.shift();
    // Remove indices with smaller values (they'll never be max)
    while (deque.length && nums[deque[deque.length - 1]] < nums[i]) deque.pop();
    deque.push(i);
    // Window is full starting at index k-1
    if (i >= k - 1) result.push(nums[deque[0]]);
  }
  return result;
}

Real-World Frontend Application

Queues are the heartbeat of async JavaScript:

JavaScript Event Loop: The callback queue holds setTimeout/setInterval callbacks. The microtask queue holds Promise .then() callbacks — it's drained before the callback queue each tick
React Concurrent Mode: State updates are queued and prioritized. High-priority updates (user input, animations) jump ahead of low-priority ones (data fetching)
Webpack / Vite module graph building: BFS from entry points to discover all imported modules
Service Workers: Network requests are queued when offline and replayed (in order) when reconnected
WebSocket message handling: Incoming messages queue up for ordered processing

Common Mistakes

Mistake	Impact	Fix
Using `Array.shift()` for dequeue	O(n) per dequeue — catastrophic for BFS	Use a pointer or proper queue class
Confusing BFS (queue) with DFS (stack)	Gets wrong traversal order	Queue for level-order/shortest-path; stack for DFS
Not marking visited before enqueuing	Same node enqueued multiple times → infinite loop	Mark visited when you enqueue, not when you dequeue
Forgetting 0-1 BFS vs regular BFS	Regular BFS only works for unit-weight graphs	For 0/1 weights: use deque; for arbitrary weights: Dijkstra

Key Problems to Solve

#	Problem	Pattern	Difficulty
1	Implement Stack Using Queues	Two queues	Easy
2	Binary Tree Level Order Traversal	BFS	Medium
3	Rotting Oranges	Multi-source BFS on grid	Medium
4	Number of Islands	BFS/DFS on grid	Medium
5	Walls and Gates	Multi-source BFS	Medium
6	Shortest Path in Binary Matrix	BFS	Medium
7	Sliding Window Maximum	Monotonic deque	Hard
8	Word Ladder	BFS + word set	Hard
9	Jump Game IV	BFS on graph of indices	Hard
10	Open the Lock	BFS over state space	Medium

Variant

Description

Use case

Simple Queue

FIFO, unlimited size

BFS, task processing

Circular Queue

Fixed-size ring buffer, head wraps around

Audio buffers, sliding windows

Deque (Double-Ended)

Insert/delete at both ends

Sliding window maximum, undo/redo

Priority Queue

Dequeue returns highest priority item

Dijkstra, task scheduling (→ uses a Heap)

Initial: [_, _, _, _, _] head=0, tail=0 Enqueue A: [A, _, _, _, _] head=0, tail=1 Enqueue B: [A, B, _, _, _] head=0, tail=2 Dequeue → A: [_, B, _, _, _] head=1, tail=2 ← no shifting! Enqueue C: [_, B, C, _, _] head=1, tail=3 Enqueue D,E: [_, B, C, D, E] head=1, tail=0 ← wrapped around!

class CircularQueue { constructor(capacity) { this.data = new Array(capacity + 1); this.head = 0; this.tail = 0; this.cap = capacity + 1; // +1 sentinel to distinguish full vs empty } enqueue(val) { if (this.isFull()) throw new Error('Queue full'); this.data[this.tail] = val; this.tail = (this.tail + 1) % this.cap; } dequeue() { if (this.isEmpty()) throw new Error('Queue empty'); const val = this.data[this.head]; this.head = (this.head + 1) % this.cap; return val; } peek() { return this.isEmpty() ? null : this.data[this.head]; } isEmpty() { return this.head === this.tail; } isFull() { return (this.tail + 1) % this.cap === this.head; } size() { return (this.tail - this.head + this.cap) % this.cap; } }

Operation

Naive Array

Circular Buffer

Linked List

Enqueue

O(1) amortized

O(1)

Dequeue

O(n) (shift!)

O(1)

Peek front

O(1)

class Queue { #head = null; #tail = null; #size = 0; enqueue(val) { const node = { val, next: null }; if (this.#tail) this.#tail.next = node; else this.#head = node; this.#tail = node; this.#size++; } dequeue() { if (!this.#head) return null; const val = this.#head.val; this.#head = this.#head.next; if (!this.#head) this.#tail = null; this.#size--; return val; } peek() { return this.#head?.val ?? null; } isEmpty() { return this.#size === 0; } size() { return this.#size; } }

Graph: A ─── B ─── D │ │ C ─── E BFS from A: Level 0: [A] → visit A, enqueue B, C Level 1: [B, C] → visit B, enqueue D, E; visit C (E already queued) Level 2: [D, E] → visit D; visit E Order: A → B → C → D → E Shortest path to D: A → B → D (2 steps)

function bfs(graph, start) { const visited = new Set([start]); const queue = [start]; const dist = { [start]: 0 }; while (queue.length) { const node = queue.shift(); // ← dequeue from front for (const neighbor of (graph[node] ?? [])) { if (!visited.has(neighbor)) { visited.add(neighbor); dist[neighbor] = dist[node] + 1; queue.push(neighbor); // ← enqueue at back } } } return dist; }

arr=[3,1,2,5,1], k=3 Window [3,1,2]: deque=[0(val3), 2(val2)] → max=arr[0]=3 Window [1,2,5]: deque=[3(val5)] → max=arr[3]=5 Window [2,5,1]: deque=[3(val5), 4(val1)] → max=arr[3]=5 Result: [3, 5, 5]

function maxSlidingWindow(nums, k) { const deque = []; // stores indices const result = []; for (let i = 0; i < nums.length; i++) { // Remove indices outside the window while (deque.length && deque[0] < i - k + 1) deque.shift(); // Remove indices with smaller values (they'll never be max) while (deque.length && nums[deque[deque.length - 1]] < nums[i]) deque.pop(); deque.push(i); // Window is full starting at index k-1 if (i >= k - 1) result.push(nums[deque[0]]); } return result; }

Mistake

Impact

Fix

Using Array.shift() for dequeue

O(n) per dequeue — catastrophic for BFS

Use a pointer or proper queue class

Confusing BFS (queue) with DFS (stack)

Gets wrong traversal order

Queue for level-order/shortest-path; stack for DFS

Not marking visited before enqueuing

Same node enqueued multiple times → infinite loop

Mark visited when you enqueue, not when you dequeue

Forgetting 0-1 BFS vs regular BFS

Regular BFS only works for unit-weight graphs

For 0/1 weights: use deque; for arbitrary weights: Dijkstra

Problem

Pattern

Difficulty

Implement Stack Using Queues

Two queues

Easy

Binary Tree Level Order Traversal

BFS

Medium

Rotting Oranges

Multi-source BFS on grid

Medium

Number of Islands

BFS/DFS on grid

Medium

Walls and Gates

Multi-source BFS

Medium

Shortest Path in Binary Matrix

BFS

Medium

Sliding Window Maximum

Monotonic deque

Hard

Word Ladder

BFS + word set

Hard

Jump Game IV

BFS on graph of indices

Hard

Open the Lock

BFS over state space

Medium

Queues

Queues#

Think of it like this

Variants

Circular Queue — Why It Matters

Time Complexity

Simple Linked-List Queue

Queue (Task Processing)

Core Patterns

Real-World Frontend Application

Common Mistakes

Key Problems to Solve

Queues

Queues#

Think of it like this

Variants

Circular Queue — Why It Matters

Time Complexity

Simple Linked-List Queue

Queue (Task Processing)

Core Patterns

Real-World Frontend Application

Common Mistakes

Key Problems to Solve

Queues

Queues