C++의 순환 대기열 데이터 구조

큐는 요소 모음을 포함하는 추상 데이터 구조입니다. 큐는 FIFO 메커니즘을 구현합니다. 즉, 먼저 삽입된 요소도 먼저 삭제됩니다.

큐는 하나의 선형 데이터 구조일 수 있습니다. 하지만 배열을 사용하여 큐를 구현하면 문제가 발생할 수 있습니다. 때때로 일부 연속 삽입 및 삭제 작업을 사용하여 전면 및 후면 위치가 변경됩니다. 그 순간에는 대기열에 요소를 삽입할 공간이 없는 것처럼 보일 것입니다. 여유 공간이 있더라도 일부 논리적 문제로 인해 사용되지 않습니다. 이 문제를 극복하기 위해 순환 큐 데이터 구조를 사용합니다.

원형 대기열은 마지막 위치와 첫 번째 위치를 연결하여 원을 만드는 대기열 유형입니다.

예시

#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