Back to Catalog
Data Structures
FIFO
Queues
FIFO — first in, first out. Enqueue at back, dequeue from front. O(1) both ends.
Intent & Description
Real-world Use Case
BFS graph traversal — enqueue start node, dequeue to visit, enqueue unvisited neighbors. Node.js event loop — I/O callbacks enqueued, dequeued in arrival order. Print spooler — jobs printed in submission order. Rate limiter — sliding window of request timestamps in a queue.
Source
📌 TL;DR
Queue = FIFO, O(1) enqueue and dequeue. Never use array.shift() — it is O(n). Back with a linked list or ring buffer. The natural structure for BFS, task queues, and event loops.
Advantages
- O(1) enqueue and dequeue when implemented correctly (linked list or ring buffer)
- Preserves strict ordering — FIFO is a natural fit for fairness-sensitive workloads
- Models real-world waiting lines, task queues, and message buffers exactly
- Simple invariant — process in arrival order, no priority logic needed
Disadvantages
- No random access — only front element is accessible without dequeuing
- Linked list backing means pointer overhead and poor cache performance vs arrays
- Array-backed queues with shift() are O(n) — a common performance trap in JS
- Unbounded queues can grow without limit — add capacity bounds in production
Implementation Example
// ─── Queue backed by doubly linked list (true O(1) dequeue) ──
class QueueNode {
constructor(value) { this.value = value; this.next = null; }
}
class Queue {
#head = null;
#tail = null;
#size = 0;
// O(1) — Add to back
enqueue(value) {
const node = new QueueNode(value);
if (!this.#tail) {
this.#head = this.#tail = node;
} else {
this.#tail.next = node;
this.#tail = node;
}
this.#size++;
}
// O(1) — Remove from front
dequeue() {
if (!this.#head) return null;
const val = this.#head.value;
this.#head = this.#head.next;
if (!this.#head) this.#tail = null;
this.#size--;
return val;
}
peek() { return this.#head?.value ?? null; } // O(1)
isEmpty() { return this.#size === 0; }
get size(){ return this.#size; }
}
// ─── Classic use case: BFS shortest path ─────────────────────
function bfs(graph, start, target) {
const queue = new Queue();
const visited = new Set([start]);
queue.enqueue([start, [start]]); // [node, pathSoFar]
while (!queue.isEmpty()) {
const [node, path] = queue.dequeue();
if (node === target) return path;
for (const neighbor of graph[node] ?? []) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.enqueue([neighbor, [...path, neighbor]]);
}
}
}
return null; // No path found
}
const graph = { A: ['B','C'], B: ['D'], C: ['D','E'], D: ['F'], E: ['F'], F: [] };
console.log(bfs(graph, 'A', 'F')); // ['A', 'B', 'D', 'F'] or ['A', 'C', 'E', 'F']
// ─── Why NOT to use array.shift() for queues ─────────────────
// ❌ O(n) dequeue — shifts every element left after removing index 0
const badQueue = [];
badQueue.push('task1'); // O(1) enqueue
badQueue.shift(); // ❌ O(n) dequeue — avoid for queues
// ✅ Use the Queue class above, or a circular buffer for fixed-size queues