Circular Queue in C++

Circular queue in C++

 

Circular Queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle. It is also called “Ring Buffer”.

Circular Queue in C++

Why Circular Queues?

Once the queue becomes full, we can not insert more elements. Even though we dequeue  few of the elements.

Because the following code –

//Overflow check condition
if (rear == SIZE-1)
cout<<"Overflow condition";
  • After each enqueue, rear value is incremented & once queue is full rear value becomes equal to size – 1
//Enqueue function
void Enqueue(){
rear++;
}

//Dequeue Function
void Dequeue(){
front--;
}
  • So no more elements can be entered & even if dequeue happens, as it only changes the front value & not rear value.

Operations on circular queue :

  • front : Get the front item from the queue.
  • rear : Get the last item from the queue.
  • enQueue() : This function is used to enqueue the element into the circular queue. New element will be added at the rear end of the queue.
  • deQueue() : This function is used to delete the element from the circular queue. Delete operation is done from the front end of the queue.
Enqueue operation on a circular queue
dequeue operation on a circular queue

C++ Program for the implementation of circular queue given below:


//Circular queue C++ program
#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)))
{
cout << "\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)
{
cout << "\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)
{
cout << "\nQueue is Empty";
return;
}

cout << "\nElements in Circular Queue are: ";

if (rear >= front)
{
for (int i = front; i <= rear; i++)
cout<<arr[i]<<" ";
}

else
{
for (int i = front; i < size; i++)
cout<<arr[i]<<" ";

for (int i = 0; i <= rear; i++)
cout<<arr[i]<<" ";
}
}

int main ()
{
Queue q (5);

// Inserting elements in Circular Queue
q.enQueue (10);
q.enQueue (20);
q.enQueue (30);
q.enQueue (40);

// Display elements present in Circular Queue
q.displayQueue ();

// Deleting elements from Circular Queue
cout << "\nDeleted value = " << q.deQueue ();
cout << "\nDeleted value = " << q.deQueue ();

q.displayQueue ();

q.enQueue (50);
q.enQueue (60);
q.enQueue (70);

q.displayQueue ();

return 0;

}
Output:

Elements in circular queue are : 10 20 30 40

Deleted element = 10

Deleted element =20

Elements in circular queue are : 30 40

Elements in circular queue are : 30 40 50 60 70