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
- 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.
- Initially, the head and the tail pointers will be pointing to the same location, this would mean that the queue is empty.
- 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.
- 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.
- The head and the tail pointer will get reinitialised to 0 every time they reach the end of the queue.
- 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:
- Computer controlled Traffic Signal System uses circular queue.
- CPU scheduling and Memory management.
Implementation of Circular Queue
Below we have the implementation of a circular queue:
- Initialize the queue, with size of the queue defined (maxSize), and head and tail pointers.
- 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.
- 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.
- 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
int front; //same as head
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