Circular Queue
Circular Queue
Circular Queue is special type queue, which follows First in First Out (FIFO) rule and as well as instead of ending queue at the last position, it starts again from the first position after the last position and behaves like circular linear data structure.
We can say it is extension of the queue data structure such that last element of the queue is associated with the first element of the queue and it is also referred as Circular Buffer. If we talk about normal queue, no additional element can be added if queue if full. Also, we can’t add the element in the queue if there is space left in front of queue, so to overcome this problem Circular Queue comes to the picture, so we can use circular queue to solve this problem with efficient manner.
Operations on Circular Queue
Enqueue Operation in Circular Queue:
- Firstly, we have to whether the queue is full or not
- For adding the first element in the queue, set front to 0
- Increase rear by 1 circularly and add the new element at the position which is pointed by rear
Dequeue Operation in Circular Queue:
- Firstly, we have to check whether the queue is empty or not.
- Return the element which is pointed by front.
- Increase front by 1
- In case of last element of the queue, set values of front and rear to -1
Implementation of Circular Queue
The number of ways for implementing the circular queue using:
- Array
- Linked List
Circular Queue Implementation in C language
Using Array: -
# include < stdio.h >
# define len 7
int queue[len];
int front = -1, rear = -1;
void enQueue(int item) // For add an element to the queue
{
if ((front == rear+1) || (front == 0 && rear == len-1)) // For checking whether the queue is full or not
{
printf("\nQueue is full\n");
return;
}
else
{
if(front == -1)
{
front = 0;
}
rear = (rear+1) % len;
queue[rear] = item;
}
}
void deQueue() // For remove an element from the queue
{
if( front == -1 && rear == -1) // For checking whether the queue is empty or not
{
printf("\nQueue is Empty\n");
return;
}
else
{
printf("\n Deleted Element is %d" , queue[front]);
if(front == rear)
{
front = - 1;
rear = - 1;
}
else
front = (front+1) % len;
}
}
void traverse() //For print the elements of the queue
{
int i = front;
printf("\nFront: ");
while(i != rear)
{
printf("%d ",queue[i]);
i = (i+1) % len;
}
printf("%d",queue[rear]);
printf(" :Rear");
}
int main() // Driver code
{
enQueue(23);
enQueue(33);
enQueue(43);
enQueue(53);
enQueue(63);
enQueue(73);
enQueue(83);
traverse();
deQueue();
traverse();
enQueue(55);
traverse();
return 0;
}
Output
Using LinkedList: -
#include<stdio.h>
#include<stdlib.h>
struct node // For declaration new node
{
int data;
struct node* next;
};
struct node *front = NULL;
struct node *rear = NULL;
void enQueue(int d) // For add an element to the queue
{
struct node * n;
n = (struct node*)malloc(sizeof(struct node));
n->data = d;
n->next = NULL;
if((front == NULL)&&(rear == NULL))
{
front = rear = n;
rear->next = front;
}
else
{
rear->next = n;
rear = n;
n->next = front;
}
}
void deQueue()// For remove an element from the queue
{
struct node* t;
t = front;
if((front == NULL)&&(rear == NULL)) // For checking whether the queue is empty or not
printf("\nQueue is Empty!!");
else if(front == rear)
{
front = rear = NULL;
free(t);
}
else
{
front = front->next;
rear->next = front;
free(t);
}
}
void traverse()//For print the elements of the queue
{
struct node* t;
t = front;
if((front==NULL)&&(rear==NULL))
printf("\nQueue is Empty!!");
else{
printf("Queue elements are:");
do{
printf("%d ",t->data);
t = t->next;
}while(t != front);
}
}
int main() // Driver code
{
int choice,n,i,data;
do{
printf("\n1 for Insert the Data \n2 for print the Data \n3 for Delete the data \n4 for Exit");
printf("\nEnter Your Choice:-");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("\nEnter the number of data: ");
scanf("%d",&n);
printf("\nEnter your data: ");
i=0;
while(i<n){
scanf("%d",&data);
enQueue(data);
i++;
}
break;
case 2:
traverse();
break;
case 3:
deQueue();
break;
case 4:
break;
}
}
while(choice!=4);
return 0;
}
Outputs: -
Circular Queue Implementation in Java language
public class CircularQueue
{
int len = 5;
int front, rear;
int queue[] = new int[len];
CircularQueue()
{
front = -1;
rear = -1;
}
int isFull()// For checking whether the queue is full or not
{
if (front == 0 && rear == len -1 || front == rear + 1 )
{
return 1;
}
return 0;
}
int isEmpty()// For checking whether the queue is empty or not
{
if (front == -1)
return 1;
else
return 0;
}
void enQueue(int item) // For add an element to the queue
{
if (isFull()==1)
{
System.out.println("Queue is full");
}
else
{
if (front == -1)
front = 0;
rear = (rear + 1) % len;
queue[rear] = item;
}
}
int deQueue()// For remove an element from the queue
{
int item;
if (isEmpty()==1)
{
System.out.println("Queue is empty");
return (-1);
}
else
{
item = queue[front];
if (front == rear)
{
front = -1;
rear = -1;
}
else
{
front = (front + 1) % len;
}
return (item);
}
}
void traverse()//For print the elements of the queue
{
int i;
if (isEmpty() == 1)
{
System.out.println("Empty Queue");
}
else
{
System.out.print("Front: ");
for (i = front ; i != rear ; i = (i + 1) % len)
System.out.print(queue[i] + " ");
System.out.print(queue[i]);
System.out.println(" :Rear" );
}
}
public static void main(String[] args)// Driver code
{
CircularQueue q = new CircularQueue();
q.deQueue();
q.enQueue(1);
q.enQueue(2);
q.enQueue(3);
q.enQueue(4);
q.enQueue(5);
q.enQueue(6);
q.traverse();
int element = q.deQueue();
if (element != -1)
{
System.out.println("Deleted Element is " + element);
}
q.traverse();
q.enQueue(7);
q.traverse();
q.enQueue(8);
}
}
Output: -
Time Complexity: -
if we talk about time complexity of enqueue and dequeue operation of a Circular Queue is O(1) for array Implementation.
Advantages of Circular Queue
- No leaks of memory because it doesn’t use dynamic memory.
- Simple implementation
- All operations in constant time O(1)
Applications of Circular Queue
- Memory Management in Operating System
- CPU Scheduling
- Buffering Data Streams
- Trafficking Signal Systems