Circular Queue in data structure
This article includes working of Circular Queue in data structure and also implementation of circular queue in python and java.
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.
Now that we have some idea about circular queues let’s take a look at some other aspects of it.
Table of contents
Best-suited Data Structures and Algorithms courses for you
Learn Data Structures and Algorithms with these high-rated online courses
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.
Read Later
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.
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 classqueue_object = CircularQueue(5)
# add elements to the queuequeue_object.enqueue(1)queue_object.enqueue(2)queue_object.enqueue(3)queue_object.enqueue(4)
# show current queuequeue_object.show_current_queue()
# print deleted elements of the queueprint ("Value Removed from queue:", queue_object.dequeue())print ("Value Removed from queue:", queue_object.dequeue())
# show current queuequeue_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 fullqueue_object.enqueue(7)
# show current queuequeue_object.show_current_queue()
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); }
}
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.
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
Top Picks & New Arrivals
