Circular Queue

A circular queue is a special type of queue where the last element is connected back to the first one, making a circle. This helps in using the available space more efficiently.

A circular queue solves the main problem of a normal queue. In a regular queue, after some insertions and deletions, empty spaces are left at the front that can't be used.

Here, indexes 0 and 1 can only be used after resetting the queue (deletion of all elements). This reduces the actual size of the queue.

How Circular Queue Works

A circular queue works using circular increment. This means when we move the pointer forward and reach the end of the queue, we go back to the beginning.

This circular movement is done using modulo division with the queue size. That is :

if REAR + 1 == 5 (overflow!), REAR = (REAR + 1)%5 = 0 (start of queue)

Circular Queue Operations

The circular queue work as follows:

• two pointers FRONT and REAR
• FRONT track the first element of the queue
• REAR track the last elements of the queue
• initially, set value of FRONT and REAR to -1

1. Enqueue Operation

• check if the queue is full
• for the first element, set value of FRONT to 0
• circularly increase the REAR index by 1 (i.e. if the rear reaches the end, next it would be at the start of the queue)
• add the new element in the position pointed to by REAR

2. Dequeue Operation

• check if the queue is empty
• return the value pointed by FRONT
• circularly increase the FRONT index by 1
• for the last element, reset the values of FRONT and REAR to -1

However, the check for full queue has a new additional case:

• Case 1: FRONT = 0 && REAR == SIZE - 1
• Case 2: FRONT = REAR + 1

The second case happens when REAR starts from 0 due to circular increment and when its value is just 1 less than FRONT, the queue is full.

Circular Queue Code:

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

  isEmpty() {
    return this.front === -1;
  }

  isFull() {
    return (this.rear + 1) % this.size === this.front;
  }

  enqueue(element) {
    if (this.isFull()) {
      console.log("Queue is full");
      return;
    }

    if (this.isEmpty()) {
      this.front = this.rear = 0;
    } else {
      this.rear = (this.rear + 1) % this.size;
    }

    this.items[this.rear] = element;
  }

  dequeue() {
    if (this.isEmpty()) {
      console.log("Queue is empty");
      return null;
    }

    let dequeuedValue = this.items[this.front];

    this.items[this.front] = null;

    if (this.front === this.rear) {
      this.front = this.rear = -1;
    } else {
      this.front = (this.front + 1) % this.size;
    }

    return dequeuedValue;
  }

  peek() {
    if (this.isEmpty()) {
      console.log("Queue is empty");
      return null;
    }
    return this.items[this.front];
  }

  print() {
    console.log(this.items);
  }
}

const circularQueue = new CircularQueue(5);

circularQueue.enqueue(2);
circularQueue.enqueue(3);
circularQueue.enqueue(4);
circularQueue.enqueue(5);
circularQueue.enqueue(9);
console.log(circularQueue.isFull());

console.log(circularQueue.dequeue());
console.log(circularQueue.dequeue());
circularQueue.enqueue(11);
circularQueue.enqueue(12);

circularQueue.isEmpty();
console.log("peek : ", circularQueue.peek());
circularQueue.print();

Circular Queue Complexity Analysis

The complexity of the enqueue and dequeue operations of a circular queue is O(1) for (array implementations).

Applications of Circular Queue

• CPU scheduling
• Memory management
• Traffic Management