एक कतार एक सार डेटा संरचना है जिसमें तत्वों का संग्रह होता है। Queue FIFO तंत्र को लागू करता है अर्थात जो तत्व पहले डाला जाता है उसे भी पहले हटा दिया जाता है।
कतार गन्ना एक रैखिक डेटा संरचना हो सकती है। लेकिन अगर हम सरणी का उपयोग करके कतार को लागू करते हैं तो यह कुछ समस्या पैदा कर सकता है। कभी-कभी कुछ लगातार डालने और हटाने के ऑपरेशन का उपयोग करके, आगे और पीछे की स्थिति बदल जाएगी। उस समय, ऐसा लगेगा कि कतार में तत्वों को सम्मिलित करने के लिए कोई स्थान नहीं है। यहां तक कि अगर कुछ खाली स्थान हैं, तो कुछ तार्किक समस्याओं के कारण उनका उपयोग नहीं किया जाएगा। इस समस्या को दूर करने के लिए, हम वृत्ताकार कतार डेटा संरचना का उपयोग करेंगे।
वृत्ताकार कतार एक प्रकार की कतार होती है जिसमें वृत्त बनाने के लिए अंतिम स्थिति पहली स्थिति से जुड़ी होती है।
एल्गोरिदम
सम्मिलित करें (कतार, कुंजी) -
begin if front = 0 and rear = n – 1, or front = rear + 1, then queue is full, and return otherwise if front = -1, then front = 0 and rear = 0 else if rear = n – 1, then, rear = 0, else rear := rear + 1 queue[rear] = key end
हटाएं (कतार) -
begin if front = -1 then queue is empty, and return otherwise item := queue[front] if front = rear, then front and rear will be -1 else if front = n – 1, then front := 0 else front := front + 1 end
उदाहरण
#include <iostream>
using namespace std;
int cqueue[5];
int front = -1, rear = -1, n=5;
void insertCQ(int val) {
if ((front == 0 && rear == n-1) || (front == rear+1)) {
cout<<"Queue Overflow \n";
return;
}
if (front == -1) {
front = 0;
rear = 0;
}
else {
if (rear == n - 1)
rear = 0;
else
rear = rear + 1;
}
cqueue[rear] = val ;
}
void deleteCQ() {
if (front == -1) {
cout<<"Queue Underflow\n";
return ;
}
cout<<"Element deleted from queue is : "<<cqueue[front]<<endl;
if (front == rear) {
front = -1;
rear = -1;
}
else {
if (front == n - 1)
front = 0;
else
front = front + 1;
}
}
void displayCQ() {
int f = front, r = rear;
if (front == -1) {
cout<<"Queue is empty"<<endl;
return;
}
cout<<"Queue elements are :\n";
if (f <= r) {
while (f <= r){
cout<<cqueue[f]<<" ";
f++;
}
}
else {
while (f <= n - 1) {
cout<<cqueue[f]<<" ";
f++;
}
f = 0;
while (f <= r) {
cout<<cqueue[f]<<" ";
f++;
}
}
cout<<endl;
}
int main() {
int ch, val;
cout<<"1)Insert\n";
cout<<"2)Delete\n";
cout<<"3)Display\n";
cout<<"4)Exit\n";
do {
cout<<"Enter choice : "<<endl;
cin>>ch;
switch(ch) {
case 1:
cout<<"Input for insertion: "<<endl;
cin>>val;
insertCQ(val);
break;
case 2:
deleteCQ();
break;
case 3:
displayCQ();
break;
case 4:
cout<<"Exit\n";
break;
default: cout<<"Incorrect!\n";
}
} while(ch != 4);
return 0;
} आउटपुट
1)Insert 2)Delete 3)Display 4)Exit Enter choice : 1 Input for insertion: 10 Enter choice : 1 Input for insertion: 20 Enter choice : 1 Input for insertion: 30 Enter choice : 1 Input for insertion: 40 Enter choice : 1 Input for insertion: 50 Enter choice : 3 Queue elements are : 10 20 30 40 50 Enter choice : 2 Element deleted from queue is : 10 Enter choice : 2 Element deleted from queue is : 20 Enter choice : 3 Queue elements are : 30 40 50 Enter choice : 4 Exit