Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Representation of a Circular Queue
3.
Circular Queue Implementation and Operations
3.1.
User Defined Data Type for Circular Queue
3.2.
Operations 
3.2.1.
EnQueue 
3.2.2.
DeQueue
3.2.3.
Display 
3.3.
Dry Run
3.4.
C++ Implementation of Operations
4.
Implementation in C++ 
4.1.
Output
5.
Time Complexity
5.1.
Space Complexity
6.
Frequently Asked Questions
6.1.
What are the different applications of the circular queue?
6.2.
What is the difference between a circular queue and a linear queue?
6.3.
What are the disadvantages of a circular queue?
6.4.
Why should we use a circular queue?
6.5.
In which category of data structures does a circular queue lie?
6.6.
What are the different ways to implement a circular queue?
6.7.
What are queue and their types in data structure?
6.8.
What are the applications of the priority queue?
7.
Conclusion
Last Updated: Mar 27, 2024
Easy

Circular Queue Implementation and Operations

Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction

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. 

Introduction image

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.

Representation image 1

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. 

Representation image 2

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.”

Representation image 3
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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:

  1. Check if the circular queue is full or not.
  2. If full, then show an error message.
  3. If not full, then insert the element at the end.
  4. Change the pointer values.

DeQueue

Deleting from the Queue from the front end is called deque.

Algorithm:

  1. Check if the circular queue is empty or not.
  2. If empty, then show an error message.
  3. If not empty, then remove the first element.
  4. Change the pointer values.

Display 

Showing the current elements of the circular queue.

Algorithm:

  1. Check if the queue is empty or not.
  2. If empty, then show the appropriate message.
  3. 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):

Dry run image 1

Insertion of 1st element with value 10:

Dry run image 2

Insertion of 2nd element with value 20:

Dry run image 3

Insertion of 3rd element with value 30:

Dry run image 4

Insertion of 4th element with value 40:

Dry run image 5

Insertion of 5th element with value 50:

Dry run image 6

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.

Dry run image 7

Next Deletion:

Dry run image 8

Next Deletion:

Dry run image 9

Next Deletion:

Dry run image 10

Next Deletion:

Dry run image 11

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

Output image 1

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.

You can also read about the topic -  hash function in data structure

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:

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 Coding Ninjas Studio.

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 Coding Ninjas Studio.

Happy Learning!

Previous article
What is the Difference Between Simple Queue and Circular Queue?
Next article
Implement Dynamic Deque using Templates Class and a Circular Array
Live masterclass