Circular Queues

In the previous lessons, we learned about the basic queue data structure and its implementations, such as array-based and linked-list-based queues. Now, let's dive into the concept of circular queues.

A circular queue is a variant of the basic queue data structure in which the last position is connected back to the first position to form a circle. This allows for efficient memory utilization and addresses the issue of wasted space in a regular queue.

Implementation

Circular queues can be implemented using arrays by considering the following properties:

• Front: the index of the first item in the queue
• Rear: the index of the last item in the queue
• Size: the current number of elements in the queue

To enqueue an element in a circular queue, we need to check whether the queue is full. If the queue is not full, we increment the rear index and add the element at the rear position. In case the rear index reaches the end of the array, we wrap it around to the beginning of the array (0 index).

To dequeue an element from a circular queue, we need to check whether the queue is empty. If the queue is not empty, we remove the element at the front index and increment the front index. If the front index reaches the end of the array, we wrap it around to the beginning of the array (0 index).

Here's an example of implementing and using a circular queue in Java:

{{code}}

Output:

15
23
38
41
510
67
72

xxxxxxxxxx

class Main {

  public static void main(String[] args) {

    // Circular Queue Example

    CircularQueue<Integer> cq = new CircularQueue<>(5);

    cq.enqueue(5);

    cq.enqueue(3);

    cq.enqueue(8);

    cq.enqueue(1);

    cq.enqueue(10);

    System.out.println(cq.dequeue());

    System.out.println(cq.dequeue());

    cq.enqueue(7);

    cq.enqueue(2);

    while (!cq.isEmpty()) {

      System.out.println(cq.dequeue());

    }

  }

}