A queue is an abstract data structure that contains a collection of elements. Queue implements the FIFO mechanism i.e the element that is inserted first is also deleted first.
Queue can be one linear data structure. But it may create some problem if we implement queue using array. Sometimes by using some consecutive insert and delete operation, the front and rear position will change. In that moment, it will look like the queue has no space to insert elements into it.
Even if there are some free spaces, that will not be used due to some logical problems. To overcome this problem, we will use the circular queue data structure.
What is Circular Queue?
A circular queue is a type of queue in which the last position is connected back to the first position to make a circle. It is also known as a Ring Buffer. In a normal queue, once the queue becomes full, we cannot insert the next element even if there is a space in front of the queue. But using a circular queue, we can use the space to insert elements.
It is a linear data structure that follows the FIFO mechanism. The circular queue is a more efficient way to implement a queue in a fixed size array. In a circular queue, the last element points to the first element making a circular link.
Representation of Circular Queue
Following is the representation of a circular queue, where the front is the index of the first element, and the rear is the index of the last element.
Operations on Circular Queue
There are mainly four operations that can be performed on a circular queue:
- Enqueue: Insert an element into the circular queue.
- Dequeue: Delete an element from the circular queue.
- Front: Get the front element from the circular queue.
- Rear: Get the last element from the circular queue.
Circular Queue using Array
Following is the implementation of a circular queue using an array:
Enqueue Operation on Circular Queue
Enqueue operation is used for inserting an element into the circular queue. The steps to perform the enqueue operation are as follows:
Algorithm for Enqueue Operation
Following are the steps to perform the enqueue operation on a circular queue:
1.Initialize an array or any data structure to store the elements of the circular queue. 2.Initialize two variables front and rear. 3.Check if the circular queue is full. 4.If it is not full, and if the front is -1, set the front to 0. 5.Increment the rear by 1 and store it in the rear index. 6.Update the rear index using rear = (rear + 1) % SIZE.
We have provided the implementation of Enqueue operation on a circular queue using C, C++, Java, and Python. You can choose the language of your choice and view the code.
//C Program#include <stdio.h>#define SIZE 5int items[SIZE];int front =-1, rear =-1;// Check if the queue is fullintisFull(){if((front == rear +1)||(front ==0&& rear == SIZE-1))return1;return0;}// Check if the queue is emptyintisEmpty(){if(front ==-1)return1;return0;}// Adding an elementvoidenQueue(int element){if(isFull())printf("\n Queue is full!! \n");else{if(front ==-1) front =0;
rear =(rear +1)% SIZE;
items[rear]= element;printf("\n Inserted -> %d", element);}}// Display the queuevoiddisplay(){int i;if(isEmpty())printf(" \n Empty Queue\n");else{printf("\n Items -> ");for(i = front; i!=rear; i=(i+1)%SIZE){printf("%d ",items[i]);}printf("%d ",items[i]);}}intmain(){enQueue(1);enQueue(2);enQueue(3);enQueue(4);enQueue(5);display();return0;}
Output
The output obtained is as follows −
Inserted -> 1 Inserted -> 2 Inserted -> 3 Inserted -> 4 Inserted -> 5 Items -> 1 2 3 4 5
Dequeue Operation on Circular Queue
Dequeue operation is used for deleting an element from the circular queue. The steps to perform the dequeue operation are as follows:
Algorithm for Dequeue Operation
Following are the steps to perform the dequeue operation on a circular queue:
1.Check if the circular queue is empty. 2.If the queue is not empty, store the element at the front index. 3.If the front and rear are equal, set the front and rear to -1. 4.Else, increase the front index by 1 using the formula front = (front + 1) % SIZE. 5.At last print the deleted element.
We have provided the implementation of Dequeue operation on a circular queue using C, C++, Java, and Python. You can choose the language of your choice and view the code.
Code for Dequeue Operation in Circular Queue
Following are the programs to remove a element from the circular queue −
#include <stdio.h>#define SIZE 5int items[SIZE];int front =-1, rear =-1;// Check if the queue is fullintisFull(){if((front == rear +1)||(front ==0&& rear == SIZE-1))return1;return0;}// Check if the queue is emptyintisEmpty(){if(front ==-1)return1;return0;}// Adding an elementvoidenQueue(int element){if(isFull())printf("\n Queue is full!! \n");else{if(front ==-1) front =0;
rear =(rear +1)% SIZE;
items[rear]= element;printf("\n Inserted -> %d", element);}}// Deleting an elementintdeQueue(){int element;if(isEmpty()){printf("\n Queue is empty!! \n");return(-1);}else{
element = items[front];if(front == rear){
front =-1;
rear =-1;}else{
front =(front +1)% SIZE;}printf("\n Deleted element -> %d \n", element);return(element);}}// Display the queuevoiddisplay(){int i;if(isEmpty())printf(" \n Empty Queue\n");else{printf("\n Items -> ");for(i = front; i!=rear; i=(i+1)%SIZE){printf("%d ",items[i]);}printf("%d ",items[i]);}}intmain(){enQueue(1);enQueue(2);enQueue(3);display();deQueue();display();return0;}
Output
The output obtained is as follows −
Inserted -> 1 Inserted -> 2 Inserted -> 3 Items -> 1 2 3 Deleted element -> 1 Items -> 2 3
Front Operation on Circular Queue
Front operation is used to get the front element from the circular queue. The steps to perform the front operation are as follows:
Algorithm for Front Operation
1.Check if the circular queue is empty. 2.If not empty, print the front index element/
We have provided the implementation of Front operation on a circular queue using C, C++, Java, and Python. You can choose the language of your choice and view the code.
Code for Front Operation in Circular Queue
Following are the programs to look at the front element of the circular queue −
#include <stdio.h>#define SIZE 5int items[SIZE];int front =-1, rear =-1;// Check if the queue is fullintisFull(){if((front == rear +1)||(front ==0&& rear == SIZE-1))return1;return0;}// Check if the queue is emptyintisEmpty(){if(front ==-1)return1;return0;}// Adding an elementvoidenQueue(int element){if(isFull())printf("\n Queue is full!! \n");else{if(front ==-1) front =0;
rear =(rear +1)% SIZE;
items[rear]= element;printf("\n Inserted -> %d", element);}}// Display the queuevoiddisplay(){int i;if(isEmpty())printf(" \n Empty Queue\n");else{printf("\n Front -> %d ",front);printf("\n Items -> ");for(i = front; i!=rear; i=(i+1)%SIZE){printf("%d ",items[i]);}printf("%d ",items[i]);}}intmain(){enQueue(1);enQueue(2);enQueue(3);display();return0;}
Output
The output obtained is as follows −
Inserted -> 1 Inserted -> 2 Inserted -> 3 Front -> 0 Items -> 1 2 3
Rear Operation on Circular Queue
Rear operation is used to get the last element from the circular queue. The steps to perform the rear operation are as follows:
Algorithm for Rear Operation
1.Check if the circular queue is empty.. 2.If it is not empty, print the element at the rear index.
We have provided the implementation of Rear operation on a circular queue using C, C++, Java, and Python. You can choose the language of your choice and view the code.
Code for Rear Operation in Circular Queue
Following are the programs to looka at the rear element−
#include <stdio.h>#define SIZE 5int items[SIZE];int front =-1, rear =-1;// Check if the queue is fullintisFull(){if((front == rear +1)||(front ==0&& rear == SIZE-1))return1;return0;}// Check if the queue is emptyintisEmpty(){if(front ==-1)return1;return0;}// Adding an elementvoidenQueue(int element){if(isFull())printf("\n Queue is full!! \n");else{if(front ==-1) front =0;
rear =(rear +1)% SIZE;
items[rear]= element;printf("\n Inserted -> %d", element);}}// Display the queuevoiddisplay(){int i;if(isEmpty())printf(" \n Empty Queue\n");else{printf("\n Items -> ");for(i = front; i!=rear; i=(i+1)%SIZE){printf("%d ",items[i]);}printf("%d ",items[i]);printf("\n Rear -> %d \n",rear);}}intmain(){enQueue(1);enQueue(2);enQueue(3);display();return0;}
Output
The output obtained is as follows −
Inserted -> 1 Inserted -> 2 Inserted -> 3 Items -> 1 2 3 Rear -> 2
Circular Queue using Linked List
Following are the implementation of a circular queue using a linked list:
//C Program#include <stdio.h>#include <stdlib.h>structNode{int data;structNode* link;};structNode* front =NULL;structNode* rear =NULL;// Check if the queue is emptyintisEmpty(){return front ==NULL;}// Adding an elementvoidenQueue(int value){structNode* newNode =(structNode*)malloc(sizeof(structNode));
newNode->data = value;
newNode->link =NULL;if(isEmpty()){
front = newNode;}else{
rear->link = newNode;}
rear = newNode;
rear->link = front;printf("\n Inserted -> %d", value);}// Deleting an elementintdeQueue(){int value;if(isEmpty()){printf("\n Queue is Empty!!");return-1;}else{structNode* temp = front;
value = temp->data;if(front == rear){
front = rear =NULL;}else{
front = front->link;
rear->link = front;}free(temp);return value;}}// Display the queuevoiddisplay(){structNode* temp = front;if(isEmpty()){printf("\n Queue is Empty!!\n");}else{printf("\n Front -> ");do{printf("%d ", temp->data);
temp = temp->link;}while(temp != front);printf("\n");}}intmain(){enQueue(14);enQueue(22);enQueue(6);// Display elements present in the queueprintf("Initial Queue ");display();// Deleting elements from queueprintf("\nElement Removed = %d",deQueue());// Display elements present in the queueprintf("\nQueue after deletion an element: ");display();// Inserting elements to queueenQueue(9);//Showing the rear of the queueprintf("\nRear Element = %d", rear->data);enQueue(20);//Showing the front of the queueprintf("\nFront Element = %d", front->data);printf("\nFinal Queue ");display();return0;}
Output
The output obtained is as follows −
Inserted -> 14 Inserted -> 22 Inserted -> 6Initial Queue Front -> 14 22 6 Element Removed = 14 Queue after deletion an element: Front -> 22 6 Inserted -> 9 Rear Element = 9 Inserted -> 20 Front Element = 22 Final Queue Front -> 22 6 9 20
Time Complexity of Circular Queue
Following are the time complexities of the circular queue:
- Enqueue Operation: The time complexity of the enQueue operation is O(1) as we can insert an element at the rear end of the queue in constant time.
- Dequeue Operation: The time complexity of the deQueue operation is O(1) as we can delete an element from the front end of the queue in constant time.
- Front Operation: The time complexity of the front operation is O(1) as we can get the front element of the queue in constant time.
- Rear Operation: The time complexity of the rear operation is O(1) as we can get the rear element of the queue in constant time.
Applications of Circular Queue
Following are some of the applications of a circular queue:
- Memory Management: Circular queues are used in memory management to manage the memory efficiently. It is used to allocate memory to the processes when they are in need of memory.
- Buffer Management: These queues are also useful in buffer management. Consider a situation where data is produced at a faster rate than it is consumed. In such cases, a circular queue is used to store the data temporarily.
- Operating System: Suppose your system has a lot of processes to execute. In such cases, for the better management of processes, the operating system uses a circular queue to allocate the CPU to the processes.
- Traffic Management: Traffic singals are controlled by the circular queue. Let’s say there are three signals, red, yellow, and green. The signals are in a circular queue. When the green signal is on, the next signal will be yellow, and then red. This process will continue in a circular manner.
- Multimedia Player: When we play songs in a multimedia player, the songs are played in a circular manner. Once the last song is played, the first song will be played next. This is done using a circular queue.
In general, when certain tasks are repeated in a circular manner, a circular queue is used to manage the tasks efficiently. Also, when the data is produced at a faster rate than it is consumed, a circular queue is used to store the data temporarily.
Leave a Reply