Queues, Deques & Circular Ring Buffers
Quick Overview
Shifting an array on every dequeue costs `O(N)`. A ring buffer moves two indices with modulo arithmetic instead, so both ends stay `O(1)` and the elements never move.
Deep Dive
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 inO(N)time. ForO(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!
Next Up in Data Structures & Algorithms Core Patterns
Big O Notation: Time & Space Complexity
Big O describes how work grows, not how long it takes. An `O(N^2)` algorithm on 1,000 items does a million steps; the same work at `O(N log N)` does about 10,000.
Dynamic Arrays & Amortized Resizing
A dynamic array doubles rather than growing by one, so the expensive copy lands on the 1st, 2nd, 4th and 8th push. Averaged across every push, that is `O(1)` amortised.
Two Pointers Pattern (Converging & Symmetrical)
A nested loop tests every pair in `O(N^2)`. On sorted data, moving two pointers inward from both ends rules out half the remaining candidates at each step and settles it in one `O(N)` pass.