# What is a Circular Queue?

Before we start to learn about Circular queue, we should first understand, why we need a circular queue, when we already have linear queue data structure.

In a Linear queue, once the queue is completely full, it's not possible to insert more elements. Even if we dequeue the queue to remove some of the elements, until the queue is reset, no new elements can be inserted. You must be wondering why? When we dequeue any element to remove it from the queue, we are actually moving the front of the queue forward, thereby reducing the overall size of the queue. And we cannot insert new elements, because the rear pointer is still at the end of the queue. The only way is to reset the linear queue, for a fresh start.

Circular Queue is also a linear data structure, which follows the principle of FIFO(First In First Out), but instead of ending the queue at the last position, it again starts from the first position after the last, hence making the queue behave like a circular data structure.

## Basic features of Circular Queue

1. In case of a circular queue, `head` pointer will always point to the front of the queue, and `tail` pointer will always point to the end of the queue.
2. Initially, the head and the tail pointers will be pointing to the same location, this would mean that the queue is empty. 3. New data is always added to the location pointed by the `tail` pointer, and once the data is added, `tail` pointer is incremented to point to the next available location. 4. In a circular queue, data is not actually removed from the queue. Only the `head` pointer is incremented by one position when dequeue is executed. As the queue data is only the data between `head` and `tail`, hence the data left outside is not a part of the queue anymore, hence removed. 5. The `head` and the `tail` pointer will get reinitialised to 0 every time they reach the end of the queue. 6. Also, the `head` and the `tail` pointers can cross each other. In other words, `head` pointer can be greater than the `tail`. Sounds odd? This will happen when we dequeue the queue a couple of times and the `tail` pointer gets reinitialised upon reaching the end of the queue. ### Going Round and Round

Another very important point is keeping the value of the `tail` and the `head` pointer within the maximum queue size.

In the diagrams above the queue has a size of `8`, hence, the value of `tail` and `head` pointers will always be between `0` and `7`.

This can be controlled either by checking everytime whether `tail` or `head` have reached the `maxSize` and then setting the value `0` or, we have a better way, which is, for a value `x` if we divide it by `8`, the remainder will never be greater than `8`, it will always be between `0` and `0`, which is exactly what we want.

So the formula to increment the `head` and `tail` pointers to make them go round and round over and again will be, `head = (head+1) % maxSize` or `tail = (tail+1) % maxSize`

## Application of Circular Queue

Below we have some common real-world examples where circular queues are used:

1. Computer controlled Traffic Signal System uses circular queue.
2. CPU scheduling and Memory management.

## Implementation of Circular Queue

Below we have the implementation of a circular queue:

1. Initialize the queue, with size of the queue defined (`maxSize`), and `head` and `tail` pointers.
2. `enqueue`: Check if the number of elements is equal to maxSize - 1:
• If Yes, then return Queue is full.
• If No, then add the new data element to the location of `tail` pointer and increment the `tail` pointer.
3. `dequeue`: Check if the number of elements in the queue is zero:
• If Yes, then return Queue is empty.
• If No, then increment the `head` pointer.
4. Finding the `size`:
• If, tail >= head, `size = (tail - head) + 1`
• But if, head > tail, then `size = maxSize - (head - tail) + 1`

``````/* Below program is written in C++ language */

#include<iostream>

using namespace std;

#define SIZE 10

class CircularQueue
{
int a[SIZE];
int rear;   //same as tail

public:
CircularQueue()
{
rear = front = -1;
}

// function to check if queue is full
bool isFull()
{
if(front == 0 && rear == SIZE - 1)
{
return true;
}
if(front == rear + 1)
{
return true;
}
return false;
}

// function to check if queue is empty
bool isEmpty()
{
if(front == -1)
{
return true;
}
else
{
return false;
}
}

//declaring enqueue, dequeue, display and size functions
void enqueue(int x);
int dequeue();
void display();
int size();
};

// function enqueue - to add data to queue
void CircularQueue :: enqueue(int x)
{
if(isFull())
{
cout << "Queue is full";
}
else
{
if(front == -1)
{
front = 0;
}
rear = (rear + 1) % SIZE;   // going round and round concept
// inserting the element
a[rear] = x;
cout << endl << "Inserted " << x << endl;
}
}

// function dequeue - to remove data from queue
int CircularQueue :: dequeue()
{
int y;

if(isEmpty())
{
cout << "Queue is empty" << endl;
}
else
{
y = a[front];
if(front == rear)
{
// only one element in queue, reset queue after removal
front = -1;
rear = -1;
}
else
{
front = (front+1) % SIZE;
}
return(y);
}
}

void CircularQueue :: display()
{
/* Function to display status of Circular Queue */
int i;
if(isEmpty())
{
cout << endl << "Empty Queue" << endl;
}
else
{
cout << endl << "Front -> " << front;
cout << endl << "Elements -> ";
for(i = front; i != rear; i= (i+1) % SIZE)
{
cout << a[i] << "\t";
}
cout << a[i];
cout << endl << "Rear -> " << rear;
}
}

int CircularQueue :: size()
{
if(rear >= front)
{
return (rear - front) + 1;
}
else
{
return (SIZE - (front - rear) + 1);
}
}

// the main function
int main()
{
CircularQueue cq;
cq.enqueue(10);
cq.enqueue(100);
cq.enqueue(1000);

cout << endl << "Size of queue: " << cq.size();

cout << endl << "Removed element: " << cq.dequeue();

cq.display();

return 0;
}``````

Inserted 10 Inserted 100 Inserted 1000 Size of queue: 3 Removed element: 10 Front -> 1 Elements -> 100 1000 Rear -> 2