Circular Queue in data structure

Circular Queue in data structure

5 mins read2.8K Views Comment
Updated on Oct 13, 2023 15:55 IST

This article includes working of Circular Queue in data structure and also implementation of circular queue in python and java.

2022_11_MicrosoftTeams-image-8.jpg

In this article, we will look into the circular queue data structure. We will explore the aspects of working a circular queue and implementation. If you are familiar with the concepts of a queue in data structure, it follows the principle of first in, first out, the circular queue is an extended version. The only difference is that in a circular queue, the last element is connected with the first element of the queue, forming a circle. This can be visualized in the below images.

2022_11_image-30.jpg

Now that we have some idea about circular queues let’s take a look at some other aspects of it.

Table of contents

Need for Circular Queues

You must be wondering, if we have a regular queue, why is there a need for a circular queue? The basic idea behind implementing a circular queue is to nullify the limitations of a conventional queue. A regular queue starts having unusable empty cells within it as the insertion and removal of queue elements goes on. For the unusable empty cells in a regular queue to be used, we have first to empty the entire queue. But in the case of the circular queue, the unusable empty can be used for adding new elements to the queue.

Breadth-First Search Algorithm
Breadth-First Search Algorithm
A graph traversal algorithm called breadth-first search investigates every node in the graph starting with the root node. In this article, we will briefly discuss BFS algorithm.
Red Black Tree
Red Black Tree
Red Balck tree variant of tree data structure which comes under the category of the self-balanced binary search tree. A binary search tree is the most popular variant of the...read more
Tree Traversal in Data Structure
Tree Traversal in Data Structure
Tree traversal is the process of systematically visiting each node in a tree data structure. It involves exploring the nodes in a specific order, such as inorder, preorder, or postorder,...read more

Also explore: Understanding Data Structures in C: Types And Operations

Working of Circular Queue

In a circular queue, like a regular queue, we have a front and a rear of the queue. In the case of a circular queue, if we intend to add additional elements to a full circular queue, the rear moves to the front of the queue. It makes use of the so-called circular increment. At the machine level, a circular queue performs the following operations.

Initial Structure of a Circular queue

·     Two pointers: There are two pointers, namely FRONT and REAR, that track the first and the last element in a queue, respectively.

·     Values of Pointers: Initially the value of FRONT and REAR are set to None or -1.

Enqueue Operations

In an enqueue operation, we add elements to the queue. For this circular queue, follows the below steps:

· First, it checks if the queue is full. If the value of REAR is equal to the size of the queue subtracted by one and the value of FRONT is equal to 0, or it checks if the value of REAR is equal to the value of FRONT subtracted by 1(i.e., (REAR==SIZE(QUEUE) – 1 && FRONT==0) or (REAR==FRONT – 1)).

· Then, on each element insertion, it circularly increases the value of the REAR index by 1. If the REAR index value can no longer be incremented, the subsequent insertion will be at the FRONT of the queue.

Dequeue Operations

In a dequeue operation, we remove elements from the queue. For this circular queue, follow the below steps:

· First, it checks if the queue is empty, meaning the value of FRONT is equal to 1(i.e., FRONT==1).

· Then, if the queue is not empty, it checks if the value of FRONT is equal to the value of REAR. If yes, it sets the value of FRONT and REAR to -1 or None. If the value of FRONT is not equal to REAR, then it checks if the value of FRONT is equal to the size of the queue subtracted by 1(i.e., FRONT==SIZE(queue) – 1).

Now that we have familiarized ourselves with the queue operations in circular queues look at the diagram below to visualize the working of a circular queue.

2022_11_image-27.jpg
2022_11_image-29.jpg

Implementing a Circular Queue

We can make use of arrays to implement a circular queue. Take a look at the below code for reference.

Implementing Circular Queue in Python

 
class CircularQueue():
# constructor of CircularQueue class
# initializing the class
def __init__(self, queue_size):
self.queue_size = queue_size
# initializing queue with none
self.queue = [None for x in range(queue_size)]
self.front = self.rear = -1
# function to insert element
# to a circular queue
def enqueue(self, value):
# check if queue is full
if ((self.rear + 1) % self.queue_size == self.queue_size):
print(" Queue is Full\n")
# check if queue is empty
elif (self.front == -1):
self.front = 0
self.rear = 0
self.queue[self.rear] = value
else:
# next position of rear
self.rear = (self.rear + 1) % self.queue_size
self.queue[self.rear] = value
# function to remove element
# to a circular queue
def dequeue(self):
# check if the queue is empty
if (self.front == -1):
print ("Queue is Empty\n")
# check for a single element
elif (self.front == self.rear):
temp=self.queue[self.front]
self.front = -1
self.rear = -1
return temp
else:
temp = self.queue[self.front]
self.front = (self.front + 1) % self.queue_size
return temp
# function to display the circular
# queue elements
def show_current_queue(self):
# check if queue is empty
if(self.front == -1):
print ("Queue is Empty")
elif (self.rear >= self.front):
print("Current circular queue:", end = " ")
for i in range(self.front, self.rear + 1):
print(self.queue[i], end = " ")
print ()
else:
print ("Current circular queue:", end = " ")
for i in range(self.front, self.queue_size):
print(self.queue[i], end = " ")
for i in range(0, self.rear + 1):
print(self.queue[i], end = " ")
if ((self.rear + 1) % self.queue_size == self.front):
print("Circular Queue Full.")
# create an object of
# the circular queue class
queue_object = CircularQueue(5)
# add elements to the queue
queue_object.enqueue(1)
queue_object.enqueue(2)
queue_object.enqueue(3)
queue_object.enqueue(4)
# show current queue
queue_object.show_current_queue()
# print deleted elements of the queue
print ("Value Removed from queue:", queue_object.dequeue())
print ("Value Removed from queue:", queue_object.dequeue())
# show current queue
queue_object.show_current_queue()
# adding this element to
# the queue
queue_object.enqueue(5)
queue_object.enqueue(6)
# adding this element to
# the queue makes it full
queue_object.enqueue(7)
# show current queue
queue_object.show_current_queue()
Copy code

Output:

Queue is empty

Added Element: 1

Added Element: 2

Added Element: 3

Added Element: 4

Added Element: 5

Queue is full

Front Index: 0

Queue Elements: 

1 2 3 4 5

Rear Index: 4

Value Removed from queue: 1

Front Index: 1

Queue Elements: 

2 3 4 5

Rear Index: 4

Added Element: 7

Front Index: 1

Queue Elements: 

2 3 4 5 7

Rear Index: 0

Queue is full

Implementing Circular Queue in Java

 
// Circular Queue implementation in Java
public class CircularQueue {
// Size of Circular Queue
int queue_size = 5;
int front, rear;
int items[] = new int[queue_size];
CircularQueue() {
front = -1;
rear = -1;
}
// function to check
// if the queue is full
boolean is_queue_full() {
if (front == 0 && rear == queue_size - 1) {
return true;
}
if (front == rear + 1) {
return true;
}
return false;
}
// function to check
// if the queue is empty
boolean is_queue_empty() {
if (front == -1)
return true;
else
return false;
}
// function for adding an element
// to th queue
void enQueue(int element) {
if (is_queue_full()) {
System.out.println("Queue is full");
} else {
if (front == -1)
front = 0;
rear = (rear + 1) % queue_size;
items[rear] = element;
System.out.println("Added Element: " + element);
}
}
// function for removing an element
// from the queue
int deQueue() {
int element;
if (is_queue_empty()) {
System.out.println("Queue is empty");
return (-1);
} else {
element = items[front];
if (front == rear) {
front = -1;
rear = -1;
} /* Q has only one element, so we reset the queue after deleting it. */
else {
front = (front + 1) % queue_size;
}
return (element);
}
}
// function to display the circular
// queue elements
void show_current_queue() {
int i;
if (is_queue_empty()) {
System.out.println("Empty Queue");
} else {
System.out.println("Front Index: " + front);
System.out.println("Queue Elements: ");
for (i = front; i != rear; i = (i + 1) % queue_size)
System.out.print(items[i] + " ");
System.out.println(items[i]);
System.out.println("Rear Index: " + rear);
}
}
public static void main(String[] args) {
CircularQueue queue_object = new CircularQueue();
// Fails because front = -1
queue_object.deQueue();
queue_object.enQueue(1);
queue_object.enQueue(2);
queue_object.enQueue(3);
queue_object.enQueue(4);
queue_object.enQueue(5);
// Fails to enqueue because
// front == 0 && rear == queue_size - 1
queue_object.enQueue(6);
queue_object.show_current_queue();
int elem = queue_object.deQueue();
if (elem != -1) {
System.out.println("Value Removed from queue: " + elem);
}
queue_object.show_current_queue();
queue_object.enQueue(7);
queue_object.show_current_queue();
// Fails to enqueue
queue_object.enQueue(8);
}
}
Copy code

Time and Space complexity of Circular Queue

The queue operations, i.e., enqueue and dequeue, in the case of a circular queue, has a constant time and space complexity.

·     Time complexity: O(1)

·     Space complexity: O(1)

Applications of Circular Queue

A circular queue can have a variety of applications in the programming world. Some of them are listed below:

·     CPU Scheduling: In CPU scheduling algorithms like the Round-Robin algorithm, we use a circular queue for managing processes.

·     Ring Buffers: These implement the circular queue with computer systems to establish communication between processes.

·     Pagination: A circular queue can handle web page pagination effectively.

Final Thoughts

So far in this article, we have managed to cover the following concepts respective to the circular queue data structure:

· What is a queue?

· Difference between a regular queue and a circular queue

· Implementation of Circular Queue in Python and java.

· Time and space complexity of the circular queue.

· Applications of circular queues.

About the Author

This is a collection of insightful articles from domain experts in the fields of Cloud Computing, DevOps, AWS, Data Science, Machine Learning, AI, and Natural Language Processing. The range of topics caters to upski... Read Full Bio