Circular queue implementation and operations

Aditya Narayan Joardar
Last Updated: May 13, 2022

Introduction

While writing a program, we use various data structures to store our data. One of them is Queue. A queue is an abstract, linear data structure in which the input/output technique is FIFO (First IFirst Out). There are many variations among queues like - linear queue, circular queue, priority queue, etc. In this article, we will discuss circular queue implementation and operations using various examples and code snippets.  

Imagine a small doughnut with some divisions. Let the doughnut be the circular queue and the divisions be the positions of the circular queue. Are you having a bit of trouble understanding? No worries, we got you covered with the help of some visual images. 

 

 

The image on the right-hand side 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. 

 

 

When the filling starts, the front pointer points to position 0, and the rear pointer points to the last element’s position. 

 

When the circular queue is filled, the front pointer points to the 0th index, and the rear pointer points to the last index. 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. 

 

  • C Implementation

Here we declare a structure named Circ_Q with three data members: elements (int type array to contain queue elements), front and rear (int type variables to store the front and rear positions). As soon as the constructor is called, some memory is allocated to our circular queue in the physical memory.

//struct to define the circular queue
typedef struct queue{
int elements[MAX_SIZE];
int front, rear;
}Circ_Q;

Operations 

A circular queue is a data container. The basic operations that take place along with their conditions are as follows - 

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

 

2.) Remove elements from the circular queue (deQueue).

a.) Check if the circular queue is empty or not.

b.) If empty, then show an error message.

c.) If not empty, then remove the first element.

d.) Change the pointer values.

 

3.) Display the elements of the circular queue.

a.) Check if the queue is empty or not.

b.) If empty, then show the appropriate message.

c.) If not empty, then print all the elements in the range front … rear.

 

 

  1. Initialization of Circular Queue

In this function, we initialize the circular queue by assigning the front and rear pointers to -1. 

//initialising the circular queue
void initialiseQueue(Circ_Q *cq){
cq->front = -1;
cq->rear = -1; 
}

 

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

 

 

 

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

//func to insert elements to the queue
void enQueue(Circ_Q *cq, int data){


if((cq->front == 0 && cq->rear == MAX_SIZE-1) || (cq->front == cq->rear+1)){
printf("\n Queue Overflow \n\n");
return;
}

if(cq->front == -1){
cq->front = 0;
cq->rear = 0;
}

else{
if(cq->rear == MAX_SIZE-1)
cq->rear = 0;
else
cq->rear += 1;
}

cq->elements [cq->rear] = data;
printf(" %d successfully added to the Circular Queue\n", data);
}

 

  1. Displaying the Circular Queue

As the name suggests, this function prints the circular queue from the front to the rear if it is not empty. 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. 

//func to print the circular queue
void displayQueue(Circ_Q *cq){
int curr_front = cq->front, curr_rear = cq->rear;

if(cq->front == -1){
printf("\n Queue is Empty \n");
return;
}

printf("\n The CIRCULAR QUEUE elements are :\t");

if(curr_front <= curr_rear){
while(curr_front <= curr_rear){
printf("%d  ", cq->elements[curr_front]);
curr_front++;
}
}

else{
while(curr_front <= MAX_SIZE-1){
printf("%d  ", cq->elements[curr_front]);
curr_front++;
}

curr_front = 0;

while(curr_front <= curr_rear){
printf("%d  ", cq->elements[curr_front]);
curr_front++;
}
}

printf("\n");
}

 

Complete C program for Circular Queue Implementation and Operations is below:

//Circular Queue implementation and operations in C

#include <stdio.h>
#define MAX_SIZE 5  //max size of circular queue 

//struct to define the circular queue
typedef struct queue{
int elements[MAX_SIZE];
int front, rear;
}Circ_Q;

//initialising the circular queue
void initialiseQueue(Circ_Q *cq){
cq->front = -1;
cq->rear = -1; 
}

//func to insert elements to the queue
void enQueue(Circ_Q *cq, int data){


if((cq->front == 0 && cq->rear == MAX_SIZE-1) || (cq->front == cq->rear+1)){
printf("\n Queue Overflow \n\n");
return;
}

if(cq->front == -1){
cq->front = 0;
cq->rear = 0;
}

else{
if(cq->rear == MAX_SIZE-1)
cq->rear = 0;
else
cq->rear += 1;
}

cq->elements [cq->rear] = data;
printf(" %d successfully added to the Circular Queue\n", data);
}

//func to delete elements from the circular queue
void deQueue(Circ_Q *cq){
if(cq->front == -1){
printf("\n Queue Underflow \n");
return;
}

printf(" Element deleted from Circular Queue: %d \n", cq->elements[cq->front]);

if(cq->front == cq->rear){
cq->front = -1;
cq->rear = -1;
}

else{
if(cq->front == MAX_SIZE-1)
cq->front = 0;
else
cq->front = cq->front+1;
}
}

//func to print the circular queue
void displayQueue(Circ_Q *cq){
int curr_front = cq->front, curr_rear = cq->rear;

if(cq->front == -1){
printf("\n Queue is Empty \n");
return;
}

printf("\n The CIRCULAR QUEUE elements are :\t");

if(curr_front <= curr_rear){
while(curr_front <= curr_rear){
printf("%d  ", cq->elements[curr_front]);
curr_front++;
}
}

else{
while(curr_front <= MAX_SIZE-1){
printf("%d  ", cq->elements[curr_front]);
curr_front++;
}

curr_front = 0;

while(curr_front <= curr_rear){
printf("%d  ", cq->elements[curr_front]);
curr_front++;
}
}

printf("\n");
}

//main func 
int main(){
Circ_Q Q;

//initialization of the circular queue
initialiseQueue(&Q);

enQueue(&Q, 10);
enQueue(&Q, 20);
enQueue(&Q, 30);
enQueue(&Q, 40);
enQueue(&Q, 50);

displayQueue(&Q);

enQueue(&Q, 60);

deQueue(&Q); 
deQueue(&Q);
deQueue(&Q);
deQueue(&Q);
deQueue(&Q);
deQueue(&Q);

displayQueue(&Q);

return 0; 
}

 

 

Output from command prompt after execution of code:

10 successfully added to the Circular Queue
 20 successfully added to the Circular Queue
 30 successfully added to the Circular Queue
 40 successfully added to the Circular Queue
 50 successfully added to the Circular Queue

The CIRCULAR QUEUE elements are :      10  20  30  40  50

Queue Overflow

Element deleted from Circular Queue: 10
Element deleted from Circular Queue: 20
Element deleted from Circular Queue: 30
Element deleted from Circular Queue: 40
Element deleted from Circular Queue: 50

Queue Underflow

Queue is Empty

--------------------------------
Process exited after 0.05368 seconds with return value 0
Press any key to continue . . .

Complexities:

Time:

In the given C implementation, the time complexity of the insertion and deletion is constant. Thus,

T(n) = O(1) 

Since in the display function, we iterate through the whole circular queue once, its time complexity is,

T(n) = O(n)

Space:

A circular queue of size n is created in the given C implementation as soon as the program is executed. Thus 

Space complexity = O(n)

Frequently Asked Questions

Q1.) What are the ways of circular queue implementation and operations that can be performed?
Ans.) A circular queue can be implemented in various ways depending on the language used by the programmer. This article covers the C implementation along with the operations that can be performed on the circular queue.

Q2.) Why should we use a circular queue? ,
Ans.) In the case of a linear queue, we can traverse through it only once. Due to this, if we remove an element from a linear queue, a new element cannot be added to its position. To overcome this drawback, we use a circular queue, wherein we can traverse the circular queue as many times as we want and perform insertion and deletion.  

Key Takeaways

To summarize, this article revolves around circular queue implementation and operations that can be performed on it. Some of the real-life applications of the circular queue are - Memory Management, CPU Scheduling, Traffic systems.

Feeling confident enough? Try out a question related to circular queue here: Circular Queue

Want to improve your coding skills and increase your chances of getting into famous IT companies? Visit Coding Interview Questions and answers for practice | Python, Java & C++ to start today.

Was this article helpful ?
3 upvotes

Comments

No comments yet

Be the first to share what you think