Updated March 13, 2023
Introduction to Circular queue in Data Structure
A circular queue is a data structure that helps to store the data linearly and is similar to the normal simple queue but with functionality where the last element is connected to the first one. This facilitates the insertion of the new element in the queue even when the queue is full, provided the first place of the queue is empty. This article will learn about the circular queue, the applications and usage of the circular queue, and learn about the operations that can be performed on a circular queue and an example using the C programming language for implementation.
Structure of Circular Queue
The operations performed on the circular queue are based on a FIFO basis which stands for first in first out principle, which means that the first element which is inserted in the circular queue will also be the first one that will be removed. Thus, the circular queue is also known as the ring buffer commonly. The end of the queue from where we perform the insertion of new elements in the queue, also known as enqueue operation, is called the rear position while the end from where we perform the delete operation is called the front end. The following figure shows the visual representation of the working of the circular queue and how the data is stored in it.
The circular queue right now contains five elements, and the front is pointing to the 0th element while the rear is to the 4th index element. If the insertion is made, then the rear will be increased by one, which means rear = rear + 1 while be done for en queue operation. In case if we want to perform the delete operation, then the front will be increased by one, which means that front = front + 1, and the element at the 0th index will be deleted, which is also called dequeued.
Operations on circular queue
The following operations can be made on the circular queue –
- Rear – This operation will retrieve the last element of the circular queue.
- Front – This operation will help in retrieving the first element of the circular queue.
- enQueue(value) – This operation will perform the insertion of the new value, which is supplied as the argument between the parenthesis to this enQueue function. The en queue operation will always be performed from the rear end of the circular queue.
While performing the enqueue operation, the algorithm will check if the queue is already occupied or full by checking the condition rear is equal to the size of queue -1 and front is exactly equal to 0 or the condition that becomes full for the queue is rear will be equal to front -1. When we denote front by f and rear by r, the condition will be as shown below –
((r==size-1 && f==0) || (r == front-1))
Then the algorithm will display that the queue is full of the above condition evaluates to true. If the condition results in false, then a new element will get inserted from the rear side, setting the rear to 0 if the queue is already full or incrementing it by one in another case.
- Dequeue() –
This operation will result in the deletion of one element from the element which was pointed by the front resulting in decreasing the value of the front by 1 in the circular queue. While performing the deletion, the algorithm checks whether the queue is empty using the condition front is exactly equal to -1, that is, f == -1. If the condition evaluates to true, then it will display that the circular queue is empty, and if not, then it will check if the front is exactly equal to the rear and, if so, set the front value as rear minus 1, i.e. f= =r-1. If not, then the check whether the front is equal to the size minus 1 is done, i.e. f == r-1, and if it results in true, then the front is set to 0, f= 0, and the deleted element value is returned.
Implementation of the circular queue
The operations which we discussed previously on the circular queue can be used using any programming language. Let us see how we can implement a circular queue using a C programming language. The following program implements the circular queue, and the names of the functions are self-defining.
#include<bits/stdc++.h>
using namespace std;
struct CircularQueue
{
// Initialize the value of front and rear ends
int r, f;
// Specifications of Circular Queue
int size;
int *arr;
CircularQueue(int s)
{
f = r = -1;
size = s;
arr = new int[s];
}
void insertInCircularQueueORenQueue(int value);
int deleteFromCircularQueueORdeQueue();
void showQueue();
};
/* Function to create Circular queue */
void CircularQueue:: insertInCircularQueueORenQueue(int value)
{
if ((f == 0 && r == size-1) ||
(r == (f-1)%(size-1)))
{
printf("\nQueue is completely occupied or Full");
return;
}
else if (f == -1) /* Add First value*/
{
f = r = 0;
arr[r] = value;
}
else if (r == size-1 && f != 0)
{
r = 0;
arr[r] = value;
}
else
{
r++;
arr[r] = value;
}
}
int CircularQueue:: deleteFromCircularQueueORdeQueue()
{
if (f == -1)
{
printf("\nCircular Queue is Empty");
return INT_MIN;
}
int data = arr[f];
arr[f] = -1;
if (f == r)
{
f = -1;
r = -1;
}
else if (f == size-1)
f = 0;
else
f++;
return data;
}
void CircularQueue::showQueue()
{
if (f == -1)
{
printf("\nCircular Queue is Empty");
return;
}
printf("\nCircular queue currently contains the following elements : ");
if (r >= f)
{
for (int i = f; i <= r; i++)
printf("%d ",arr[i]);
}
else
{
for (int i = f; i < size; i++)
printf("%d ", arr[i]);
for (int i = 0; i <= r; i++)
printf("%d ", arr[i]);
}
}
int main()
{
CircularQueue q(5);
// Insert few elements in Queue
1. insertInCircularQueueORenQueue(14);
2. insertInCircularQueueORenQueue(22);
3. insertInCircularQueueORenQueue(13);
4. insertInCircularQueueORenQueue(-6);
// Show all the current elements present in the circular queue
q.showQueue();
// Delete the elements from the queue
printf("\nElement deleted from circular queue = %d", q. deleteFromCircularQueueORdeQueue());
printf("\nElement deleted from circular queue = %d", q. deleteFromCircularQueueORdeQueue());
q.showQueue();
1. insertInCircularQueueORenQueue(9);
2. insertInCircularQueueORenQueue(20);
3. insertInCircularQueueORenQueue(5);
q.showQueue();
1 insertInCircularQueueORenQueue(20);
return 0;
}
The output of the above code is as shown below –
Conclusion
The circular queue is a linear data structure whose end is connected to the start and is used in the traffic system, memory management, and CPU scheduling.
Recommended Articles
This is a guide to the Circular queue in Data Structure. Here we discuss the operations that can be performed on a circular queue, along with an example. You may also have a look at the following articles to learn more –
