Circular Queue Program in C++ : Data Structure

In this article, We will see an important concept of Data structure, Circular Queue that is a type of Queue Data Structure, after going through the whole article you will come to know about Circular Queue, How to implement Circular Queue, Program and the Time and Space Complexities.

What is Circular Queue?

Circular queue is a Linear data Structure that is a Extended or Expanded form of Normal Queue. It works on the principle of FIFO (First in First Out) means that the element that comes first that will be deleted first (if you do delete operation).

Operations in Circular Queue

enQueue : It is used to insert element in the queue.
deQueue : It is used to delete the element from queue. In a circular queue, the element is always deleted from the front position.

Circular Queue Program in C++

There are 2 programs are given below to implement Circular queue in C++

Program 1

#include<iostream>
#define MAX 50
using namespace std;

// gloabal variables – queue_array, front, rear
int queue[MAX];
int front=-1,rear=-1;

// Utility to Enqueue an element to the Queue
void enqueue(int num)
{
if((rear==MAX-1 && front==0) || (front==rear+1))
{
cout<<“Queue is Full !!\n”;
return;
}

if(rear == MAX-1) // front != 0
rear = -1;
rear++;
queue[rear] = num;
if(front == -1)
front=0;
}

// Utility to Dequeue an element from Queue
void dequeue()
{
if(front==-1)
{
cout<<“Queue is Empty !!\n”;
return;
}
int number;
number = queue[front];
queue[front] = INT_MAX;

if(front == rear)
{
front = -1;
rear = -1;
}
else if(front == MAX-1) //rear != MAX-1
front = 0;
else
front++;

cout<<“Dequeued element = “<<number<<“\n”;
}
// Utility to display Front of Queue

void disp_queue()
{
if(front == -1)
{
cout<<“Queue is Empty !!\n”;
return;
}
int i;
for(i=0;i<MAX;i++)
{
if(queue[i] == INT_MAX)
continue;
cout<<queue[i]<<” “;
}
cout<<“\n”;
}

// Driver Code
int main()
{
int optn,number;

for(int i=0;i<MAX;i++)
queue[i] = INT_MAX;

while(1)
{
cout<<“\nOperations available : \n”;
cout<<“1. ENQUEUE\n2. DEQUEUE\n3. DISPLAY queue\n4. Exit\n\n”;
cout<<“Enter your choice : “;
cin>>optn;

switch(optn)
{
case(1):
cout<<“Enter the number : “;
cin>>number;
enqueue(number);
break;
case(2):
dequeue();
break;
case(3):
disp_queue();
break;
case(4):
exit(0);
default :
cout<<“Enter a valid Number”;
}
}
return 0;
}

Output

Program 2

#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;
}

Time and Space complexity of Linear Search

Time Complexity in Linear Search

enQueue : O(1)
deQueue : O(1)

Space Complexity in Binary Search

Space complexity : O(N)

Advantages of Linear Search

Memory Optimization
Better Performance than Linear Queue
Easy to Implement.

Disadvantages of Linear Search

It has limited capacity, which can lead to overflow and data loss.
These are more complex to implement than a simple linear queue.

Hope all your doubt will be Cleared after reading the whole Article Carefully. You can connect with us using the following links :

Important Links

Join WhatsApp	Click Here
Join Telegram	Click Here
Join Twitter (X)	Click Here
Join Instagram	Click Here