A circular queue is an advanced form of a linear queue. In the linear queue, we can’t insert an element in the queue if the rear is pointing to the last index of the queue and the queue is not completely filled. This causes wastage of memory. To overcome this wastage we use the circular queue.
In a circular queue if the last index is filled then, then the rear points to the first index of the queue. It works on the First In First Out (FIFO) principle.
The red arrow is a front pointer and the black arrow is a rear pointer.
Table of Contents
Basic terminologies
- Front: The first pointer points to the first element in the queue.
- Rear: The rear pointer points to the last element in the queue.
- Enqueue: inserting an element into the queue is called enqueue.
- Dequeue: It is the process of deleting an element from the queue.
Insertion in the circular queue
Step-1:
- Check if the queue is completely filled or not.
- If (rear==queue size-1 AND front==0) OR (rear==front-1) then the queue is completely filled and we can’t insert more elements in it.
Step-2:
- Otherwise ,we check if rear ==queue size-1 then we assign rear =0 else rear =rear+1 and then we insert an element at rear position.
Deletion in the circular queue
Step-1:
- We check if the queue contains any element.
- If front ==-1 then the queue is empty.
Step-2:
- When the queue is not empty and both front and the rear pointer is pointing to the same index then assign front=-1 and rear=-1 Otherwise, if front == queue size-1 then front =0.
C++ program for insertion and deletion in Circular Queue
// C or C++ program for insertion and
// deletion in Circular Queue
#include<bits/stdc++.h>
using namespace std;
struct Queue
{
// Initialize front and rear
int rear, front;
// Circular Queue
int size;
int *arr;
Queue(int s)
{
front = rear = -1;
size = s;
arr = new int[s];
}
void enQueue(int value);
int deQueue();
void displayQueue();
};
/* Function to create Circular queue */
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) /* Insert First Element */
{
front = rear = 0;
arr[rear] = value;
}
else if (rear == size-1 && front != 0)
{
rear = 0;
arr[rear] = value;
}
else
{
rear++;
arr[rear] = value;
}
}
// Function to delete element from Circular Queue
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;
}
// Function displaying the elements
// of Circular Queue
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]);
}
}
/* Driver of the program */
int main()
{
Queue q(5);
// Inserting elements in Circular Queue
q.enQueue(14);
q.enQueue(22);
q.enQueue(13);
q.enQueue(-6);
// Display elements present in Circular Queue
q.displayQueue();
// Deleting elements from Circular Queue
printf("\nDeleted value = %d", q.deQueue());
printf("\nDeleted value = %d", q.deQueue());
q.displayQueue();
q.enQueue(9);
q.enQueue(20);
q.enQueue(5);
q.displayQueue();
q.enQueue(20);
return 0;
}
Elements in Circular Queue are: 14 22 13 -6 Deleted value = 14 Deleted value = 22 Elements in Circular Queue are: 13 -6 Elements in Circular Queue are: 13 -6 9 20 5 Queue is Full
Java program for insertion and deletion in Circular Queue
// Java program for insertion and
// deletion in Circular Queue
import java.util.* ;
class Solution
{
// Structure of a Node
static class Node
{
int data;
Node link;
}
static class Queue
{
Node front, rear;
}
// Function to create Circular queue
static void enQueue(Queue q, int value)
{
Node temp = new Node();
temp .data = value;
if (q .front == null)
q .front = temp;
else
q .rear .link = temp;
q .rear = temp;
q .rear .link = q .front;
}
// Function to delete element from Circular Queue
static int deQueue(Queue q)
{
if (q .front == null)
{
System.out.printf ("Queue is empty");
return Integer.MIN_VALUE;
}
// If this is the last node to be deleted
int value; // Value to be dequeued
if (q .front == q .rear)
{
value = q .front .data;
q .front = null;
q .rear = null;
}
else // There are more than one nodes
{
Node temp = q .front;
value = temp .data;
q .front = q .front .link;
q .rear .link= q .front;
}
return value ;
}
// Function displaying the elements of Circular Queue
static void displayQueue( Queue q)
{
Node temp = q .front;
System.out.printf("\nElements in Circular Queue are: ");
while (temp .link != q .front)
{
System.out.printf("%d ", temp .data);
temp = temp .link;
}
System.out.printf("%d", temp .data);
}
/* Driver of the program */
public static void main(String args[])
{
// Create a queue and initialize front and rear
Queue q = new Queue();
q .front = q .rear = null;
// Inserting elements in Circular Queue
enQueue(q, 14);
enQueue(q, 22);
enQueue(q, 6);
// Display elements present in Circular Queue
displayQueue(q);
// Deleting elements from Circular Queue
System.out.printf("\nDeleted value = %d", deQueue(q));
System.out.printf("\nDeleted value = %d", deQueue(q));
// Remaining elements in Circular Queue
displayQueue(q);
enQueue(q, 9);
enQueue(q, 20);
displayQueue(q);
}
}Elements in Circular Queue are: 14 22 6 Deleted value = 14 Deleted value = 22 Elements in Circular Queue are: 6 Elements in Circular Queue are: 6 9 20
Time Complexity
- enqueue() : O(1).
- dequeue() : O(1).
Application in real life
- In CPU scheduling the job which comes first is executed first.
- A computer-controlled traffic system uses a circular queue for traffic control.