# Queues

> FIFO — first in, first out. Enqueue at back, dequeue from front. O(1) both ends.

- **Category**: Data Structures
- **Subcategory**: linear
- **Canonical URL**: https://designpattern.fyi/data_structures/queues/

---

## Description
Clean, reusable architecture pattern.


## Use Cases
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.



## Implementation Example

```javascript
// ─── 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

```



## Trade-offs


### 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




### Considerations & Drawbacks

- 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







---
**Reference**: [Original Source](https://www.bigocheatsheet.com)