jsschools

Queue

A FIFO (First-In, First-Out) abstract data type supporting enqueue at the back and dequeue from the front.

Spec ↗

Syntax

class Queue {
  #head = 0; #data = [];
  enqueue(val) { this.#data.push(val); }
  dequeue()    { return this.#data[this.#head++]; }
  peek()       { return this.#data[this.#head]; }
  get size()   { return this.#data.length - this.#head; }
}

Returns

Queue — A new Queue instance.

Examples

class Queue {
  #head = 0; #data = [];
  enqueue(val) { this.#data.push(val); }
  dequeue() {
    if (this.size === 0) return undefined;
    return this.#data[this.#head++];
  }
  peek() { return this.#data[this.#head]; }
  get size() { return this.#data.length - this.#head; }
  isEmpty() { return this.size === 0; }
}

// BFS shortest path in an unweighted graph
function bfs(graph, start, end) {
  const q = new Queue();
  const visited = new Set([start]);
  q.enqueue([start, 0]);
  while (!q.isEmpty()) {
    const [node, dist] = q.dequeue();
    if (node === end) return dist;
    for (const nb of graph[node] ?? []) {
      if (!visited.has(nb)) { visited.add(nb); q.enqueue([nb, dist + 1]); }
    }
  }
  return -1;
}
const g = { A: ['B', 'C'], B: ['D'], C: ['D'], D: [] };
console.log(bfs(g, 'A', 'D'));
Output 
2

const q = new Queue();
q.enqueue('first'); q.enqueue('second'); q.enqueue('third');
console.log(q.dequeue(), q.size);
Output 
first 2

Notes

| Operation | Best | Avg | Worst | Space | |----------|------|------|-------|-------| | Enqueue | O(1) | O(1) | O(1) | O(n) | | Dequeue | O(1) | O(1) | O(1) | O(1) | | Peek | O(1) | O(1) | O(1) | O(1) | Using `Array.shift()` for dequeue is O(n) due to element re-indexing. The `#head` pointer trick avoids shifting and keeps dequeue O(1) at the cost of growing the backing array — periodically compact when #head > half the array length. A doubly linked list gives strict O(1) without compaction.

See also