A queue is a linear data structure that follows the First In First Out (FIFO) principle, in contrast to the Last In First Out (LIFO) characteristic of a stack. In a queue, the first element added is the first to be removed.
Basic Concepts of Queues
A queue has two primary operations:
- Enqueue: Add an element to the end of the queue
- Dequeue: Remove an element from the front of the queue
Additionally, queues typically provide the following helper operations:
- peek(): View the front element without removing it
- isEmpty(): Check if the queue is empty
- size(): Return the number of elements in the queue
Queue Implementations
Array Implementation
The simplest way to implement a queue is using an array:
class ArrayQueue {
constructor() {
this.items = [];
}
// Enqueue
enqueue(element) {
this.items.push(element);
}
// Dequeue
dequeue() {
if (this.isEmpty()) return undefined;
return this.items.shift();
}
// Peek at the front element
peek() {
if (this.isEmpty()) return undefined;
return this.items[0];
}
// Check if the queue is empty
isEmpty() {
return this.items.length === 0;
}
// Return the queue size
size() {
return this.items.length;
}
// Clear the queue
clear() {
this.items = [];
}
// Print the queue contents
print() {
console.log(this.items.toString());
}
}
Time Complexity Analysis:
- Enqueue: O(1)
- Dequeue: O(n) — because all remaining elements need to be shifted
Linked List Implementation (More Efficient Dequeue)
Using a linked list can optimize the time complexity of the dequeue operation:
class Node {
constructor(element) {
this.element = element;
this.next = null;
}
}
class LinkedListQueue {
constructor() {
this.front = null; // Front of the queue
this.rear = null; // Rear of the queue
this.size = 0;
}
// Enqueue
enqueue(element) {
const newNode = new Node(element);
if (this.isEmpty()) {
this.front = newNode;
this.rear = newNode;
} else {
this.rear.next = newNode;
this.rear = newNode;
}
this.size++;
}
// Dequeue
dequeue() {
if (this.isEmpty()) return undefined;
const removedElement = this.front.element;
this.front = this.front.next;
if (this.front === null) {
this.rear = null; // Queue is empty
}
this.size--;
return removedElement;
}
// Peek at the front element
peek() {
if (this.isEmpty()) return undefined;
return this.front.element;
}
// Check if the queue is empty
isEmpty() {
return this.size === 0;
}
// Return the queue size
getSize() {
return this.size;
}
// Clear the queue
clear() {
this.front = null;
this.rear = null;
this.size = 0;
}
// Print the queue contents
print() {
let current = this.front;
let str = '';
while (current) {
str += `${current.element} `;
current = current.next;
}
console.log(str.trim());
}
}
Time Complexity Analysis:
- Enqueue: O(1)
- Dequeue: O(1)
- Peek: O(1)
Queue Applications
Task Scheduling
Queues are commonly used in task scheduling systems to process tasks in the order they are received:
class TaskScheduler {
constructor() {
this.queue = new LinkedListQueue();
}
addTask(task) {
this.queue.enqueue(task);
console.log(`Added task: ${task}`);
}
processTasks() {
while (!this.queue.isEmpty()) {
const task = this.queue.dequeue();
console.log(`Processing task: ${task}`);
// Actual task processing logic would go here
}
console.log('All tasks processed');
}
}
const scheduler = new TaskScheduler();
scheduler.addTask('Email notification');
scheduler.addTask('Database backup');
scheduler.addTask('User report generation');
scheduler.processTasks();
Print Queue
Simulating the order in which a printer processes print jobs:
class PrintQueue {
constructor() {
this.queue = new LinkedListQueue();
}
addPrintJob(jobName, pages) {
this.queue.enqueue({ jobName, pages });
console.log(`Added print job: ${jobName} (${pages} pages)`);
}
processPrintJobs(printerSpeed) {
let totalTime = 0;
while (!this.queue.isEmpty()) {
const job = this.queue.dequeue();
const timeForJob = job.pages * 60 / printerSpeed; // Assume 60/printerSpeed seconds per page
totalTime += timeForJob;
console.log(`Printing ${job.jobName} (${job.pages} pages) - Time taken: ${timeForJob.toFixed(2)} seconds`);
}
console.log(`Total printing time: ${totalTime.toFixed(2)} seconds`);
}
}
const printerQueue = new PrintQueue();
printerQueue.addPrintJob('Report', 20);
printerQueue.addPrintJob('Presentation', 10);
printerQueue.addPrintJob('Manual', 30);
printerQueue.processPrintJobs(10); // Assume printer speed is 10 pages/minute
Breadth-First Search (BFS)
Queues are a fundamental data structure for implementing BFS algorithms:
function bfs(graph, startNode) {
const visited = new Set();
const queue = new LinkedListQueue();
const result = [];
queue.enqueue(startNode);
visited.add(startNode);
while (!queue.isEmpty()) {
const currentNode = queue.dequeue();
result.push(currentNode);
for (const neighbor of graph[currentNode]) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.enqueue(neighbor);
}
}
}
return result;
}
// Example graph
const graph = {
A: ['B', 'C'],
B: ['A', 'D', 'E'],
C: ['A', 'F'],
D: ['B'],
E: ['B', 'F'],
F: ['C', 'E']
};
console.log(bfs(graph, 'A')); // Output: ['A', 'B', 'C', 'D', 'E', 'F']
Buffer Implementation
Queues can be used to implement buffers, such as a keyboard input buffer:
class KeyboardBuffer {
constructor(maxSize = 10) {
this.queue = new LinkedListQueue();
this.maxSize = maxSize;
}
pressKey(key) {
if (this.queue.getSize() >= this.maxSize) {
console.log('Buffer full, oldest key discarded');
this.queue.dequeue();
}
this.queue.enqueue(key);
console.log(`Key pressed: ${key}`);
}
getBuffer() {
const buffer = [];
let current = this.queue.front;
while (current) {
buffer.push(current.element);
current = current.next;
}
return buffer;
}
}
const buffer = new KeyboardBuffer(3);
buffer.pressKey('A');
buffer.pressKey('B');
buffer.pressKey('C');
console.log(buffer.getBuffer()); // ['A', 'B', 'C']
buffer.pressKey('D'); // Output: Buffer full, oldest key discarded
console.log(buffer.getBuffer()); // ['B', 'C', 'D']
Advanced Queue Implementations
Circular Queue
A circular queue optimizes space usage by using a fixed-size array and modular arithmetic:
class CircularQueue {
constructor(capacity) {
this.capacity = capacity + 1; // Extra space to distinguish empty vs full
this.items = new Array(this.capacity).fill(undefined);
this.front = 0;
this.rear = 0;
}
// Enqueue
enqueue(element) {
if (this.isFull()) return false;
this.items[this.rear] = element;
this.rear = (this.rear + 1) % this.capacity;
return true;
}
// Dequeue
dequeue() {
if (this.isEmpty()) return undefined;
const element = this.items[this.front];
this.items[this.front] = undefined; // Optional, clear reference
this.front = (this.front + 1) % this.capacity;
return element;
}
// Peek at the front element
peek() {
if (this.isEmpty()) return undefined;
return this.items[this.front];
}
// Check if the queue is empty
isEmpty() {
return this.front === this.rear;
}
// Check if the queue is full
isFull() {
return (this.rear + 1) % this.capacity === this.front;
}
// Return the queue size
size() {
return (this.rear - this.front + this.capacity) % this.capacity;
}
}
Time Complexity:
- All operations are O(1)
Priority Queue
In a priority queue, elements are dequeued based on their priority rather than their order of insertion:
class PriorityQueue {
constructor() {
this.items = [];
}
// Enqueue, insert based on priority
enqueue(element, priority) {
const queueElement = { element, priority };
let added = false;
for (let i = 0; i < this.items.length; i++) {
if (queueElement.priority < this.items[i].priority) {
this.items.splice(i, 0, queueElement);
added = true;
break;
}
}
if (!added) {
this.items.push(queueElement);
}
}
// Dequeue
dequeue() {
if (this.isEmpty()) return undefined;
return this.items.shift().element;
}
// Peek at the front element
peek() {
if (this.isEmpty()) return undefined;
return this.items[0].element;
}
// Check if the queue is empty
isEmpty() {
return this.items.length === 0;
}
// Return the queue size
size() {
return this.items.length;
}
// Print the queue contents
print() {
console.log(this.items.map(item => `${item.element}(${item.priority})`).toString());
}
}
// Usage example
const priorityQueue = new PriorityQueue();
priorityQueue.enqueue('Task 1', 3);
priorityQueue.enqueue('Task 2', 1);
priorityQueue.enqueue('Task 3', 2);
console.log(priorityQueue.dequeue()); // Task 2 (highest priority)
console.log(priorityQueue.dequeue()); // Task 3
console.log(priorityQueue.dequeue()); // Task 1
More Efficient Implementation (using a binary heap):
class PriorityQueueHeap {
constructor() {
this.items = [];
}
enqueue(element, priority) {
const queueElement = { element, priority };
let contain = false;
for (let i = 0; i < this.items.length; i++) {
if (this.items[i].element === element) {
if (queueElement.priority < this.items[i].priority) {
this.items[i].priority = queueElement.priority;
this.heapifyUp(i);
}
contain = true;
break;
}
}
if (!contain) {
this.items.push(queueElement);
this.heapifyUp(this.items.length - 1);
}
}
dequeue() {
if (this.isEmpty()) return undefined;
const front = this.items[0];
const end = this.items.pop();
if (this.items.length > 0) {
this.items[0] = end;
this.heapifyDown(0);
}
return front.element;
}
peek() {
if (this.isEmpty()) return undefined;
return this.items[0].element;
}
isEmpty() {
return this.items.length === 0;
}
size() {
return this.items.length;
}
heapifyUp(index) {
let parent = Math.floor((index - 1) / 2);
while (index > 0 && this.items[index].priority < this.items[parent].priority) {
[this.items[index], this.items[parent]] = [this.items[parent], this.items[index]];
index = parent;
parent = Math.floor((index - 1) / 2);
}
}
heapifyDown(index) {
const length = this.items.length;
const element = this.items[index];
while (true) {
let leftChildIndex = 2 * index + 1;
let rightChildIndex = 2 * index + 2;
let leftChild, rightChild;
let swap = null;
if (leftChildIndex < length) {
leftChild = this.items[leftChildIndex];
if (leftChild.priority < element.priority) {
swap = leftChildIndex;
}
}
if (rightChildIndex < length) {
rightChild = this.items[rightChildIndex];
if (
(swap === null && rightChild.priority < element.priority) ||
(swap !== null && rightChild.priority < leftChild.priority)
) {
swap = rightChildIndex;
}
}
if (swap === null) break;
[this.items[index], this.items[swap]] = [this.items[swap], this.items[index]];
index = swap;
}
}
}
Time Complexity:
- Enqueue: O(log n)
- Dequeue: O(log n)
- Peek: O(1)
JavaScript Built-in Queue Implementation
While JavaScript does not have a built-in queue data structure, arrays can be used to simulate one:
// Simulate a queue using an array (note the inefficiency of dequeue)
const queue = [];
queue.push('A'); // Enqueue
queue.push('B');
queue.push('C');
console.log(queue.shift()); // Dequeue and return 'A'
console.log(queue.shift()); // Return 'B'
Note: Using an array’s shift() method for dequeue operations has a time complexity of O(n) because it requires shifting all remaining elements. For scenarios requiring frequent dequeue operations, a linked list-based queue is recommended.
Queue Performance Optimization
- Avoid Frequent Dequeue Operations: For scenarios with frequent dequeues, use a linked list-based queue instead of an array-based one.
- Space Optimization with Circular Queues: For fixed-size queues, circular queues can avoid data shifting.
- Batch Operations: For large datasets, consider batch enqueue/dequeue operations.
- Concurrent Processing: In multi-threaded environments, use concurrent queues to safely handle shared data.
Practical Application Scenarios
- Task Scheduling Systems: Process scheduling in operating systems, print task queues, etc.
- Message Queues: Message passing in asynchronous systems, such as RabbitMQ, Kafka, etc.
- Breadth-First Search (BFS): Node traversal in graph algorithms.
- Buffer Management: Keyboard input buffers, network packet buffers, etc.
- Bandwidth Limiting: Control data transmission rates to prevent network congestion.
- Event Loops: Event handling mechanisms in browsers and Node.js.
- Load Balancing: Distributing requests in server clusters.
Queues are a simple yet powerful data structure with widespread applications in computer science and real-world systems. Understanding the principles and implementations of queues is crucial for developing efficient and reliable software systems.
