การดำเนินการคิวแบบวงกลม-การแทรกและการลบใน C++

คิวเป็นโครงสร้างข้อมูลนามธรรมที่มีชุดขององค์ประกอบ คิวใช้กลไก FIFO กล่าวคือองค์ประกอบที่แทรกก่อนจะถูกลบก่อนเช่นกัน

อ้อยในคิวเป็นโครงสร้างข้อมูลเชิงเส้นเดียว แต่อาจสร้างปัญหาได้หากเราใช้คิวโดยใช้อาร์เรย์ บางครั้งการใช้การแทรกและการลบแบบต่อเนื่องกัน ตำแหน่งด้านหน้าและด้านหลังจะเปลี่ยนไป ในขณะนั้นคิวจะดูเหมือนไม่มีที่ว่างให้แทรกองค์ประกอบเข้าไป แม้ว่าจะมีพื้นที่ว่างอยู่บ้าง แต่จะไม่ถูกใช้งานเนื่องจากปัญหาเชิงตรรกะบางอย่าง เพื่อแก้ปัญหานี้ เราจะใช้โครงสร้างข้อมูลคิวแบบวงกลม

คิววงกลมคือประเภทของคิวที่ตำแหน่งสุดท้ายเชื่อมต่อกับตำแหน่งแรกเพื่อสร้างวงกลม

อัลกอริทึม

insert(queue,key) −

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