Circular Queue in Data Structure

Circular queue in data structure is the updated version of normal queue in which the last element is connected to the first element of the queue.

Circular Queue is an important topic of Data Structure. Questions based on Circular queue are sometime asked in GATE examination.

Here we are going to learn about basic concepts of circular queue.

C Program to implement circular queue in Data Structure is also explained in this tutorial.

Frequently Asked Questions

Following questions are generally asked from circular queue –

What is difference between queue and circular queue?
What is circular queue example?
What is circular queue in C++?
What is linear and circular queue?
How do you use a circular queue?
Why is circular queue used?
Write a circular queue program in c.

After reading this circular queue tutorial students will be able to answer the above frequently asked questions.

What is Circular Queue ?

Circular Queue is the Extended version of Linear Queue.
In circular Queue the last element of the circular queue is connected to first element of the Circular Queue.
Circular Queue also follow the First in First Out Policy.

Why Circular Queue in Data Structure ?

Whenever we are deleting one element from the front end of a Linear Queue, all the remaining elements will be shifted in a forward direction.
So each element will be shifted to its preceding location. While shifting, the process would consume so much time. So to avoid this problem the concept of circular queue was introduced.
In a circular queue, the queue is represented in the form of a circle.

Let us consider a circular queue of size 6 as shown in following figure.

Characteristics of Circular Queue Data Structure

Circular Queue has the following characteristics –

Circular queue data structure is a linear data structure.
It is based on First In First Out (FIFO) method.
It also has two ends front and rear based on which all the operations are performed.
Like linear queue, in circular queue also insertion will be done from the rear element and deletion will be from the front element.

Conditions followed by a Circular Queue in Data Structure

If front=-1 and rear=-1, the queue is empty.
If rear=size of queue-1, the queue is full.

If (front=-1 && rear=-1);

{

Queue is empty;

}

If (rear==size-1);

{

Queue is full;

}

Insertion in Circular Queue Data Structure

Different cases of insertion operation in circular queue are as shown in the figure given below –

Step wise step circular queue algorithm for insertion operation is given below-

Case 1: In this case front=0 and rear=max size-1=5. So we can’t insert any more elements in this queue.

Case 2: In this case, rear+1=front, hence no more element can be added to the queue

Case 3: In this case, rear=front=-1. Here the queue is empty and hence the rear should be initialized with 0 and insert the element in the 0^th position.

Case 4: In this case, front=1 and rear=max. size-1=5. Here we can insert the element in the 0^th place. First rear should be initialized with 0 and the element should be inserted.

Case 5: Here front=0 and rear=2. In this case elements can be inserted. Rear should be incremented by 1 and hence rear=3+1=4. Hence the element is to be inserted in the 4^th position.

Note – The time complexity of insert operation is O[1].

Deletion in Circular Queue Data Structure

Different cases of deletion operation

Step wise step circular queue algorithm for deletion operation is given below –

Case 1: In this case, rear=front=-1, and the queue is empty. Hence, we can’t delete any element from the queue.

Case 2: In this case, front has reached rear by deleting all the previous elements. Hence after deleting the 0^th element both front and rear would be reset to -1, i.e. front=rear=-1.

Case 3: In this case front has reached max. size-1=5^th position. To delete the existing elements front should be initialized with 0 and element 43 will be deleted.

Case 4: In this case front=0 and rear=2. When we delete the element 2 (0^th position), the position of front will be incremented by 1.

Note – Time complexity of deletion operation is O[1].

Conclusion and Summary

In this circular queue data structure tutorial we have explained insertion and deletion operation on circular queue.
Circular queue using array is an important topic of data structure.
Circular Queue program in C is also explained in this tutorial.

I hope this Circular Queue tutorial will be helpful for student in understanding the concepts of circular queue.