Circular Queue in C++ Programming

Data Structure in C++

What is Circular Queue in C++

A Circular Queue in C++ is a data structure in which elements are stored in a circular manner. In Circular Queue, after the last element, the first element occurs.

A Circular Queue is used to overcome the limitation we face in the array implementation of a Queue. The problem is that when the rear reaches the end and if we delete some elements from the front and then try to add a new element in the queue, it says "Queue is full", but still there are spaces available in the queue. See the example given below.

In the above image, the queue is full because the rear R reached the end of the queue. We have deleted two elements from the queue, so the front F is at index 2. We can see that there are spaces available in the queue, but we can't add a new element because the rear can't go back to index 0.

Operation on Circular Queue

There are two operations possible on the circular queue.

• Add - When we add an element in the circular queue.
• Delete - When we delete an element from the circular queue.

To understand how the above operations work on a circular queue. See the example given below.

From the above image, we can see that when we add a new element in the circular queue, the variable R is increased by R=(R+1)%Size, and the new element is added at the new position of R and te is increased by 1. Similarly, when we delete an element from the circular queue, the variable F is increased by F=(F+1)%Size and te is decreased by 1.

Add Operation in Circular Queue

For add operation in the circular queue first, we check if the value of te is equal to the value of size then, we will display a message Queue is full, else we will increase the value of R by R=(R+1)%Size and add the element in the array at the new location of R and then increased the value of te by 1.

if(te==size)
{
    cout<<"Queue is full\n";
}
else
{
    R=(R+1)%size;
    arr[R]=new_item;
    te=te+1;
}

Delete Operation in Circular Queue

For delete operation in the circular queue first, we check if the value of te is 0 then, we will display a message Queue is empty, else we will display the deleted element on the screen and then increase the value of F by F=(F+1)%Size and then decrease the value of te by 1.

if(te==0)
{
    cout<<"Queue is empty\n";
}
else
{
    cout<<"Element Deleted = "<<arr[F];
    F=(F+1)%size;
    te=te-1;
}

Program of Circular Queue using Array

Below is the complete program of circular queue in C++ using an array having size 5.

#include <iostream>
#include <conio.h>
#include <stdlib.h>

using namespace std;

#define size 5

int main()
{
    int arr[size],R=-1,F=0,te=0,ch,n,i,x;

    for(;;)		// An infinite loop
    {
        system("cls");		// for clearing the screen
        cout<<"1. Add\n";
        cout<<"2. Delete\n";
        cout<<"3. Display\n";
        cout<<"4. Exit\n";
        cout<<"Enter Choice: ";
        cin>>ch;

        switch(ch)
        {
            case 1:
                if(te==size)
                {
                    cout<<"Queue is full";
                    getch();	// pause the loop to see the message
                }
                else
                {
                    cout<<"Enter a number ";
                    cin>>n;
                    R=(R+1)%size;
                    arr[R]=n;
                    te=te+1;
                }
                break;

            case 2:
                if(te==0)
                {
                    cout<<"Queue is empty";
                    getch();	// pause the loop to see the message
                }
                else
                {
                    cout<<"Number Deleted = "<<arr[F];
                    F=(F+1)%size;
                    te=te-1;
                    getch();	// pause the loop to see the number
                }
                break;

            case 3:
                if(te==0)
                {
                    cout<<"Queue is empty";
                    getch();	// pause the loop to see the message
                }
                else
                {
                    x=F;
                    for(i=1; i<=te; i++)
                    {
                        cout<<arr[x]<<" ";
                        x=(x+1)%size;
                    }
                    getch();	// pause the loop to see the numbers
                }
                break;

            case 4:
                exit(0);
                break;

            default:
                cout<<"Wrong Choice";
                getch();	// pause the loop to see the message
        }
    }
    return 0;
}

In the above program, we have defined a macro named size having value 5 using the statement #define. We can use the word size to declare the size of the array as int arr[size]. When we run the above program, the word size will be replaced by its value 5. So the size of the array will be 5.