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.
A Queue processes elements in the exact order of arrival. Items enter at the back (enqueue) and leave from the front (dequeue).
A Deque allows O(1) insertions and deletions from both ends (front and rear).
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
Capacity: 4, Head: 1, Tail: 1 (Full)
[ 40 | 10 | 20 | 30 ]
▲ ▲
Tail Head
arr.shift() re-indexes all elements in O(N) time. For O(1) operations, use a doubly-linked list or circular ring buffer.Use queues for task scheduling and BFS graph traversals. Next, let's explore Hash Maps and Collision Resolution!
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.
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.
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.