← Index

Linear Structures

Queue

First In, First Out — the checkout-line structure.

What it is

A queue only lets you add at the back and remove from the front, both O(1) with the right implementation. It models anything processed in the order it arrived. Note: array.shift() is O(n) because it re-indexes every element — a real queue implementation avoids that (see the code).

Real-world examples

• A checkout line — first person in line is served first, new people join at the back.
• A ticket queue at a print shop: jobs get printed in the order they were submitted.

Where you've probably used this already

• Background job processors — BullMQ, SQS, RabbitMQ — literally queues of work items, FIFO by default.
• BFS traversal (see bfs-dfs.js) uses a queue internally to explore level by level.
• Rate-limited API request handling — queue incoming requests and drain them at a controlled pace.

Complexity

Code

// Queue — First In, First Out (FIFO). Think a checkout line:
// first person in line is the first one served.

class Queue {
  constructor() {
    // An object keyed by index avoids the O(n) cost of Array.shift(),
    // which has to re-index every remaining element.
    this.items = {};
    this.front = 0;
    this.back = 0;
  }

  enqueue(item) {
    this.items[this.back] = item;
    this.back++;
  }

  dequeue() {
    if (this.front === this.back) return undefined; // empty
    const item = this.items[this.front];
    delete this.items[this.front];
    this.front++;
    return item;
  }

  peek() {
    return this.items[this.front];
  }

  isEmpty() {
    return this.front === this.back;
  }
}

// --- Example Usage ---
const q = new Queue();
q.enqueue("first");
q.enqueue("second");
q.enqueue("third");

console.log("Peek:", q.peek());     // "first"
console.log("Dequeue:", q.dequeue()); // "first"
console.log("Dequeue:", q.dequeue()); // "second"
console.log("Peek after dequeues:", q.peek()); // "third"

// Real uses of this exact pattern:
// - task queues / job processors (BullMQ, SQS, RabbitMQ)
// - printer spool, request handling in a server
// - BFS traversal (see graph.js / bfs-dfs.js) uses a queue internally