Beyond the basic FIFO queue. Explore Circular, Priority, and Double-ended queues—specialized structures for specific algorithmic challenges.
Last position connects back to first, forming a circle. Eliminates wasted space in array implementation.
Elements served based on priority, not insertion order. Highest priority element is dequeued first.
Double-ended queue allowing insertion and deletion at both front and rear ends.
A circular queue connects the last position back to the first, forming a circle. This solves the "false overflow" problem of linear queues where space is available at the front but we can't insert at the rear.
After the last position, we wrap around to the first position using modulo arithmetic.
Unlike linear queues, empty spaces at the front can be reused when rear reaches the end.
Front and rear pointers use (position + 1) % size to wrap around.
class CircularQueue {
constructor(size) {
this.items = new Array(size);
this.size = size;
this.front = -1;
this.rear = -1;
}
enqueue(element) {
if (this.isFull()) return false;
if (this.front === -1) this.front = 0;
// Circular increment
this.rear = (this.rear + 1) % this.size;
this.items[this.rear] = element;
return true;
}
dequeue() {
if (this.isEmpty()) return null;
const item = this.items[this.front];
if (this.front === this.rear) {
// Last element
this.front = -1;
this.rear = -1;
} else {
// Circular increment
this.front = (this.front + 1) % this.size;
}
return item;
}
isFull() {
return (this.rear + 1) % this.size === this.front;
}
}Circular queue uses modulo arithmetic to reuse empty slots at the beginning, achieving O(1) operations without shifting elements.
A priority queue serves elements based on priority, not insertion order. The highest priority element is always served first. Typically implemented using a Heap for efficient operations.
Parent node is always greater than or equal to children. Root is the maximum priority element.
After insertion or extraction, heap property is restored through heapify-up or heapify-down.
Dijkstra's algorithm, A* pathfinding, Huffman coding, task scheduling, and load balancing.
class PriorityQueue {
constructor() {
this.heap = [];
}
// Insert with priority
enqueue(value, priority) {
const node = { value, priority };
this.heap.push(node);
this.heapifyUp(this.heap.length - 1);
}
heapifyUp(index) {
const parent = Math.floor((index - 1) / 2);
if (parent >= 0 && this.heap[parent].priority > this.heap[index].priority) {
[this.heap[parent], this.heap[index]] =
[this.heap[index], this.heap[parent]];
this.heapifyUp(parent);
}
}
// Extract minimum (highest priority)
dequeue() {
if (this.heap.length === 0) return null;
const min = this.heap[0];
const end = this.heap.pop();
if (this.heap.length > 0) {
this.heap[0] = end;
this.heapifyDown(0);
}
return min;
}
}A deque (pronounced "deck") allows insertion and deletion at both the front and rear ends. It combines the capabilities of both stacks and queues, offering maximum flexibility.
Insertion at only one end, deletion at both ends. Useful for specific scheduling algorithms.
Deletion at only one end, insertion at both ends. Used in buffer management.
class Deque {
constructor() {
this.items = [];
}
// Add to front
pushFront(element) {
this.items.unshift(element);
}
// Add to rear (same as queue enqueue)
pushRear(element) {
this.items.push(element);
}
// Remove from front (same as queue dequeue)
popFront() {
if (this.isEmpty()) return null;
return this.items.shift();
}
// Remove from rear (same as stack pop)
popRear() {
if (this.isEmpty()) return null;
return this.items.pop();
}
peekFront() {
return this.items[0];
}
peekRear() {
return this.items[this.items.length - 1];
}
}Classic deque application: Check if a string is palindrome by comparing characters from both ends.
Each variant solves specific problems. Here's when to use which.
| Operation | Circular | Priority | Deque |
|---|---|---|---|
| Insert Front | O(1) | O(log n) | O(1) |
| Insert Rear | O(1) | O(log n) | O(1) |
| Delete Front | O(1) | O(log n) | O(1) |
| Delete Rear | O(1) | - | O(1) |
| Peek | O(1) | O(1) | O(1) |