Queues and deques

The FIFO rule:

A queue is a linear data structure where insertions happen at one end (the rear) and deletions happen at the other (the front). The rule is FIFO (First In, First Out): the element added first is the one removed first.

Imagine a checkout line at a grocery store. Customers join at the back and leave from the front. The first to join is the first to pay and leave. You never skip ahead; no one cuts in front. That is FIFO.

The two operations:

1. Enqueue: Add an element to the rear of the queue. Returns nothing; updates the queue in-place.
2. Dequeue: Remove and return the front element of the queue. If the queue is empty, either return null or raise an error (implementation-dependent).

There is also often a front or peek operation to see the front element without removing it.

const queue = [];  // Empty queue

// Enqueue: add 10, 20, 30
queue.push(10);    // Queue: [10]
queue.push(20);    // Queue: [10, 20]
queue.push(30);    // Queue: [10, 20, 30]

// Peek: see the front
console.log(queue[0]);  // 10 (without removing)

// Dequeue: remove the front
// DO NOT use queue.shift() in a real queue! It is O(n).
const front = queue[0];
queue = queue.slice(1);  // Inefficient! Why?

Why .shift() is O(n), and how to fix it:

When you use JavaScript’s .shift() or remove from the front of an array, the language must reindex all remaining elements:

Before:  [10, 20, 30, 40]  (indices 0, 1, 2, 3)
Remove index 0 (10).
After:   [20, 30, 40]      (indices 0, 1, 2)
         ↑  Reindex all!

That reindexing is O(n) work. If you call dequeue n times, it costs O(n²) total — very expensive.

Solution 1: Use front and rear pointers.

Instead of removing, keep a front pointer. Enqueue goes to the rear; dequeue increments the front pointer.

class Queue {
  constructor() {
    this.items = [];
    this.front = 0;  // Pointer to the front
  }
  
  enqueue(value) {
    this.items.push(value);
  }
  
  dequeue() {
    if (this.front >= this.items.length) return null;
    const value = this.items[this.front];
    this.front++;
    return value;
  }
  
  peek() {
    if (this.front >= this.items.length) return null;
    return this.items[this.front];
  }
  
  isEmpty() {
    return this.front >= this.items.length;
  }
}

Now both enqueue and dequeue are O(1). But there is a problem: the front pointer only moves forward. After many dequeues, the front part of the array is wasted space. If you dequeue 1000 items, the first 1000 slots are never reused.

Solution 2: Use a circular buffer.

A circular buffer wraps around. When you reach the end of the array, the next enqueue goes back to index 0 (if that slot is empty). This reuses space and keeps both ends O(1):

class CircularQueue {
  constructor(capacity) {
    this.items = new Array(capacity);
    this.front = 0;
    this.rear = -1;
    this.size = 0;
    this.capacity = capacity;
  }
  
  enqueue(value) {
    if (this.size === this.capacity) {
      // Queue is full. Grow the array.
      this._resize();
    }
    this.rear = (this.rear + 1) % this.capacity;
    this.items[this.rear] = value;
    this.size++;
  }
  
  dequeue() {
    if (this.size === 0) return null;
    const value = this.items[this.front];
    this.front = (this.front + 1) % this.capacity;
    this.size--;
    return value;
  }
  
  peek() {
    if (this.size === 0) return null;
    return this.items[this.front];
  }
  
  _resize() {
    const newCapacity = this.capacity * 2;
    const newItems = new Array(newCapacity);
    for (let i = 0; i < this.size; i++) {
      newItems[i] = this.items[(this.front + i) % this.capacity];
    }
    this.items = newItems;
    this.front = 0;
    this.rear = this.size - 1;
    this.capacity = newCapacity;
  }
}

The modulo % operator wraps the pointers: when rear reaches the end, it wraps to 0.

Solution 3: Use a linked list.

A linked list naturally supports O(1) insertion at the tail and O(1) deletion at the head:

class Node {
  constructor(value, next = null) {
    this.value = value;
    this.next = next;
  }
}

class QueueLinkedList {
  constructor() {
    this.head = null;  // Front of queue
    this.tail = null;  // Rear of queue
  }
  
  enqueue(value) {
    const newNode = new Node(value);
    if (this.tail === null) {
      this.head = this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
  }
  
  dequeue() {
    if (this.head === null) return null;
    const value = this.head.value;
    this.head = this.head.next;
    if (this.head === null) this.tail = null;
    return value;
  }
  
  peek() {
    if (this.head === null) return null;
    return this.head.value;
  }
  
  isEmpty() {
    return this.head === null;
  }
}

The deque: queues on both ends

A deque (double-ended queue) allows insertion and deletion at both ends. You can push and pop from both the front and the rear. A deque implemented with a doubly linked list or a circular buffer supports all four operations in O(1):

class Deque {
  constructor() {
    this.items = [];
    this.front = 0;
    this.rear = -1;
    this.size = 0;
  }
  
  pushBack(value) {
    this.items.push(value);
    this.rear++;
    this.size++;
  }
  
  pushFront(value) {
    this.items.unshift(value);
    this.rear++;
    this.size++;
  }
  
  popBack() {
    if (this.size === 0) return null;
    this.size--;
    this.rear--;
    return this.items.pop();
  }
  
  popFront() {
    if (this.size === 0) return null;
    this.size--;
    this.front++;
    return this.items.shift();  // This is O(n)!
  }
  
  peekFront() {
    if (this.size === 0) return null;
    return this.items[this.front];
  }
  
  peekBack() {
    if (this.size === 0) return null;
    return this.items[this.rear];
  }
}

Note: The above naive deque is inefficient (popFront uses .shift()). A proper deque uses a circular buffer or doubly linked list to ensure O(1) for all operations.