JavaScript Program to Implement a Circular Queue Using Arrays

Introduction

A Circular Queue is a linear data structure in which the last position is connected back to the first position, forming a circle. It is often used in situations where a fixed-size buffer is required, such as in traffic simulation, resource management, or handling real-time data.

In a circular queue:

• Front: Points to the front (first) element in the queue.
• Rear: Points to the last element in the queue.
• Enqueue: Adds an element to the rear.
• Dequeue: Removes an element from the front.
• The queue is considered full when the next position of rear is front.
• The queue is considered empty when front is equal to -1.

This guide will walk you through implementing a circular queue in JavaScript using an array.

Problem Statement

Create a JavaScript program that:

• Implements a Circular Queue using an array.
• Supports operations such as:
  • Enqueue: Insert an element into the circular queue.
  • Dequeue: Remove an element from the circular queue.
  • Display: Display the current elements in the queue.

Example:

• Input: Enqueue 10, 20, 30, 40, Dequeue once.
• Output: Queue after dequeue: [20, 30, 40].

Solution Steps

1. Define the Circular Queue Class:
   • Implement methods for:
     • Enqueue: Add an element to the rear.
     • Dequeue: Remove an element from the front.
     • Display: Display the current state of the circular queue.
2. Handle Wraparound: Manage the circular nature of the queue using modulo arithmetic.
3. Check Full/Empty Conditions: Ensure that enqueue and dequeue operations only proceed when the queue is not full or empty, respectively.

JavaScript Program

Step 1: Define the Circular Queue Class

// JavaScript Program to Implement a Circular Queue Using Arrays
// Author: https://www.rameshfadatare.com/

class CircularQueue {
    constructor(size) {
        this.size = size;          // Maximum size of the queue
        this.queue = new Array(size); // Array to store the queue elements
        this.front = -1;           // Index of the front element
        this.rear = -1;            // Index of the rear element
    }

    // Check if the queue is full
    isFull() {
        return (this.front === (this.rear + 1) % this.size);
    }

    // Check if the queue is empty
    isEmpty() {
        return this.front === -1;
    }

    // Enqueue: Add an element to the queue
    enqueue(element) {
        if (this.isFull()) {
            console.log("Queue is full. Cannot enqueue.");
            return;
        }
        if (this.front === -1) {
            // First element insertion
            this.front = 0;
        }
        this.rear = (this.rear + 1) % this.size;
        this.queue[this.rear] = element;
        console.log(`${element} enqueued`);
    }

    // Dequeue: Remove an element from the queue
    dequeue() {
        if (this.isEmpty()) {
            console.log("Queue is empty. Cannot dequeue.");
            return;
        }

        const removedElement = this.queue[this.front];
        if (this.front === this.rear) {
            // Only one element was present
            this.front = this.rear = -1;
        } else {
            this.front = (this.front + 1) % this.size;
        }
        console.log(`${removedElement} dequeued`);
        return removedElement;
    }

    // Display the elements in the queue
    displayQueue() {
        if (this.isEmpty()) {
            console.log("Queue is empty.");
            return;
        }

        console.log("Queue elements:");
        let i = this.front;
        while (true) {
            console.log(this.queue[i]);
            if (i === this.rear) break;
            i = (i + 1) % this.size;
        }
    }
}

Step 2: Example Usage

// Example usage of the Circular Queue
const cq = new CircularQueue(5); // Circular queue of size 5

// Enqueue elements
cq.enqueue(10);
cq.enqueue(20);
cq.enqueue(30);
cq.enqueue(40);
cq.enqueue(50);

// Display queue
cq.displayQueue(); // Output: 10, 20, 30, 40, 50

// Try to enqueue into a full queue
cq.enqueue(60); // Output: Queue is full. Cannot enqueue.

// Dequeue elements
cq.dequeue(); // Output: 10 dequeued
cq.dequeue(); // Output: 20 dequeued

// Display queue after dequeue
cq.displayQueue(); // Output: 30, 40, 50

// Enqueue more elements after dequeue
cq.enqueue(60);
cq.enqueue(70);

// Display queue after more enqueues
cq.displayQueue(); // Output: 30, 40, 50, 60, 70

Output Example

10 enqueued
20 enqueued
30 enqueued
40 enqueued
50 enqueued
Queue elements:
10
20
30
40
50
Queue is full. Cannot enqueue.
10 dequeued
20 dequeued
Queue elements:
30
40
50
60 enqueued
70 enqueued
Queue elements:
30
40
50
60
70

Explanation

Step 1: Define the Circular Queue Class

• isFull(): Checks if the queue is full by determining if the next position of the rear would equal the front.
• isEmpty(): Checks if the queue is empty by seeing if front is -1.
• enqueue(): Adds an element to the queue by updating the rear pointer and placing the element at that position. The rear is wrapped around using modulo arithmetic ((rear + 1) % size).
• dequeue(): Removes an element from the queue by updating the front pointer and returning the element. If only one element remains, both front and rear are reset to -1.
• displayQueue(): Traverses the queue from front to rear, wrapping around if necessary.

Step 2: Example Usage

• The program creates a circular queue of size 5 and performs various operations such as enqueueing and dequeueing elements. It also handles edge cases where the queue is full or empty.

Time Complexity

• Enqueue: O(1), since it simply updates the rear pointer and inserts the element at the new position.
• Dequeue: O(1), since it updates the front pointer and removes the element.
• Display: O(n), where n is the number of elements in the queue, because it traverses all the elements.

Conclusion

This JavaScript program implements a circular queue using arrays. Circular queues are useful in scenarios where fixed-size buffers are needed, and the wrapping behavior helps optimize memory usage. The program provides essential operations like enqueue, dequeue, and display, ensuring efficient management of queue elements.