Understanding Queues in Programming

January 10, 2025 | Data Structures

Queues are fundamental data structures in programming. They operate on the FIFO (First In, First Out) principle, where elements are added at the back and removed from the front. This structure is commonly used in scenarios like task scheduling, buffering, and breadth-first search in graphs.

Characteristics of Queues

1. FIFO Principle: The first element added is the first to be removed.
2. Two Main Operations:
   • Enqueue: Add an element to the back of the queue.
   • Dequeue: Remove an element from the front of the queue.
3. Limited Access: Only the front and back elements are accessible.

Types of Queues

1. Simple Queue: Operates strictly on the FIFO principle.
2. Circular Queue: The rear of the queue connects to the front, forming a circle.
3. Priority Queue: Elements are dequeued based on priority rather than the order they were enqueued.
4. Deque (Double-Ended Queue): Elements can be added or removed from both ends.

Queue Operations in JavaScript

JavaScript does not have a built-in Queue class, but you can use an array to implement queue behavior.

Example: Simple Queue

class Queue {
    constructor() {
        this.items = [];
    }

    // Enqueue: Add an element to the back
    enqueue(element) {
        this.items.push(element);
    }

    // Dequeue: Remove an element from the front
    dequeue() {
        if (this.isEmpty()) {
            return 'Queue is empty';
        }
        return this.items.shift();
    }

    // Peek: View the front element
    peek() {
        if (this.isEmpty()) {
            return 'Queue is empty';
        }
        return this.items[0];
    }

    // Check if the queue is empty
    isEmpty() {
        return this.items.length === 0;
    }

    // View all elements in the queue
    printQueue() {
        return this.items.join(', ');
    }
}

const queue = new Queue();
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
console.log(queue.dequeue()); // Output: 10
console.log(queue.peek());    // Output: 20
console.log(queue.printQueue()); // Output: 20, 30

Example: Circular Queue

class CircularQueue {
    constructor(size) {
        this.size = size;
        this.items = Array(size).fill(null);
        this.front = -1;
        this.rear = -1;
    }

    // Enqueue
    enqueue(element) {
        if ((this.rear + 1) % this.size === this.front) {
            return 'Queue is full';
        }
        if (this.front === -1) {
            this.front = 0;
        }
        this.rear = (this.rear + 1) % this.size;
        this.items[this.rear] = element;
    }

    // Dequeue
    dequeue() {
        if (this.front === -1) {
            return 'Queue is empty';
        }
        const element = this.items[this.front];
        if (this.front === this.rear) {
            this.front = this.rear = -1;
        } else {
            this.front = (this.front + 1) % this.size;
        }
        return element;
    }

    // Peek
    peek() {
        if (this.front === -1) {
            return 'Queue is empty';
        }
        return this.items[this.front];
    }
}

const circularQueue = new CircularQueue(5);
circularQueue.enqueue(10);
circularQueue.enqueue(20);
circularQueue.enqueue(30);
console.log(circularQueue.dequeue()); // Output: 10
console.log(circularQueue.peek());    // Output: 20

Use Cases of Queues

1. Task Scheduling: Queues handle tasks in the order they arrive (e.g., print jobs).
2. Breadth-First Search: In graph traversal, nodes are visited level by level using a queue.
3. Data Buffers: Queues manage data buffering in scenarios like streaming.
4. Asynchronous Tasks: Background tasks or promises often use queues for execution.