The circular queue avoids wasting space in the usual implementation of a queue using arrays.
DeQueue - removing an element from the queue;
FRONT and REAR are two pointers used to keep track of the first and last elements in the queue.
As you can see in the image above, after some amount of enqueueing and dequeuing, its size has been reduced.
Indexes 0 and 1 can only be used after the queue has been flushed, when all elements have been removed.
How the circular queue works
A circular queue works on a circular increment process, that is, when we try to increment any variable and reach the end of the queue, we start from the beginning of the queue modulo division with the queue size.
That is:
if REAR + 1 == 5 (overflow!), REAR = (REAR + 1)%5 = 0 (start of queue)
Queue operations work like this:
- Two pointers called FRONT and REAR are used to keep track of the first and last elements in the queue.
- When initializing the queue, we set the value of FRONT and REAR to -1.
- When adding an element, we increment the value of the REAR index and place the new element at the position pointed to by REAR.
- When we dequeue an element, we return the value pointed to by FRONT and gradually increase the FRONT index.
- Before queuing, we check if the queue is full.
- Before removing the queue, we check if the queue is empty.
- When initializing the first element, we set the value of FRONT to 0.
- When removing the last element, we reset the FRONT and REAR values to -1.
However, checking for a full queue has a new additional clause:
- Case 1: FRONT = 0 && REAR == SIZE - 1
- Case 2: FRONT = REAR + 1
The second case occurs when REAR starts at 0 due to circular increment, and when its value is only 1 less than FRONT, the queue is full.
Implementation of a cyclic queue in a programming language
The most common implementation of a queue uses arrays, but an implementation using lists may also be possible.
Implementation using C programming
#include <stdio.h>
#define SIZE 5
int items[SIZE];
int front = -1, rear =-1;
int isFull()
{
if( (front == rear + 1) || (front == 0 && rear == SIZE-1)) return 1;
return 0;
}
int isEmpty()
{
if(front == -1) return 1;
return 0;
}
void enQueue(int element)
{
if(isFull()) printf("\n Queue is full!! \n");
else
{
if(front == -1) front = 0;
rear = (rear + 1) % SIZE;
items[rear] = element;
printf("\n Inserted -> %d", element);
}
}
int deQueue()
{
int element;
if(isEmpty()) {
printf("\n Queue is empty !! \n");
return(-1);
} else {
element = items[front];
if (front == rear){
front = -1;
rear = -1;
} /* В Q есть только один элемент, поэтому мы сбрасываем очередь после ее удаления. */
else {
front = (front + 1) % SIZE;
}
printf("\n Deleted element -> %d \n", element);
return(element);
}
}
void display()
{
int i;
if(isEmpty()) printf(" \n Empty Queue\n");
else
{
printf("\n Front -> %d ",front);
printf("\n Items -> ");
for( i = front; i!=rear; i=(i+1)%SIZE) {
printf("%d ",items[i]);
}
printf("%d ",items[i]);
printf("\n Rear -> %d \n",rear);
}
}
int main()
{
// Ложь, потому что front = -1
deQueue();
enQueue(1);
enQueue(2);
enQueue(3);
enQueue(4);
enQueue(5);
// Невозможно поставить в очередь, потому что front == 0 && rear == SIZE - 1
enQueue(6);
display();
deQueue();
display();
enQueue(7);
display();
// Невозможно поставить в очередь, потому что front == rear + 1
enQueue(8);
return 0;
}
When you run this program, you will get the following:
Inserted -> 1 Inserted -> 2 Inserted -> 3 Inserted -> 4 Inserted -> 5 Queue is full!! Front -> 0 Items -> 1 2 3 4 5 Rear -> 4 Deleted element -> 1 Front -> 1 Items -> 2 3 4 5 Rear -> 4 Inserted -> 7 Front -> 1 Items -> 2 3 4 5 7 Rear -> 0 Queue is full!!
Implementation using C programming ++
#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;
} /* Q имеет только один элемент, поэтому мы удаляем очередь после удаления. */
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;
// Ложь, потому что front = -1
q.deQueue();
q.enQueue(1);
q.enQueue(2);
q.enQueue(3);
q.enQueue(4);
q.enQueue(5);
// Невозможно поставить в очередь, потому что front == 0 && rear == SIZE - 1
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();
// Невозможно поставить в очередь, потому что front == rear + 1
q.enQueue(8);
return 0;
}
When you run this program, you will get the following:
Queue is empty Inserted 1 Inserted 2 Inserted 3 Inserted 4 Inserted 5 Queue is full Front -> 0 Items -> 12345 Rear -> 4 Deleted Element is 1 Front -> 1 Items -> 2345 Rear -> 4 Inserted 7 Front -> 1 Items -> 23457 Rear -> 0 Queue is full
