Master queue operations, implementation variants, and real-world applications. This tutorial covers BFS, priority queues, circular buffers, and common interview problems with coding examples.
Queues in DSA: FIFO Principles & Applications
Queue Usage in Systems (2023)
1. Queue Fundamentals
Core Principles:
- FIFO: First In First Out principle
- Key Operations: Enqueue, Dequeue, Peek
- Dynamic Size: Grows/shrinks as needed
Time Complexities:
| Operation | Array-based | Linked List-based |
|---|---|---|
| Enqueue | O(1)* | O(1) |
| Dequeue | O(1) | O(1) |
| Peek | O(1) | O(1) |
| Search | O(n) | O(n) |
* O(n) when resizing needed
Basic Implementations:
Array-based Queue
class ArrayQueue {
constructor(capacity = 10) {
this.items = new Array(capacity);
this.front = 0;
this.rear = -1;
this.size = 0;
}
enqueue(item) {
if (this.isFull()) this.resize();
this.rear = (this.rear + 1) % this.items.length;
this.items[this.rear] = item;
this.size++;
}
dequeue() {
if (this.isEmpty()) throw new Error("Queue underflow");
const item = this.items[this.front];
this.front = (this.front + 1) % this.items.length;
this.size--;
return item;
}
resize() {
const newItems = new Array(this.items.length * 2);
for (let i = 0; i < this.size; i++) {
newItems[i] = this.items[(this.front + i) % this.items.length];
}
this.items = newItems;
this.front = 0;
this.rear = this.size - 1;
}
}Linked List Queue
class QueueNode {
constructor(val, next = null) {
this.val = val;
this.next = next;
}
}
class LinkedListQueue {
constructor() {
this.head = null;
this.tail = null;
this.size = 0;
}
enqueue(val) {
const node = new QueueNode(val);
if (this.isEmpty()) {
this.head = this.tail = node;
} else {
this.tail.next = node;
this.tail = node;
}
this.size++;
}
dequeue() {
if (this.isEmpty()) throw new Error("Queue underflow");
const val = this.head.val;
this.head = this.head.next;
this.size--;
if (this.isEmpty()) this.tail = null;
return val;
}
}2. Queue Applications
Classic Problems:
Breadth-First Search (BFS)
function bfs(graph, start) {
const queue = [start];
const visited = new Set([start]);
const result = [];
while (queue.length) {
const node = queue.shift();
result.push(node);
for (const neighbor of graph[node]) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push(neighbor);
}
}
}
return result;
}Recent Calls Counter
class RecentCounter {
constructor() {
this.queue = [];
}
ping(t) {
this.queue.push(t);
while (this.queue[0] < t - 3000) {
this.queue.shift();
}
return this.queue.length;
}
}Real-world Use Cases:
- Printers: Job scheduling
- Web Servers: Request handling
- CPU Scheduling: Process management
- Event Loops: Message processing
3. Advanced Queue Techniques
Specialized Variants:
Priority Queue
class PriorityQueue {
constructor(comparator = (a, b) => a > b) {
this.heap = [];
this.comparator = comparator;
}
enqueue(val) {
this.heap.push(val);
this.bubbleUp();
}
dequeue() {
const root = this.heap[0];
const last = this.heap.pop();
if (this.heap.length > 0) {
this.heap[0] = last;
this.sinkDown();
}
return root;
}
bubbleUp() {
let index = this.heap.length - 1;
while (index > 0) {
const parentIdx = Math.floor((index - 1) / 2);
if (!this.comparator(this.heap[index], this.heap[parentIdx])) break;
[this.heap[parentIdx], this.heap[index]] =
[this.heap[index], this.heap[parentIdx]];
index = parentIdx;
}
}
}Circular Queue
class CircularQueue {
constructor(k) {
this.queue = new Array(k);
this.head = -1;
this.tail = -1;
this.size = 0;
}
enQueue(value) {
if (this.isFull()) return false;
if (this.isEmpty()) this.head = 0;
this.tail = (this.tail + 1) % this.queue.length;
this.queue[this.tail] = value;
this.size++;
return true;
}
deQueue() {
if (this.isEmpty()) return false;
if (this.head === this.tail) {
this.head = this.tail = -1;
} else {
this.head = (this.head + 1) % this.queue.length;
}
this.size--;
return true;
}
}Queue Problem-Solving Cheat Sheet
| Problem Type | Approach | Time Complexity |
|---|---|---|
| BFS Traversal | Standard queue | O(V + E) |
| Sliding Window | Deque for indices | O(n) |
| Task Scheduling | Priority queue | O(n log n) |
| Recent Calls | Maintain time window | O(1) amortized |
4. Specialized Queue Variants
Double-Ended Queue (Deque)
Insert/remove from both ends
class Deque {
constructor() {
this.items = [];
}
addFront(item) {
this.items.unshift(item);
}
addRear(item) {
this.items.push(item);
}
removeFront() {
return this.items.shift();
}
removeRear() {
return this.items.pop();
}
}Blocking Queue
Thread-safe with wait semantics
class BlockingQueue {
constructor() {
this.queue = [];
this.lock = new Mutex();
this.notEmpty = new ConditionVariable();
}
async enqueue(item) {
await this.lock.acquire();
try {
this.queue.push(item);
this.notEmpty.signal();
} finally {
this.lock.release();
}
}
async dequeue() {
await this.lock.acquire();
try {
while (this.queue.length === 0) {
await this.notEmpty.wait(this.lock);
}
return this.queue.shift();
} finally {
this.lock.release();
}
}
}Delay Queue
Elements available after delay
class DelayQueue {
constructor() {
this.queue = new PriorityQueue(
(a, b) => a.availableAt < b.availableAt
);
}
add(item, delayMs) {
this.queue.enqueue({
item,
availableAt: Date.now() + delayMs
});
}
poll() {
if (this.queue.isEmpty()) return null;
const { item, availableAt } = this.queue.peek();
if (availableAt <= Date.now()) {
return this.queue.dequeue().item;
}
return null;
}
}Queue Problem-Solving Checklist
✓ Handle empty queue cases (underflow)
✓ Consider circular buffers for fixed-size queues
✓ Use priority queues for ordered processing
✓ Optimize for concurrency when needed
DSA Expert Insight: Queue problems appear in 25% of technical interviews, especially in graph traversal and system design questions. Mastering both standard and priority queues is essential for efficient problem-solving.
0 Interaction
0 Views
0 Likes
×
