Circular Queue

A normal queue follows the FIFO (First In, First Out) principle. Elements are added at the rear and removed from the front.

When we implement a queue using a fixed-size array, however, we can run into a problem. After removing some elements, empty spaces can appear at the beginning of the array, while the rear reaches the end.

A circular queue solves this problem by allowing the rear to wrap around to the beginning of the array and reuse those empty spaces.

The Problem with a Normal Array Queue

Suppose we have an array with five positions:

Index:   0    1    2    3    4
        ┌────┬────┬────┬────┬────┐
        │ 10 │ 20 │ 30 │ 40 │ 50 │
        └────┴────┴────┴────┴────┘
         ↑                   ↑
       Front               Rear

Now suppose we remove 10, 20, and 30.

The queue becomes:

Index:   0    1    2    3    4
        ┌────┬────┬────┬────┬────┐
        │    │    │    │ 40 │ 50 │
        └────┴────┴────┴────┴────┘
                         ↑    ↑
                       Front Rear

There are three empty spaces at the beginning.

But if the rear has already reached index 4, a simple array implementation might say the queue is full and refuse to add another element.

That's wasteful because we actually have free space available.

A circular queue fixes this.

What is a Circular Queue?

A circular queue treats the array as if the last position is connected back to the first position.

Instead of thinking of the array as:

0 → 1 → 2 → 3 → 4 → End

we think of it as:

0 → 1 → 2 → 3 → 4
↑                 ↓
└─────────────────┘

When the rear reaches the last index, it can wrap around to index 0.

This allows us to reuse positions that became empty after elements were removed.

How Circular Queue Works

Suppose we have:

Index:   0    1    2    3    4
        ┌────┬────┬────┬────┬────┐
        │    │    │    │ 40 │ 50 │
        └────┴────┴────┴────┴────┘
                         ↑    ↑
                       Front Rear

Now we want to add 60.

There is no free position after index 4, so the rear wraps around:

Index:   0    1    2    3    4
        ┌────┬────┬────┬────┬────┐
        │ 60 │    │    │ 40 │ 50 │
        └────┴────┴────┴────┴────┘
         ↑              ↑
       Rear            Front

The queue is now logically:

40 → 50 → 60

The physical positions in the array don't need to be next to each other. The circular structure connects them logically.

Front and Rear

A circular queue usually keeps track of two important positions:

front
rear

Front points to the element that will be removed next.

Rear points to the position where the next element will be inserted, depending on the implementation.

For example:

Index:   0    1    2    3    4
        ┌────┬────┬────┬────┬────┐
        │ 60 │    │    │ 40 │ 50 │
        └────┴────┴────┴────┴────┘
         ↑              ↑
       Rear            Front

The logical order is:

40 → 50 → 60

even though the values are physically stored across the end and beginning of the array.

The Modulo Operator

The % operator is extremely important when implementing a circular queue.

Suppose the array size is 5.

The indexes are:

0, 1, 2, 3, 4

If we want to move forward from index 4, we want to return to index 0.

We can do:

(rear + 1) % 5

When rear is 4:

(4 + 1) % 5
= 5 % 5
= 0

So the index wraps around to 0.

Similarly:

0 → 1 → 2 → 3 → 4 → 0 → 1 → ...

This is the key technique behind a circular queue.

Enqueue Operation

Enqueue means adding an element to the queue.

Suppose we have:

10 → 20 → 30

and we perform:

enqueue(40)

The queue becomes:

10 → 20 → 30 → 40

In a circular array, the rear is moved using:

rear = (rear + 1) % capacity;

Then the new value is stored at that position.

Dequeue Operation

Dequeue removes the element from the front.

Suppose:

10 → 20 → 30 → 40

We perform:

dequeue()

10 is removed:

20 → 30 → 40

The front then moves forward:

front = (front + 1) % capacity;

If the front reaches the end of the array, it wraps back to the beginning.

Implementing a Circular Queue in Java

Let's build a simple circular queue using an array:

class CircularQueue {

    private int[] data;
    private int front;
    private int rear;
    private int size;

    CircularQueue(int capacity) {
        data = new int[capacity];
        front = 0;
        rear = -1;
        size = 0;
    }

    void enqueue(int value) {

        if (size == data.length) {
            System.out.println("Queue is full");
            return;
        }

        rear = (rear + 1) % data.length;
        data[rear] = value;
        size++;
    }

    int dequeue() {

        if (size == 0) {
            System.out.println("Queue is empty");
            return -1;
        }

        int value = data[front];

        front = (front + 1) % data.length;
        size--;

        return value;
    }

    int peek() {

        if (size == 0) {
            System.out.println("Queue is empty");
            return -1;
        }

        return data[front];
    }
}

Here, size helps us determine whether the queue is empty or completely full.

Using the Circular Queue

We can use our class like this:

class Main {
    public static void main(String[] args) {

        CircularQueue queue = new CircularQueue(5);

        queue.enqueue(10);
        queue.enqueue(20);
        queue.enqueue(30);
        queue.enqueue(40);
        queue.enqueue(50);

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

        queue.enqueue(60);
        queue.enqueue(70);

        System.out.println(queue.peek());
    }
}

The important part is that after removing elements from the front, the newly added elements can reuse the empty spaces at the beginning.

Circular Queue vs Normal Queue

The main difference is how the array space is managed.

A simple linear queue might behave like:

10 20 30 40 50
↑              ↑
Front          Rear

After removing elements:

_  _  _  40 50
         ↑  ↑
       Front Rear

The empty spaces at the beginning may not be reused.

A circular queue allows the rear to wrap around:

60 70 _ 40 50
↑       ↑
Rear   Front

So the available space can be reused.

Circular Queue vs Circular Linked List

These two structures sound similar, but they are different.

A circular queue is a queue implementation where the storage wraps around, commonly using an array.

A circular linked list is a linked list where the last node points back to the first node.

Circular queue:

[0] → [1] → [2] → [3] → [4]
 ↑                       ↓
 └───────────────────────┘

Circular linked list:

10 → 20 → 30
↑         ↓
└─────────┘

The underlying concepts are different.

Time Complexity

A properly implemented circular queue provides efficient operations:

The modulo operation allows us to move front and rear around the array without shifting elements.

Real-Life Example

Imagine a group of people waiting for a ride that has a fixed number of seats.

As people leave, new people can take the newly available positions.

Instead of treating the available positions as permanently tied to their original location, we can continuously reuse them.

A similar idea appears in systems that continuously process data, where new items keep entering as old items leave.

Common Applications

Circular queues are useful in situations where data is continuously added and removed.

Some examples include:

• CPU scheduling

• Round-robin scheduling

• Circular buffers

• Streaming data

• Network buffering

• Keyboard input buffers

• Printer systems

• Producer-consumer systems

For example, in round-robin CPU scheduling, processes are given a fixed amount of CPU time one after another. After the last process gets its turn, the system goes back to the first process.

This naturally fits a circular structure.

The Main Idea

A circular queue is a queue that uses a circular arrangement so that the rear can wrap around to the beginning of the storage space.

The most important idea is:

Last index
    ↓
    4
    ↓
    0
    ↑
First index

The modulo operation makes this possible:

(rear + 1) % capacity

and:

(front + 1) % capacity

So instead of wasting empty spaces at the beginning of an array, a circular queue can reuse them.

A circular queue follows FIFO like a normal queue, but its front and rear positions wrap around so that unused array space can be reused efficiently.