Previously we have discussed What is Queue. This tutorial is about a Circular queue in Data Structures with Working, need, working, operations, and implementation of the circular queue in Data Structures and Algorithms.
The Circular queue is a modified version of the queue, where the last element is pointing to the first one. This forms a circle-like structure.
What is the need for a circular queue?
The major drawback of the queue was that after some operations of insertion and deletion, the queue becomes unusable.
Therefore, this problem was overcome after the use of a circular queue. In the circular queue, when the pointer reaches the end of the queue, then the elements are inserted at the starting position of the queue.
Working of the circular queue –
The circular queue works on the feature called circular increment. When we reach the end of the queue, the pointer then increments to the first of the queue.
Here, the circular increment is performed by modulo division with the queue size. That is,
if REAR + 1 == 8 (overflow!),
REAR = (REAR + 1)%5 = 0 (start of queue)
Circular Queue Operations –
The circular queue has two pointers namely ‘front’ and ‘rear’ where ‘front’ tracks the front of the queue and ‘rear’ tracks the last elements of the queue. Initially, the value of the front and rear to -1.
Enqueue operation –
Check if the queue is full. If not, insert the first element by incrementing the front pointer. For the first time, the front will be pointing to -1, so it will be set to 0 when you will enqueue the first element.
Dequeue Operation –
First, check if the queue is empty. If not, return the value pointed by the front and circularly increase the index by 1. For the last element, reset the values of the front and rear to -1. But here, checking whether the queue is full has an additional case –
Case 1: FRONT = 0 and REAR == SIZE – 1
Case 2: FRONT = REAR + 1
The second case happens when REAR starts from 0 due to circular increment and when its value is just 1 less than FRONT, the queue is full.
Implementation of the circular queue in C++ –
#include <iostream>
#define SIZE 5
using namespace std;
class Queue {
private:
int items[SIZE], front, rear;
public:
Queue() {
front = -1;
rear = -1;
}
bool isFull() {
if (front == 0 && rear == SIZE - 1) {
return true;
}
if (front == rear + 1) {
return true;
}
return false;
}
bool isEmpty() {
if (front == -1)
return true;
else
return false;
}
void enQueue(int element) {
if (isFull()) {
cout << "Queue is full";
} else {
if (front == -1) front = 0;
rear = (rear + 1) % SIZE;
items[rear] = element;
cout << endl
<< "Inserted " << element << endl;
}
}
int deQueue() {
int element;
if (isEmpty()) {
cout << "Queue is empty" << endl;
return (-1);
} else {
element = items[front];
if (front == rear) {
front = -1;
rear = -1;
}
else {
front = (front + 1) % SIZE;
}
return (element);
}
}
void display() {
int i;
if (isEmpty()) {
cout << endl
<< "Empty Queue" << endl;
} else {
cout << "Front -> " << front;
cout << endl
<< "Items -> ";
for (i = front; i != rear; i = (i + 1) % SIZE)
cout << items[i];
cout << items[i];
cout << endl
<< "Rear -> " << rear;
}
}
};
int main() {
Queue q;
q.deQueue();
q.enQueue(1);
q.enQueue(2);
q.enQueue(3);
q.enQueue(4);
q.enQueue(5);
q.enQueue(6);
q.display();
int elem = q.deQueue();
if (elem != -1)
cout << endl
<< "Deleted Element is " << elem;
q.display();
q.enQueue(7);
q.display();
q.enQueue(8);
return 0;
}
So, in this article, we learned about one of the modified versions of a queue which is quite useful in CPU scheduling and memory management.
