Last Updated on September 22, 2023 by Mayank Dham
In this Blog, we will talk about circular queue in data structure. We will cover the multiple approaches to implement circular queue in data structure. Also we will see the applications of circular queue in data structure. Circular queue is an efficient data structure in comparison with a simple queue as it doesn’t waste the space allotted to it.
Lets see What Is Circular Queue in Data Structure?
What is Circular Queue in Data Structure?
A circular queue in data structures is a linear arrangement that adheres to the principle of First In First Out (FIFO). Within this structure, the final element is linked to the initial element, creating a circular connection that forms a ring-like configuration, often referred to as a Ring buffer.
How does the Circular queue in data structure work?
A circular queue in data structure works in the process of circular increment i.e. when we’ll increment the pointer and reach the end then pointer points to the beginning of the queue.
Operations of a Circular Queue in Data Structure:
- front(): front is used to track the first element of the queue.
- rear(): rear is used to track the last element of the queue.
- Enqueue: This operation is used to Insert an element at the end of the queue.
- Dequeue: This operation is used to remove and return an element from the front of the queue.
Steps for Enqueue Operation:
- Check if the queue is full.
- If the queue is full then, the print queue is full.
- If not, check the condition(rear == size -1 && front != 0)
- If it is true then set the rear = 0 and insert the new element.
Algorithm to Insert an Element in a Circular Queue in Data Structure
Step 1: IF (REAR+1)%MAX = FRONT
Write " OVERFLOW "
Goto step 4
[End OF IF]
Step 2: IF FRONT = -1 and REAR = -1
SET FRONT = REAR = 0
ELSE IF REAR = MAX – 1 and FRONT ! = 0
SET REAR = 0
ELSE
SET REAR = (REAR + 1) % MAX
[END OF IF]
Step 3: SET QUEUE[REAR] = VAL
Step 4: EXIT
Steps for Dequeue Operations:
- Firstly, check whether the queue is empty or not.
- If the queue is empty then display the queue is empty.
- If not, check the condition(rear == front)
- If the condition is true then set front = rear = -1.
- Else, front == size-1 and return the element.
Algorithm to Delete an Element from the Circular Queue in Data Structure
Step 1: IF FRONT = -1
Write " UNDERFLOW "
Goto Step 4
[END of IF]
Step 2: SET VAL = QUEUE[FRONT]
Step 3: IF FRONT = REAR
SET FRONT = REAR = -1
ELSE
IF FRONT = MAX -1
SET FRONT = 0
ELSE
SET FRONT = FRONT + 1
[END of IF]
[END OF IF]
Step 4: EXIT
Code Implementation
#include<bits/stdc++.h>
using namespace std;
class Queue
{
int rear, front;
int size;
int *arr;
public:
Queue(int s)
{
front = rear = -1;
size = s;
arr = new int[s];
}
void enQueue(int value);
int deQueue();
void displayQueue();
};
void Queue::enQueue(int value)
{
if ((front == 0 && rear == size-1) ||
(rear == (front-1)%(size-1)))
{
printf("\nQueue is Full");
return;
}
else if (front == -1)
{
front = rear = 0;
arr[rear] = value;
}
else if (rear == size-1 && front != 0)
{
rear = 0;
arr[rear] = value;
}
else
{
rear++;
arr[rear] = value;
}
}
int Queue::deQueue()
{
if (front == -1)
{
printf("\nQueue is Empty");
return INT_MIN;
}
int data = arr[front];
arr[front] = -1;
if (front == rear)
{
front = -1;
rear = -1;
}
else if (front == size-1)
front = 0;
else
front++;
return data;
}
void Queue::displayQueue()
{
if (front == -1)
{
printf("\nQueue is Empty");
return;
}
printf("\nElements in Circular Queue are: ");
if (rear >= front)
{
for (int i = front; i <= rear; i++)
printf("%d ",arr[i]);
}
else
{
for (int i = front; i < size; i++)
printf("%d ", arr[i]);
for (int i = 0; i <= rear; i++)
printf("%d ", arr[i]);
}
}
int main()
{
Queue q(5);
// Inserting elements in Circular Queue
q.enQueue(40);
q.enQueue(22);
q.enQueue(30);
q.enQueue(-7);
q.displayQueue();
printf("\nDeleted value = %d", q.deQueue());
printf("\nDeleted value = %d", q.deQueue());
q.displayQueue();
q.enQueue(90);
q.enQueue(20);
q.enQueue(5);
q.displayQueue();
q.enQueue(20);
return 0;
}
import java.util.ArrayList;
class CircularQueue{
private int size, front, rear;
private ArrayList<Integer> queue = new ArrayList<Integer>();
CircularQueue(int size)
{
this.size = size;
this.front = this.rear = -1;
}
public void enQueue(int data)
{
if((front == 0 && rear == size - 1) ||
(rear == (front - 1) % (size - 1)))
{
System.out.print("Queue is Full");
}
else if(front == -1)
{
front = 0;
rear = 0;
queue.add(rear, data);
}
else if(rear == size - 1 && front != 0)
{
rear = 0;
queue.set(rear, data);
}
else
{
rear = (rear + 1);
if(front <= rear)
{
queue.add(rear, data);
}
else
{
queue.set(rear, data);
}
}
}
public int deQueue()
{
int temp;
if(front == -1)
{
System.out.print("Queue is Empty");
// Return -1 in case of empty queue
return -1;
}
temp = queue.get(front);
if(front == rear)
{
front = -1;
rear = -1;
}
else if(front == size - 1)
{
front = 0;
}
else
{
front = front + 1;
}
// Returns the dequeued element
return temp;
}
// Method to display the elements of queue
public void displayQueue()
{
// Condition for empty queue.
if(front == -1)
{
System.out.print("Queue is Empty");
return;
}
System.out.print("Elements in the " +
"circular queue are: ");
if(rear >= front)
{
for(int i = front; i <= rear; i++)
{
System.out.print(queue.get(i));
System.out.print(" ");
}
System.out.println();
}
else
{
for(int i = front; i < size; i++)
{
System.out.print(queue.get(i));
System.out.print(" ");
}
for(int i = 0; i <= rear; i++)
{
System.out.print(queue.get(i));
System.out.print(" ");
}
System.out.println();
}
}
public static void main(String[] args)
{
CircularQueue q = new CircularQueue(5);
q.enQueue(14);
q.enQueue(22);
q.enQueue(13);
q.enQueue(-6);
q.displayQueue();
int x = q.deQueue();
if(x != -1)
{
System.out.print("Deleted value = ");
System.out.println(x);
}
x = q.deQueue();
if(x != -1)
{
System.out.print("Deleted value = ");
System.out.println(x);
}
q.displayQueue();
q.enQueue(9);
q.enQueue(20);
q.enQueue(5);
q.displayQueue();
q.enQueue(20);
}
}
class CircularQueue():
# constructor
def __init__(self, size):
self.size = size
self.queue = [None for i in range(size)]
self.front = self.rear = -1
def enqueue(self, data):
if ((self.rear + 1) % self.size == self.front):
print(" Queue is Full\n")
elif (self.front == -1):
self.front = 0
self.rear = 0
self.queue[self.rear] = data
else:
self.rear = (self.rear + 1) % self.size
self.queue[self.rear] = data
def dequeue(self):
if (self.front == -1): # condition for empty queue
print ("Queue is Empty\n")
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.size
return temp
def display(self):
if(self.front == -1):
print ("Queue is Empty")
elif (self.rear >= self.front):
print("Elements in the circular queue are:",
end = " ")
for i in range(self.front, self.rear + 1):
print(self.queue[i], end = " ")
print ()
else:
print ("Elements in Circular Queue are:",
end = " ")
for i in range(self.front, self.size):
print(self.queue[i], end = " ")
for i in range(0, self.rear + 1):
print(self.queue[i], end = " ")
print ()
if ((self.rear + 1) % self.size == self.front):
print("Queue is Full")
ob = CircularQueue(5)
ob.enqueue(14)
ob.enqueue(22)
ob.enqueue(13)
ob.enqueue(-6)
ob.display()
print ("Deleted value = ", ob.dequeue())
print ("Deleted value = ", ob.dequeue())
ob.display()
ob.enqueue(9)
ob.enqueue(20)
ob.enqueue(5)
ob.display()
Time complexity: O(1)
Implementation of Circular Queue using Linked List
The address part of a linked list, a linear data structure that stores two parts—the data part and the address part—contains the node’s address is a linear data structure that stores two parts—the data part and the address part—contains the address of the node after it. Since the circular queue in this case is implemented using a linked list, the linked list complies with the Queue’s rules. Enqueue and dequeue operations take O(1) time when we implement a circular queue using a linked list.
Code Implementation:
#include <stdio.h>
// Declaration of struct type node
struct node
{
int data;
struct node *next;
};
struct node *front=-1;
struct node *rear=-1;
// function to insert the element in the Queue
void enqueue(int x)
{
struct node *newnode; // declaration of pointer of struct node type.
newnode=(struct node *)malloc(sizeof(struct node)); // allocating the memory to the newnode
newnode->data=x;
newnode->next=0;
if(rear==-1) // checking whether the Queue is empty or not.
{
front=rear=newnode;
rear->next=front;
}
else
{
rear->next=newnode;
rear=newnode;
rear->next=front;
}
}
// function to delete the element from the queue
void dequeue()
{
struct node *temp; // declaration of pointer of node type
temp=front;
if((front==-1)&&(rear==-1)) // checking whether the queue is empty or not
{
printf("\nQueue is empty");
}
else if(front==rear) // checking whether the single element is left in the queue
{
front=rear=-1;
free(temp);
}
else
{
front=front->next;
rear->next=front;
free(temp);
}
}
// function to get the front of the queue
int peek()
{
if((front==-1) &&(rear==-1))
{
printf("\nQueue is empty");
}
else
{
printf("\nThe front element is %d", front->data);
}
}
// function to display all the elements of the queue
void display()
{
struct node *temp;
temp=front;
printf("\n The elements in a Queue are : ");
if((front==-1) && (rear==-1))
{
printf("Queue is empty");
}
else
{
while(temp->next!=front)
{
printf("%d,", temp->data);
temp=temp->next;
}
printf("%d", temp->data);
}
}
void main()
{
enqueue(34);
enqueue(10);
enqueue(23);
display();
dequeue();
peek();
} Applications of Circular Queue in Data Structure
The circular Queue in data structure can be used in the following scenarios:
- Memory Management: Memory management is provided by the circular queue. As we’ve just shown, memory is not managed particularly effectively in a linear queue. However, in the case of a circular queue, the memory is effectively managed by putting the elements in an empty space.
- CPU Scheduling: The circular queue in data structure is another tool the operating system employs to insert and then run programs.
- Traffic System: One of the best instances of a circular queue in a traffic management system controlled by computers is a traffic signal. After each interval of time, each traffic light turns on one at a time. Like when a red light comes on for a minute, followed by a yellow light for a minute, and then a green light. The red light turns on after the green light.
Conclusion
In conclusion, understanding the circular queue in data structures is essential for efficiently managing data and processes that exhibit cyclic behavior. Circular queues combine the properties of both queues and circular structures, offering advantages in resource allocation, buffering, scheduling, and various other applications. Their ability to handle elements in a cyclic manner while maintaining efficient memory utilization makes them a valuable tool in various domains of computer science and engineering.
Frequently Asked Questions (FAQs) about Circular Queue in Data Structure:
Below are the FAQs related to Circular Queue in Data Structure:
1. What is the advantage of using a circular queue?
Circular queues efficiently manage cyclic data or processes and utilize memory effectively by reusing available space.
2. How is a circular queue implemented?
A circular queue can be implemented using arrays or linked lists. In arrays, modulo arithmetic is used to wrap around the queue, while linked lists are modified to form a circular arrangement.
3. What is the significance of circular increment in a circular queue?
Circular increment ensures that when the end of the queue is reached, the next element is positioned at the beginning of the queue, forming a circular structure.
4. What are the main operations supported by a circular queue?
The primary operations of a circular queue include enqueue (addition of an element), dequeue (removal of an element), front (retrieve the front element), rear (retrieve the rear element), and isEmpty (check if the queue is empty).
5. What are the applications of circular queues in data structures?
Circular queues are used in resource allocation, buffering, scheduling, simulation systems, data transmission, print spooling, real-time systems, networking, memory management, and more.