# Circular Queue

A normal Queue follows **FIFO — First In, First Out**. Elements are inserted from the rear and removed from the front.

But a normal array-based Queue has an interesting problem.

Imagine a queue with five positions:

```text
Index:    0    1    2    3    4
         [10] [20] [30] [40] [50]
          ↑                   ↑
        Front                Rear
```

The queue is full.

Now suppose we dequeue three elements:

```text
Index:    0      1      2    3    4
         [  ]   [  ]   [  ] [40] [50]
                             ↑    ↑
                          Front  Rear
```

There are now three empty positions at the beginning. But in a simple linear queue, `rear` has already reached the end of the array, so those positions may not be reused.

This is where the **Circular Queue** comes in.

* * *

## What is a Circular Queue?

A **Circular Queue** is a Queue in which the last position of the underlying array is connected back to the first position.

Conceptually:

![](https://cdn.hashnode.com/uploads/covers/6950e81e2f9daf13464777e3/4e50a54b-13ed-47c9-8d25-31550c9c6e8a.png align="center")

When `rear` reaches the last index, it can **wrap around to index 0** if space is available.

This makes better use of the fixed-size array.

A Circular Queue still follows:

> **FIFO — First In, First Out**

The difference is in how we manage the available positions.

* * *

# Front and Rear

A Circular Queue normally maintains two variables:

*   `front` — points to the element that will be removed next.
    
*   `rear` — points to the position where the latest element was inserted.
    

For an empty queue:

```text
front = -1
rear = -1
```

For example, after inserting the first element:

```text
Index:    0    1    2    3    4
         [10] [ ]  [ ]  [ ]  [ ]
          ↑
       front/rear
```

Now:

```text
front = 0
rear = 0
```

After inserting more elements:

```text
Index:    0    1    2    3    4
         [10] [20] [30] [40] [ ]
          ↑                   ↑
        Front                Rear
```

So:

```text
front = 0
rear = 3
```

* * *

# Why Do We Need `%`?

The most important part of a Circular Queue is the **modulo (**`%`**) operator**.

Suppose the queue size is `5`.

The valid indexes are:

```text
0  1  2  3  4
```

What happens when `rear` is at index `4` and we want to move it forward?

Normally:

```text
4 + 1 = 5
```

But index `5` doesn't exist. (we are talking about fixed size memory)

Using modulo:

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

So `rear` wraps back to index `0`.

This gives us the fundamental circular movement formula:

```python
(rear + 1) % size
```

The same idea is used when moving `front`:

```python
(front + 1) % size
```

* * *

# Conditions of a Circular Queue

Before implementing a Circular Queue, we need to understand its important conditions.

## 1\. Empty Queue

The queue is empty when:

```text
front = -1
```

We also maintain:

```text
rear = -1
```

So the initial state is:

```text
front = rear = -1
```

* * *

## 2\. First Element Insertion

When the first element is inserted:

```text
front = rear = 0
```

The first element is placed at index `0`.

* * *

## 3\. Queue is Full

A Circular Queue is full when the next position of `rear` is `front`.

The condition is:

```python
(rear + 1) % size == front
```

For example, with a queue of size 5:

```text
Index:    0    1    2    3    4
         [10] [20] [30] [40] [50]
          ↑                   ↑
        Front                Rear
```

Here:

```text
(rear + 1) % size
= (4 + 1) % 5
= 0
```

And:

```text
front = 0
```

Therefore:

```text
(rear + 1) % size == front
```

The queue is full.

This is the **overflow condition**.

* * *

## 4\. Deleting an Element

When deleting an element, we remove the element at `front`.

Then `front` moves forward:

```python
front = (front + 1) % size
```

If the deleted element was the last remaining element, we reset:

```text
front = rear = -1
```

This brings the queue back to its initial empty state.

* * *

# Circular Queue Operations

A Circular Queue mainly supports:

### Enqueue

Insert an element at the rear.

```text
enqueue → rear moves
rear = (rear + 1) % size
```

### Dequeue

Remove an element from the front.

```text
dequeue → front moves
front = (front + 1) % size
```

### isEmpty

Checks whether:

```text
front == -1
```

### isFull

Checks whether:

```text
(rear + 1) % size == front
```

* * *

# Circular Queue Implementation in Python

Unlike some of my earlier Queue and Deque implementations, this time I am **not using Python's built-in** `append()`**,** `pop()`**,** `insert()`**, or** `deque` **operations to implement the core behavior**.

Instead, this implementation uses a fixed-size list and manually manages:

*   `front`
    
*   `rear`
    
*   overflow
    
*   underflow
    
*   circular movement
    

This is much closer to the traditional array-based implementation that can be translated to languages such as C, C++, or Java.

```python
class CircularQueue:
    def __init__(self, size):
        self.size = size
        self.items = [None] * size
        self.front = self.rear = -1

    def isEmpty(self):
        return self.front == -1

    def isFull(self):
        return (self.rear + 1) % self.size == self.front

    def enqueue(self, value):
        if self.isFull():
            print(value, "Can't be inserted, the Circular Queue is full")

        elif self.isEmpty():
            self.front = self.rear = 0
            self.items[self.rear] = value
            print("The first element has been inserted:", value)

        else:
            self.rear = (self.rear + 1) % self.size
            self.items[self.rear] = value
            print("Element inserted:", value)

    def dequeue(self):
        if self.isEmpty():
            print("The Circular Queue is empty")

        elif self.front == self.rear:
            print(self.items[self.front], "the last element has been dequeued")

            self.items[self.front] = None
            self.front = self.rear = -1

        else:
            print(self.items[self.front], "has been dequeued")

            self.items[self.front] = None
            self.front = (self.front + 1) % self.size

    def printCQ(self):
        print("The current status of the queue is:", self.items)
```

* * *

# Understanding Enqueue

Let's look at the most important part:

```python
self.rear = (self.rear + 1) % self.size
```

Suppose:

```text
size = 5
rear = 4
```

Then:

```text
rear = (4 + 1) % 5
rear = 0
```

So the rear wraps around.

For example:

```text
Before:

Index:    0      1      2    3    4
         [None] [None] [None][40] [50]
                              ↑     ↑
                            Front  Rear
```

Now insert `60`.

The new rear becomes:

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

So:

```text
Index:    0    1      2      3    4
         [60] [None] [None] [40][50]
          ↑                       ↑
         Rear                    Front
```

The physical array looks unusual, but the logical Circular Queue is:

```text
40 → 50 → 60
```

This is the key idea behind a Circular Queue.

* * *

# Understanding Dequeue

For deletion:

```python
self.items[self.front] = None
self.front = (self.front + 1) % self.size
```

The first statement clears the old position.

The second moves `front` to the next position.

For example:

```text
Before:

[10] [20] [30] [40] [50]
 ↑
front
```

After dequeue:

```text
[None] [20] [30] [40] [50]
         ↑
       front
```

The queue now starts from `20`.

* * *

# The Last Element Case

There is a special condition:

```python
self.front == self.rear
```

This means that the queue currently contains **one element**, assuming the queue is not empty.

For example:

```text
Index:    0    1    2    3    4
         [ ]  [ ]  [ ] [40] [ ]
                       ↑
                  front/rear
```

Since both `front` and `rear` point to the same position, deleting this element means the queue becomes empty.

Therefore:

```python
self.front = self.rear = -1
```

We also clear the array position:

```python
self.items[self.front] = None
```

before resetting the indices.

* * *

# Testing the Circular Queue

Let's create a Circular Queue of size 5:

```python
cq = CircularQueue(5)
```

Initially:

```text
front = -1
rear = -1
```

Trying to dequeue:

```python
cq.dequeue()
```

produces:

```text
The Circular Queue is empty
```

Now insert five elements:

```python
cq.enqueue(10)
cq.enqueue(20)
cq.enqueue(30)
cq.enqueue(40)
cq.enqueue(50)
```

The array becomes:

```text
[10, 20, 30, 40, 50]
```

Now try inserting another element:

```python
cq.enqueue(60)
```

The Circular Queue is full, so:

```text
60 Can't be inserted, the Circular Queue is full
```

This is an **overflow** condition.

* * *

# Reusing Empty Positions

Now remove three elements:

```python
cq.dequeue()
cq.dequeue()
cq.dequeue()
```

The array becomes:

```text
[None, None, None, 40, 50]
```

Now there are three available positions at the beginning.

Insert `60`:

```python
cq.enqueue(60)
```

Since `rear` wraps around:

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

the value `60` is inserted at index `0`.

The array becomes:

```text
[60, None, None, 40, 50]
```

The logical queue is:

```text
40 → 50 → 60
```

This is the major advantage of a Circular Queue.

* * *

# Complete Example

```python
class CircularQueue:
    def __init__(self, size):
        self.size = size
        self.items = [None] * size
        self.front = self.rear = -1

    def isEmpty(self):
        return self.front == -1

    def isFull(self):
        return (self.rear + 1) % self.size == self.front

    def enqueue(self, value):
        if self.isFull():
            print(value, "can't be inserted, the Circular Queue is full")

        elif self.isEmpty():
            self.front = self.rear = 0
            self.items[self.rear] = value
            print("The first element has been inserted:", value)

        else:
            self.rear = (self.rear + 1) % self.size
            self.items[self.rear] = value
            print("Element inserted:", value)

    def dequeue(self):
        if self.isEmpty():
            print("The Circular Queue is empty")

        elif self.front == self.rear:
            print(self.items[self.front], "the last element has been dequeued")
            self.items[self.front] = None
            self.front = self.rear = -1

        else:
            print(self.items[self.front], "has been dequeued")
            self.items[self.front] = None
            self.front = (self.front + 1) % self.size

    def printCQ(self):
        print("The current status of the queue is:", self.items)


cq = CircularQueue(5)

cq.dequeue()

cq.enqueue(10)
cq.enqueue(20)
cq.enqueue(30)
cq.enqueue(40)
cq.enqueue(50)
cq.enqueue(60)

cq.printCQ()

cq.dequeue()
cq.dequeue()
cq.dequeue()

cq.printCQ()

cq.enqueue(60)

cq.printCQ()

cq.dequeue()
cq.dequeue()
cq.dequeue()
cq.dequeue()
```

The important states are:

```text
Initial:
[None, None, None, None, None]

After five insertions:
[10, 20, 30, 40, 50]

After three deletions:
[None, None, None, 40, 50]

After inserting 60:
[60, None, None, 40, 50]

Logical queue:
40 → 50 → 60
```

* * *

# Circular Queue vs Normal Queue

The main difference is how the available array space is reused.

### Normal Linear Queue

```text
[10] [20] [30] [40] [50]
 ↑                       ↑
Front                   Rear
```

After deleting some elements:

```text
[ ] [ ] [ ] [40] [50]
              ↑     ↑
            Front  Rear
```

The empty spaces at the beginning may not be reusable without shifting elements or using another technique.

### Circular Queue

The rear can wrap around:

```text
[60] [ ] [ ] [40] [50]
 ↑                 ↑
Rear              Front
```

The empty positions are reused without shifting the elements.

* * *

# Time Complexity

One of the biggest advantages of the Circular Queue is that its basic operations can be performed in constant time.

| Operation | Time Complexity |
| --- | --- |
| `enqueue()` | O(1) |
| `dequeue()` | O(1) |
| `isEmpty()` | O(1) |
| `isFull()` | O(1) |

The `%` operation allows us to move around the array without traversing it.

* * *

# Applications of Circular Queue

Circular Queues are useful when we have a **fixed amount of memory** and want to reuse freed positions efficiently.

Common applications include:

*   CPU scheduling
    
*   Round-robin scheduling
    
*   Memory buffers
    
*   Keyboard buffers
    
*   Network data buffering
    
*   Streaming data
    
*   Producer-consumer systems
    
*   Resource management
    

A common real-world example is a **buffer** where new data keeps arriving while old data is continuously being processed.

* * *

# Important Things to Remember

If you want to remember Circular Queue quickly, focus on these rules:

```text
Empty:
front = rear = -1

First insertion:
front = rear = 0

Move rear:
rear = (rear + 1) % size

Move front:
front = (front + 1) % size

Full:
(rear + 1) % size == front

One element:
front == rear

After deleting the last element:
front = rear = -1
```

The most important formula is:

```python
(index + 1) % size
```

It is what allows the index to move from the end of the array back to the beginning.

* * *

# Final Thoughts

A Circular Queue solves an important limitation of a basic array-based Queue: **reusing the empty spaces created at the beginning of the array**.

The key idea isn't complicated:

> **When you reach the end, go back to the beginning.**

By maintaining `front` and `rear` and using modulo arithmetic, we can implement insertion and deletion in **O(1)** time without shifting elements.

The Python implementation might look simple, but understanding what is happening underneath is much more important than simply using a built-in data structure.

Once you understand how `front`, `rear`, overflow, underflow, and modulo arithmetic work together, you have a strong foundation for understanding more advanced structures such as **circular buffers, priority queues, and other queue-based algorithms**.