Introduction
A queue is an abstract data type generally used in the same way as the name suggests.
In Queue, the insertion of elements occurs at the rear end, and deletion occurs at the front end, works in (FIFO) manner. There are many variations among queues like - linear queues, circular queues, priority queues, etc.
In this blog, we will discuss the topic of circular queues their representation, different operations we can perform on them, and their implementation.
Representation of a Circular Queue
Let’s take a look at the example = [ 0, 1, 2, 3, 4, 5, 6, 7 ] where the size of the circular queue is 8.
The image below depicts an abstract circular queue. Initially, when a circular queue is created, it is empty, and the front and rear pointers are initialized to -1.
Suppose, initially first four elements are inserted into the circular queue. So, our Front pointer is on the 1st element and the Rear pointer is on the 4th element.
When the insertion of the elements starts, the Front pointer points to position 0, and the rear pointer points to the last inserted element’s position.
When the circular queue is completely filled, the front pointer points to the 0th index of the inserted element, and the rear pointer points to the last index of the inserted element. The main point of highlight is that the front pointer and the rear pointers are connected. Due to this property of the circular queue, it is also known as a “Ring Buffer.”
Circular Queue Implementation and Operations
Circular Queue implementation and operations involve creating the circular queue in our memory and performing various operations. To do so, we can use global variables, structures, or constructors.
In this article, all the circular queue implementation and operations are done in C++ language using struct and no global variables.
User Defined Data Type for Circular Queue
Here we declare a structure named circular_queue with three data members: arr (int type array to contain queue elements), front and rear (int type variables to store the front and rear positions). As soon as the default constructor is called, some memory is allocated to our circular queue in the physical memory.
// Struct to define the circular queue
struct circular_queue{
// Array to store the elements of the queue
int arr[MAX_SIZE];
// Pointers for front and rear end
int front,rear;
}Operations
Different types of operations that can be performed on our circular queue are:
EnQueue
Inserting in the queue in the rear end is called enQueue.
Algorithm:
- Check if the circular queue is full or not.
- If full, then show an error message.
- If not full, then insert the element at the end.
- Change the pointer values.
DeQueue
Deleting from the Queue from the front end is called deque.
Algorithm:
- Check if the circular queue is empty or not.
- If empty, then show an error message.
- If not empty, then remove the first element.
- Change the pointer values.
Display
Showing the current elements of the circular queue.
Algorithm:
- Check if the queue is empty or not.
- If empty, then show the appropriate message.
- If not empty, then print all the elements in the range front -> rear.
Dry Run
Initially, the insertion of elements in the circular queue takes place in the order
10, 20, 30, 40, and 50.
Circular queue(empty):
Insertion of 1st element with value 10:
Insertion of 2nd element with value 20:
Insertion of 3rd element with value 30:
Insertion of 4th element with value 40:
Insertion of 5th element with value 50:
Here, our circular queue is completely full as our front pointer is 0 and our rear pointer is 4 i.e. they are corresponding neighbours if we see in the figure above so no more insertions can be done. If our front pointer is 0 and last pointer is at max size -1 or if we our front pointer is equal to the rear pointer +1 that means they have reached adjacent to each other and, hence our circular queue is full.
Insertion of an element with the value 60:
‘Queue overflow’ message is displayed as our queue is already full.
Display of circular queue:
The elements in order are 10, 20, 30,40, and 50.
Deletion of an element from the circular queue:
As we know, the deletion takes place from the front end so let’s see how our circular queue will look after deletion.
Next Deletion:
Next Deletion:
Next Deletion:
Next Deletion:
Next Deletion:
As we can observe, our circular queue is now empty as our rear and front pointers have value equal to -1 so deletion from the queue is not possible. Hence, an error message is displayed as the output.
Display of Circular queue:
As the queue is empty, there will be no elements that can be displayed so an messgae ‘queue is empty’ is displayed as the output to the user.
C++ Implementation of Operations
1. Initialization of Circular Queue
In this function, we initialize the circular queue by assigning the front and rear pointers to -1.
// Function to initialize the circular queue
void initialiseQueue(circular_queue *cq){
// Setting the front and rear pointers to -1
cq->front = -1;
cq->rear = -1;
}
2. enQueue in Circular Queue
In this function, we pass the circular queue and the element to be added into the circular queue as arguments. This block contains various checks to ensure that the element is correctly inserted as long as there is space in the circular queue. If the circular queue is full, then an error message is displayed. Else, the element is added, and a message is displayed.
// Function to insert elements to the circular queue
void enQueue(circular_queue *cq, int value){
if((cq->front == 0 && cq->rear == MAX_SIZE-1) || (cq->front == cq->rear+1)){
// Queue is already full
cout<<("\n Queue Overflow \n\n");
return;
}
// Queue is empty
if(cq->front == -1){
cq->front = 0;
cq->rear = 0;
}
// Queue contains some elements
else{
// Reached the end of the circular queue
if(cq->rear == MAX_SIZE-1)
cq->rear = 0;
else
// incrementing rear pointer by 1 otherwise
cq->rear += 1;
}
cq->arr [cq->rear] = value;
cout<<(" Element with value ");
cout<<value;
// Successful addition of the element
cout<<(" is successfully added to the Circular Queue\n");
}
3. deQueue in Circular Queue
This function is used for deleting the elements from the circular queue. During deletion, the first element is deleted, then the second, and so on. To do so, we pass the circular queue as an argument. We first check if the circular queue is empty or not. If it is empty, then an error message is displayed. Else, the first element is deleted.
// Function to delete the elements from the circular queue
void deQueue(circular_queue *cq){
// Queue is Empty
if(cq->front == -1){
cout<<("\n Queue is Empty/Deletion is not possible \n");
return;
}
// Element deleted from the front end of the circular queue
cout<<(" Element with value ");
cout<<cq->arr[cq->front];
cout<<(" deleted from Circular Queue\n");
// If Queue contained only 1 element before deletion
if(cq->front == cq->rear){
cq->front = -1;
cq->rear = -1;
}
// Queue contains greater than one element
else{
if(cq->front == MAX_SIZE-1)
cq->front = 0;
else
cq->front = cq->front+1;
}
}
4. Displaying the Circular Queue
As the name suggests, this function prints the circular queue from the front to the rear and also checks if the circular queue is empty or not. To do so, we pass the circular queue as an argument. If the queue is empty, then an appropriate error message is displayed. Else, we print the whole circular queue.
// Function to display the elements of the circular queue
void display_queue(circular_queue *cq){
int curr_front = cq->front, curr_rear = cq->rear;
// Circular queue is empty
if(cq->front == -1){
cout<<("\n Queue is Empty \n");
return;
}
cout<<("\n The Circular Queue elements are :\n");
cout<<" ";
// If front <= rear simply iterate over the arr
if(curr_front <= curr_rear){
while(curr_front <= curr_rear){
cout<<(cq->arr[curr_front]);
cout<<" ";
curr_front++;
}
}
/*
If front >= rear we have to go first
from front to last element(MAX_SIZE-1)
then from 0 to rear end
*/
else{
// Iterating from front to last element(MAX_SIZE-1)
while(curr_front <= MAX_SIZE-1){
cout<<(cq->arr[curr_front]);
cout<<" ";
curr_front++;
}
curr_front = 0;
// Iterating from 0 to rear end
while(curr_front <= curr_rear){
cout<<(cq->arr[curr_front]);
cout<<" ";
curr_front++;
}
}
cout<<"\n";
}Implementation in C++
#include <bits/stdc++.h>
using namespace std;
const int MAX_SIZE=5;
// Struct to define the circular queue
struct circular_queue{
// Array to store the elements of the queue
int arr[MAX_SIZE];
// Pointers for front and rear end
int front,rear;
};
// Function to initialise the circular queue
void initialise_queue(circular_queue *cq){
// Setting the front and rear pointers to -1
cq->front = -1;
cq->rear = -1;
}
// Function to insert elements to the circular queue
void enQueue(circular_queue *cq, int value){
if((cq->front == 0 && cq->rear == MAX_SIZE-1) || (cq->front == cq->rear+1)){
// Queue is already full
cout<<("\n Queue Overflow \n\n");
return;
}
// Queue is empty
if(cq->front == -1){
cq->front = 0;
cq->rear = 0;
}
// Queue contains some elements
else{
// Reached the end of the circular queue
if(cq->rear == MAX_SIZE-1)
cq->rear = 0;
else
// incrementing rear pointer by 1 otherwise
cq->rear += 1;
}
cq->arr [cq->rear] = value;
cout<<(" Element with value ");
cout<<value;
// Successful addition of the element
cout<<(" is successfully added to the Circular Queue\n");
}
// Function to delete the elements from the circular queue
void deQueue(circular_queue *cq){
// Queue is Empty
if(cq->front == -1){
cout<<("\n Queue is Empty/Deletion is not possible \n");
return;
}
// Element deleted from the front end of the circular queue
cout<<(" Element with value ");
cout<<cq->arr[cq->front];
cout<<(" deleted from Circular Queue\n");
// If Queue contained only 1 element before deletion
if(cq->front == cq->rear){
cq->front = -1;
cq->rear = -1;
}
// Queue contains greater than one element
else{
if(cq->front == MAX_SIZE-1)
cq->front = 0;
else
cq->front = cq->front+1;
}
}
// Function to display the elements of the circular queue
void display_queue(circular_queue *cq){
int curr_front = cq->front, curr_rear = cq->rear;
// Circular queue is empty
if(cq->front == -1){
cout<<("\n Queue is Empty \n");
return;
}
cout<<("\n The Circular Queue elements are :\n");
cout<<" ";
// If front <= rear simply iterate over the arr
if(curr_front <= curr_rear){
while(curr_front <= curr_rear){
cout<<(cq->arr[curr_front]);
cout<<" ";
curr_front++;
}
}
/*
If front >= rear we have to go first
from front to last element(MAX_SIZE-1)
then from 0 to rear end
*/
else{
// Iterating from front to last element(MAX_SIZE-1)
while(curr_front <= MAX_SIZE-1){
cout<<(cq->arr[curr_front]);
cout<<" ";
curr_front++;
}
curr_front = 0;
// Iterating from 0 to rear end
while(curr_front <= curr_rear){
cout<<(cq->arr[curr_front]);
cout<<" ";
curr_front++;
}
}
cout<<"\n";
}
// Driver code for main function
int main(){
// Making a circular queue
circular_queue q;
// Initialization of the circular queue
initialise_queue(&q);
// Pushing elements in order 10->20->30->40->50
enQueue(&q, 10);
enQueue(&q, 20);
enQueue(&q, 30);
enQueue(&q, 40);
enQueue(&q, 50);
// Displaying the elements of the circular queue
display_queue(&q);
// Pushing some element
enQueue(&q, 60);
// Deleting elements from the circular queue
deQueue(&q);
deQueue(&q);
deQueue(&q);
deQueue(&q);
deQueue(&q);
deQueue(&q);
display_queue(&q);
return 0;
}Output
Time Complexity
In the given C++ implementation, the time complexity of the insertion and deletion is constant. Thus, deQueue and enQueue operations get executed in O(1) time.
T(n) = O(1) for insertion and deletion
Since in the display function, we iterate through the whole circular queue once, its time complexity is,
T(n) = O(N) for displaying the elements
Where N is the current number of elements in our circular queue.
Space Complexity
A circular queue of size n is created in the given C++ implementation as soon as the program is executed. Thus, O(N) space is required for circular queue implementation where N is the maximum size of our circular queue.
Read about Application of Queue in Data Structure here.
Frequently Asked Questions
What are the different applications of the circular queue?
Circular queues are used in memory management, traffic control systems, and CPU scheduling algorithms.
What is the difference between a circular queue and a linear queue?
A linear data structure known as a queue employs the FIFO (First In, First Out) ordering principle. A circular queue is just a linear queue variation in which the front and back ends are joined to reduce the linear queue's inefficient use of space.
What are the disadvantages of a circular queue?
You can only store as many elements in a circular queue as the length of the queue, therefore you must know the maximum size in advance. In a circular queue, some actions, like deletion or insertion, can be complicated.
Why should we use a circular queue?
If the queue is linear, we can only go through it once. As a result, when an element is removed from a linear queue, no new element may be added to take its place. We utilize a circular queue to solve this problem since it allows for unlimited traversals and insertion and deletion operations.
In which category of data structures does a circular queue lie?
A circular queue lies in the linear category of data structures which follows the FIFO principle.
What are the different ways to implement a circular queue?
There are various methods to implement a circular queue but the most common ones are using arrays and linked lists.
What are queue and their types in data structure?
A queue is a data structure that follows the property of first in first out. There are four kinds of queues available – simple queue, circular queue, priority queue, and double-ended queue.
What are the applications of the priority queue?
Priority queues are used for a lot of computer operations. Dijkstra’s shortest path algorithm, Prim’s algorithm, Huffman code, and Heap sort are some of the algorithms which utilize priority queues. Apart from this, priority queues are also utilized in operating system functionalities such as priority scheduling, load balancing and interrupt handling.
Conclusion
Queues are data structures that resemble real-life queues and support entry from one end and exit from another end. They have several real-life applications which involve the implementation of a stack using two queues, CPU task scheduling, graph traversals, etc.
In this blog, we discussed the topic of circular queues and the different operations that we can perform on them and we saw the implementation of circular queues in C++. Queues are also an important data structure in view of interview preparations and placement. It is therefore imperative to become an expert with queues, understand what goes underneath the hood, and where you can apply your learnings.
Recommended Reading:
- Application of Linked List
- Application of Priority Queue
- Advantages of Circular Queue
- Queue of Pairs in C++ STL
- How to Efficiently Implement K Queues in a Single Array?
- Sorting of Queue
- Implementation of Queue using Arrays in C++
- How to Remove a Specific Element from Queue
- Queue Data Structure and its Applications
Do check out the Interview guide for Product Based Companies, as well as some of the popular interview problems, asked in top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on CodeStudio.
Also, check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, and System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on CodeStudio.
Happy Learning!
