JavaScript: Implement a Circular Queue using Arrays

1. Introduction

A circular queue, also known as a ring buffer, is a linear data structure that follows the First In First Out (FIFO) principle. The difference between a regular queue and a circular queue is that in a circular queue, the last position is connected to the front. This makes the circular queue ideal for scenarios where the queue needs to be reset when the end is reached.

2. Program Overview

In this program, we will implement a circular queue using an array. The operations we'll cover include:

1. enqueue() - to insert an element

2. dequeue() - to remove and return the first element

3. front() - to view the first element without removing it

4. rear() - to view the last element

5. isEmpty() - to check if the queue is empty

6. isFull() - to check if the queue is full

3. Code Program

// Class to represent Circular Queue
function CircularQueue(capacity) {
    this.capacity = capacity + 1;  // One space is reserved to help in determining if queue is full or empty
    this.front = 0;
    this.rear = 0;
    this.array = new Array(this.capacity);
}

// Function to insert an element
// and change rear
CircularQueue.prototype.enqueue = function(item) {
    if (this.isFull()) {
        console.log("Queue is full. Cannot enqueue.");
        return;
    }
    this.array[this.rear] = item;
    this.rear = (this.rear + 1) % this.capacity;
}

// Function to delete an element
// and change front
CircularQueue.prototype.dequeue = function() {
    if (this.isEmpty()) {
        console.log("Queue is empty. Cannot dequeue.");
        return;
    }
    var item = this.array[this.front];
    this.front = (this.front + 1) % this.capacity;
    return item;
}

// Function to get the front of the queue without removal
CircularQueue.prototype.frontItem = function() {
    if (this.isEmpty()) {
        console.log("Queue is empty.");
        return;
    }
    return this.array[this.front];
}

// Function to get the rear of the queue
CircularQueue.prototype.rearItem = function() {
    if (this.isEmpty()) {
        console.log("Queue is empty.");
        return;
    }
    return this.array[(this.rear + this.capacity - 1) % this.capacity];
}

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

// Check if the queue is empty
CircularQueue.prototype.isEmpty = function() {
    return this.front == this.rear;
}

// Test the Circular Queue
var cq = new CircularQueue(5);
cq.enqueue(1);
cq.enqueue(2);
cq.enqueue(3);
cq.enqueue(4);
cq.enqueue(5);
console.log("Front item is: " + cq.frontItem());
console.log("Rear item is: " + cq.rearItem());

cq.dequeue();
console.log("After one dequeue, front item is: " + cq.frontItem());

cq.enqueue(6);
console.log("After one enqueue, rear item is: " + cq.rearItem());

Output:

Front item is: 1
Rear item is: 5
After one dequeue, front item is: 2
After one enqueue, rear item is: 6

4. Step By Step Explanation

1. CircularQueue Class: Represents our circular queue. We initialize it with a capacity but internally allocate capacity + 1 space to help us determine if the queue is full or empty. We also have pointers front and rear to keep track of where to insert and remove elements.

2. enqueue(): This method checks if the queue is full using isFull(). If it isn't, it inserts an item at the rear and moves the rear pointer forward, wrapping around if necessary.

3. dequeue(): This method checks if the queue is empty using isEmpty(). If it isn't, it removes an item from the front and moves the front pointer forward, wrapping around if needed.

4. frontItem() & rearItem(): These methods let us peek at the front and rear of the queue without modifying them.

5. isEmpty() & isFull(): These helper methods tell us if the queue is empty or full, respectively.

6. In our test, we add items to our circular queue, peek at the front and rear, remove an item, and then add another.

The circular nature of the queue is handled by the modulus operation, ensuring that when we reach the end of the array, we wrap around to the beginning.