Circular Queue Data Structure, C or C++ Program for Insertion, Deletion and Traversing Operations of Circular Queue.

 Circular Queue:-

Circular queue is a special type of queue in which last position and first position are assumed as adjacent position. It means in circular queue first position will occur after last position. It is a linear data structure. It is collection of ordered data elements. It is also known as FIFO system or FCFS system. It means an element which is inserted first will be deleted first. Here data elements will be inserted from one end of queue called rear and deleted from the other end called front. We can use Array or Linked list representation to store circular queue in memory.  Hence, we assume first and last position are adjacent in circular queue and resolve this problems of linear/static queue. It is more effective technique than physical queue.

सर्कुलर क्यू एक विशेष प्रकार का क्यू होता है जिसमे फर्स्ट और लास्ट पोजीशन को एक दुसरे के नजदीक(आस-पास) माना जाता है  अर्थात लास्ट पोजीशन के बाद हमेशा फर्स्ट पोजीशन आती है। यह एक लीनियर डाटा स्ट्रक्चर है। यह क्रमबद्ध डाटा एलेमेंट्स का संग्रह है। इसे FIFO (फर्स्ट इन फर्स्ट आउट) या FCFS (फर्स्ट कम फर्स्ट सर्व) सिस्टम के नाम से भी जाना जाता है अर्थात सर्कुलर क्यू में यदि किसी एलिमेंट को सबसे पहले इन्सर्ट किया जाता है, तब उसे ही सबसे पहले डिलीट किया जाता है। यहाँ एलिमेंट का इंसर्शन क्यू के रियर छोर पर तथा डिलीशन फ्रंट छोर से किया जाता है। हम अरे एवं लिंक्ड लिस्ट में से किसी एक का प्रयोग कर मेमोरी में सर्कुलर क्यू तैयार कर सकते है। सर्कुलर क्यू में मेमोरी का प्रभावी उपयोग होता है अत: फर्स्ट और लास्ट पोजीशन को एक दुसरे के नजदीक(आस-पास) मानकर, हम लीनियर क्यू की समस्या को हल कर सकते है। यह फिजिकल क्यू की तुलना में अधिक विश्वसनीय होता है।    

Circular Queue

Operations performed on circular queue are as follows:-

सर्कुलर क्यू पर किये जाने वाले ऑपरेशन निम्न है- 

1.) Insertion:- 

To add new element in cqueue is called insertion operation. This work is done on rear of circular queue. If front=0 and rear=N-1 or front=rear+1, It means cqueue is full and insertion operation is performed, then overflow condition will occur. If first element is inserted in cqueue then set front=rear=0. If rear=N-1 and front != 0, then we set rear=0 otherwise rear is increased by 1.

सर्कुलर क्यू में किसी नए एलिमेंट को जोड़ना, इंसर्शन ऑपरेशन कहलाता है। यह कार्य सर्कुलर क्यू के रियर पर किया जाता है यदि rear=N-1 अर्थात क्यू फुल हो एवं इंसर्शन ऑपरेशन किया जाये, तब ओवरफ्लो कंडीशन उत्पन्न होती है। यदि क्यू में पहले एलिमेंट का इंसर्शन किया जाता है तब front=rear=0 सेट किया जाता है। यदि rear=N-1 है एवं front !=0 तब rear=0 सेट किया जाता है अन्यथा रियर को एक से बढाया जाता है। 

2.) Deletion:- To remove/ delete an element from cqueue is called deletion. This work is done by front of queue. If front=-1 It means cqueue is empty and we perform deletion operation then underflow condition will occur. If last element (front=rear) is remained in queue then set front=rear= -1. if front=N-1 then set front=0 otherwise front is increased by 1.

सर्कुलर क्यू से किसी एलिमेंट को हटाना/ निकालना , डिलीशन ऑपरेशन कहलाता है। यह कार्य सर्कुलर क्यू के फ्रंट से किया जाता है। यदि front=-1 अर्थात सर्कुलर क्यू खाली हो एवं डिलीशन ऑपरेशन किया जाये, तब अंडरफ्लो कंडीशन उत्पन्न होती है। यदि क्यू में अंतिम एलिमेंट (front=rear) का डिलीशन किया जाता है तब front=rear=-1 सेट किया जाता है। यदि front=N-1 तब front=0 सेट किया जाता है अन्यथा फ्रंट को एक से बढाया जाता है।    

3.) Traversing:- To visit/ print of all elements of queue is called traversing. This work is done from front to rear of queue. If front= -1, it means queue is empty and then Traversing operation cant be performed.

क्यू में उपस्थित सभी एलिमेंट को ट्रेवर्स/ विजिट/एक्सेस/प्रिंट करना, ट्रेवरसींग ऑपरेशन कहलाता है। यह कार्य front से rear तक किया जाता है। यदि front=-1 अर्थात क्यू खाली है, तब ट्रेवरसींग ऑपरेशन नहीं किया जा सकता है। यदि front<=rear तब एक लूप i=front से i<=rear तक रन किया जाता है अन्यथा दो लूप रन किया जाता है जिसमे  पहला लूप  i=front से i<=N-1 तक तथा दूसरा लूप i=0 से i<=rear तक रन किया जाता है।  

Example Program:-

C++ or C Program for Insertion,Deletion,Traversing Operations of Circular Queue

File Name:- cqueue.cpp

#include<iostream.h>

#include<conio.h>

#define N 5

int cqueue[N],front=-1,rear=-1,item;

//insertion function

void cinsertion(){

if(((front==0)&&(rear==N-1))||(front==rear+1)){

cout<<"Overflow Condition"<<endl;

getch();

return;

}

cout<<"Enter an Item to insert"<<endl;

cin>>item;

if(rear==-1)

front=rear=0;

else{

if(rear==N-1){

rear=0;}

else{

rear++;

}

}

cqueue[rear]=item;

cout<<item<<" is inserted in circular queue"<<endl<<"insertion completed"<<endl;

getch();

return;

}

//deletion function

void cdeletion(){

if(front==-1){

cout<<"underflow Condition"<<endl;

getch();

return;

}

item=cqueue[front];

if(front==rear){

front=rear=-1;

}

else

{if(front==N-1){

front=0;

}

else{

front++;

}

}

cout<<item<<" is deleted from circular queue"<<endl<<"deletion completed"<<endl;

getch();

return;

}

//traversing function

void ctraversing(){

int i;

if(front==-1){

cout<<"circular queue is empty"<<endl;

getch();

return;

}

cout<<"Circular Queue is: "<<endl;

if(rear>=front){

for(i=front;i<=rear;i++){

cout<<cqueue[i]<<" ";

}

}

else{

for(i=front;i<=N-1;i++){

cout<<cqueue[i]<<" ";

}

for(i=0;i<=rear;i++){

cout<<cqueue[i]<<" ";

}

}

cout<<endl<<"front= "<<front<<" and rear= "<<rear<<endl<<"traversing completed"<<endl;

getch();

return;

}

//main function

void main(){

int ch;

while(1){

clrscr();

cout<<"Circular Queue Operation:\n1.INSERTION\n2.DELETION\n3.TRAVERSING\n4.EXIT\nenter your choice"<<endl;

cin>>ch;

switch(ch){

case 1: cinsertion();break;

case 2: cdeletion();break;

case 3: ctraversing();break;

case 4: exit();

defaul: cout<<Wrong Choice"<<endl; 

getch();

}}}

File Name:- cqueue.c

#include<stdio.h>

#include<conio.h>

#define N 5

int cqueue[N],front=-1,rear=-1,item;

void cinsertion(){

if(((front==0)&&(rear==N-1))||(front==rear+1)){

printf("Overflow Condition\n");

getch();

return;

}

printf("Enter an Item to insert\n");

scanf("%d",&item);

if(rear==-1)

front=rear=0;

else{

if(rear==N-1){

rear=0;}

else{

rear++;

}

}

cqueue[rear]=item;

printf("%d is inserted\ninsertion completed\n",item);

getch();

return;

}

void cdeletion(){

if(front==-1){

printf("underflow Condition\n");

getch();

return;

}

item=cqueue[front];

if(front==rear){

front=rear=-1;

}

else

{if(front==N-1){

front=0;

}

else{

front++;

}

}

printf("%d is deleted\nDeletion completed\n",item);

getch();

return;

}

void ctraversing(){

int i;

if(front==-1){

printf("circular queue is Empty\n");

getch();

return;

}

printf("Circular Queue is:");

if(rear>=front){

for(i=front;i<=rear;i++){

printf("%d ",cqueue[i]);

}

}

else{

for(i=front;i<=N-1;i++){

printf("%d ",cqueue[i]);

}

for(i=0;i<=rear;i++){

printf("%d ",cqueue[i]);

}

}

printf("\nfront=%d and rear=%d\n",front,rear);

printf("Traversing completed");

getch();

return;

}

void main(){

int ch;

while(1){

clrscr();

printf("cqueue Operation:-\n1.INSERTION\n2.DELETION\n3.TRAVERSING\n4.EXIT\nEnter your choice\n");

scanf("%d",&ch);

switch(ch){

case 1: cinsertion();break;

case 2: cdeletion();break;

case 3: ctraversing();break;

case 4: exit();

default:

printf("Wrong Choice\n");

getch();

}}}