This Tutorial on C++ Circular Queue Data Structure Explains What is Circular Queue, What are the Basic Operations along with Implementation & Applications:
A circular queue is an extension of the basic queue that we have discussed earlier. It is also known as “Ring buffer”.
What is Circular Queue in C++?
A circular queue is a linear data structure that is used to store data items. It performs operations by following the FIFO (First In, First Out) approach and the last position in the queue is connected back to the first position to form a circle.
=> Look For The Entire C++ Training Series Here
Table of Contents:
Circular Queue In C++
The following diagram shows a circular queue.
The above image shows a circular data structure of size 10. The first six elements are already in the queue and we see that the first position and last position are joined. Due to this arrangement, space doesn’t go wasted as it happens in a linear queue.
In a linear queue after the queue is full, we delete the elements from another end, and the status of the queue is still shown as full and we cannot insert more elements.
In the circular queue, when the queue is full, and when we remove elements from the front since last and first positions are connected, we can insert the elements at the rear which was vacated by deleting the element.
In the next section, we will learn about the basic operations of the circular queue.
Basic Operations
Some of the basic operations of the circular queue are as follows:
Front: Returns the front position in the circular queue.
Rear: Returns the rear position in the circular queue.
Enqueue: Enqueue (value) is used to insert an element in the circular queue. The element is always inserted at the rear end of the queue.
We follow the following sequence of steps to insert a new element in the circular queue.
#1) Check if the circular queue is full: test ((rear == SIZE-1 && front == 0) || (rear == front-1)), where ‘SIZE’ is the size of the circular queue.
#2) If the circular queue is full then it displays a message as “Queue is full”. If queue is not full then, check if (rear == SIZE – 1 && front != 0). If it is true then set rear=0 and insert element.
Dequeue: Dequeue function is used to delete an element from the queue. In the circular queue, the element is always deleted from the front end. Given below is the sequence for dequeue operation in a circular queue.
Steps:
#1) Check if the circular queue is Empty: check if (front==-1).
#2) If it is empty then display the message “Queue is empty”. If queue is not empty then perform step 3.
#3) Check if (front==rear). If it is true then set front=rear= -1 else check if (front==size-1), if it is true then set front=0 and return the element.
Illustration
In this section, we will go through a detailed illustration of adding/removing elements in the circular queue.
Consider the following circular queue of 5 elements as shown below:
Next, we insert item 1 in the queue.
Next, we insert an item with value 3.
When we insert the elements to make a queue full, the representation will be as shown below.
Now we delete the two elements i.e. item 1 and item 3 from the queue as shown below.
Next, we insert or enqueue element 11 in the circular queue as represented below.
Again let us insert element 13 in the circular queue. The queue will look as shown below.
We see that in the circular queue we move or insert elements in a circle. Hence we can consume the entire space of the queue till it becomes full.
Implementation
Let’s implement the circular queue using C++.
#include<iostream>
using namespace std;
class Queue {
public:
// Initialize front and rear
int rear, front;
// Circular Queue
int size;
int *circular_queue;
Queue(int sz) {
front = rear = -1;
size = sz;
circular_queue = new int[sz];
}
void enQueue(int elem);
int deQueue();
void displayQueue();
};
/* Function to create Circular queue */
void Queue::enQueue(int elem)
{
if ((front == 0 && rear == size-1) || (rear == (front-1)%(size-1))) {
cout<<"\nQueue is Full";
return;
}
else if (front == -1) { /* Insert First Element */
front = rear = 0;
circular_queue[rear] = elem;
}
else if (rear == size-1 && front != 0) {
rear = 0;
circular_queue[rear] = elem;
}
else {
rear++;
circular_queue[rear] = elem;
}
}
// Function to delete element from Circular Queue
int Queue::deQueue()
{
if (front == -1) {
cout<<"\nQueue is Empty";
return -1;
}
int data = circular_queue[front];
circular_queue[front] = -1;
if (front == rear) {
front = -1;
rear = -1;
}
else if (front == size-1)
front = 0;
else
front++;
return data;
}
//display elements of Circular Queue
void Queue::displayQueue()
{
if (front == -1) {
cout<<"\nQueue is Empty"<<endl;
return;
}
cout<<"\nCircular Queue elements: ";
if (rear >= front) {
for (int i = front; i <= rear; i++)
cout<<circular_queue[i]<<" ";
}
Else {
for (int i = front; i < size; i++)
cout<<circular_queue[i]<<" ";
for (int i = 0; i <= rear; i++)
cout<<circular_queue[i]<<" ";
}
}
//main program
int main()
{
Queue pq(5);
// Insert elements in Circular Queue
pq.enQueue(2);
pq.enQueue(4);
pq.enQueue(6);
pq.enQueue(8);
// Display elements present in Circular Queue
pq.displayQueue();
// Delete elements from Circular Queue
cout<<"\nElement Dequeued = "<<pq.deQueue();
cout<<"\nElement Dequeued = "<<pq.deQueue();
pq.displayQueue();
pq.enQueue(10);
pq.enQueue(12);
pq.enQueue(14);
pq.displayQueue();
pq.enQueue(10);
return 0;
}
Output:
Above shown is the output of circular queue operations. First, we add the elements and then dequeue or remove two elements. Next, we insert or enqueue three more elements in the circular queue. We see that unlike linear queue, the elements are added at the end of the queue.
Linked List Implementation
Let’s discuss the linked list implementation of a circular queue now. Given below is the linked list implementation of the circular queue in C++. Note that we make use of struct to represent each node. The operations are the same as discussed before except that in this case, we have to perform them with respect to the linked list nodes.
The output shows the circular queue after enqueue operation, dequeue and also after the second enqueue operation.
#include<iostream>
using namespace std;
struct Node
{
int data;
struct Node* link;
};
struct PQueue
{
struct Node *front, *rear;
};
/* this functions performs enqueue operation for circular queue */
void enQueue(PQueue *pq,int elem)
{
struct Node *temp = new Node;
temp->data = elem;
if (pq->front == NULL)
pq->front = temp;
else
pq->rear->link = temp;
pq->rear = temp;
pq->rear->link = pq->front;
}
// This function performs dequeue operation for Circular Queue
int deQueue(PQueue *pq)
{
if (pq->front == NULL)
{
cout<<"Queue is empty!!";
return -1;
}
int elem; // item to be dequeued
// item is the last node to be deleted
if (pq->front == pq->rear)
{
elem = pq->front->data;
free(pq->front);
pq->front = NULL;
pq->rear = NULL;
}
else //more than one nodes
{
struct Node *temp = pq->front;
elem = temp->data;
pq->front = pq->front->link;
pq->rear->link= pq->front;
free(temp);
}
return elem ;
}
//display elements of Circular Queue
void displayQueue(struct PQueue *pq)
{
struct Node *temp = pq->front;
while (temp->link != pq->front)
{
cout<<temp->data<<" ";
temp = temp->link;
}
cout<<temp->data;
}
//main program
int main()
{
// Create a circular queue and initialize front and rear
PQueue *pq = new PQueue;
pq->front = pq->rear = NULL;
// Insert/enqueue elements in Circular Queue
enQueue(pq, 1);
enQueue(pq, 3);
enQueue(pq, 5);
cout<<"\nCircular Queue elements after enqueue operation: ";
// Display elements in Circular Queue
displayQueue(pq);
// Delete/dequeue elements from Circular Queue
cout<<"\nDequeued Item: "<<deQueue(pq);
cout<<"\nDequeued Item: "<<deQueue(pq);
cout<<"\nCircular Queue elements after two dequeue operation: ";
// Remaining elements in Circular Queue after dequeue
displayQueue(pq);
enQueue(pq, 7);
enQueue(pq, 9);
cout<<"\nCircular Queue elements after two enqueue operations: ";
displayQueue(pq);
return 0;
}
Output:
Next implementation is a Java program to demonstrate circular queue using the linked list.
import java.util.* ;
class Main
{
// Node structure
static class Node {
int data;
Node link;
}
static class CQueue {
Node front, rear;
}
// Enqueue operation for circular queue
static void enQueue(CQueue cq, int value) {
Node temp = new Node();
temp .data = value;
if (cq .front == null)
cq .front = temp;
else
cq .rear .link = temp;
cq .rear = temp;
cq .rear .link = cq .front;
}
// Dequeue operation for Circular Queue
static int deQueue(CQueue cq) {
if (cq .front == null) {
System.out.printf ("Queue is empty!!");
return Integer.MIN_VALUE;
}
int value; // Value to be dequeued
// the last node to be deleted
if (cq.front == cq.rear) {
value = cq.front.data;
cq.front = null;
cq.rear = null;
}
else { // There are more than one nodes
Node temp = cq.front;
value = temp.data;
cq.front = cq.front.link;
cq.rear.link= cq.front;
}
return value ;
}
// display the elements of Circular Queue
static void displayQueue( CQueue cq)
{
Node temp = cq.front;
while (temp.link != cq.front)
{
System.out.printf("%d ", temp.data);
temp = temp.link;
}
System.out.printf("%d", temp.data);
}
/* main program */
public static void main(String args[])
{
// Create a queue and initialize front and rear
CQueue cq = new CQueue();
cq.front = cq.rear = null;
// Insert/enqueue elements in Circular Queue
enQueue(cq, 2);
enQueue(cq, 4);
enQueue(cq, 6);
System.out.print("\nCircular Queue elements after Enqueue Operation:");
// Display elements in Circular Queue
displayQueue(cq);
// Delete/dequeue elements from Circular Queue
System.out.printf("\nDequeued Item = %d", deQueue(cq));
System.out.printf("\nDequeued Item = %d", deQueue(cq));
System.out.print("\nCircular Queue elements after Dequeue Operation:");
displayQueue(cq);
enQueue(cq, 8);
enQueue(cq, 10);
System.out.print("\nCircular Queue elements after second Enqueue Operation:");
displayQueue(cq);
}
}
Output:
The output of the above program is similar to the previous program.
Applications
Let’s discuss some of the applications of the circular queue.
- CPU Scheduling: Operating system process that requires some event to occur or for some other processes to complete for execution is often maintained in a circular queue so that they execute one after the other when all the conditions are met or when all events occur.
- Memory Management: Use of ordinary queues wastes memory space as already mentioned in our above discussion. Using a circular queue for memory management is beneficial for optimum memory usage.
- Computer Controlled Traffic Signal System: Computerized traffic signals are often added to a circular queue so that they repeat themselves after the specified time interval has elapsed.
Conclusion
Circular queues fix the major disadvantage of a normal queue wherein we cannot insert elements when the rear pointer is at the end of the queue even when we delete the elements and space is emptied. In a circular queue, elements are arranged in a circular fashion, so that space is not wasted at all.
We have also seen the major operations of the circular queue. Circular queues are mostly useful for scheduling purposes and applications like traffic signal systems where the signals glow in turns.
In our next tutorial, we will learn about the double-ended queues that are simply called “deque”.
=> Visit Here To Learn C++ From Scratch