Queues, Deques & Circular Ring Buffers

Dynamic Arrays & Amortized Resizing

Learn how dynamic arrays achieve O(1) amortized insertion, contiguous memory layout, and geometric doubling strategies.

1. First-In-First-Out (FIFO)

A Queue processes elements in the exact order of arrival. Items enter at the back (enqueue) and leave from the front (dequeue).

2. Double-Ended Queue (Deque)

A Deque allows $O(1)$ insertions and deletions from both ends (front and rear).

3. The Circular Ring Buffer

Array-based queues suffer from $O(N)$ dequeue shifts if implemented with arr.shift(). A Circular Ring Buffer avoids shifts by using head and tail pointers that wrap around using the modulo operator (%):

class CircularQueue {
  constructor(capacity) {
    this.buffer = new Array(capacity);
    this.capacity = capacity;
    this.head = 0;
    this.tail = 0;
    this.size = 0;
  }

  enqueue(val) {
    if (this.size === this.capacity) throw new Error("Queue is Full!");
    this.buffer[this.tail] = val;
    this.tail = (this.tail + 1) % this.capacity; // Wrap around!
    this.size++;
    return true;
  }

  dequeue() {
    if (this.size === 0) return null;
    const item = this.buffer[this.head];
    this.head = (this.head + 1) % this.capacity; // Wrap around!
    this.size--;
    return item;
  }
}

const q = new CircularQueue(3);
q.enqueue(10);
q.enqueue(20);
q.enqueue(30);
console.log(q.dequeue()); // Output: 10
q.enqueue(40);            // Wraps to index 0!
console.log(q.dequeue()); // Output: 20

4. Visual Circular Buffer

Capacity: 4, Head: 1, Tail: 1 (Full)
[ 40 | 10 | 20 | 30 ]
  ▲    ▲
Tail  Head

5. Common Mistakes

• Using Array shift() for Production Queues: Calling arr.shift() re-indexes all elements in $O(N)$ time. For $O(1)$ operations, use a doubly-linked list or circular ring buffer.

6. Next Steps

Use queues for task scheduling and BFS graph traversals. Next, let's explore Hash Maps and Collision Resolution!