Hàng đợi vòng tròn-Thao tác chèn và xóa trong C ++

Hàng đợi là một cấu trúc dữ liệu trừu tượng chứa một tập hợp các phần tử. Hàng đợi thực hiện cơ chế FIFO tức là phần tử được chèn vào trước cũng sẽ bị xóa trước.

Queue là một cấu trúc dữ liệu tuyến tính. Nhưng nó có thể tạo ra một số vấn đề nếu chúng ta triển khai hàng đợi bằng cách sử dụng mảng. Đôi khi bằng cách sử dụng một số thao tác chèn và xóa liên tiếp, vị trí phía trước và phía sau sẽ thay đổi. Trong thời điểm đó, nó sẽ giống như hàng đợi không có khoảng trống để chèn các phần tử vào nó. Ngay cả khi có một số không gian trống, nó sẽ không được sử dụng do một số vấn đề logic. Để khắc phục sự cố này, chúng tôi sẽ sử dụng cấu trúc dữ liệu hàng đợi vòng tròn.

Hàng đợi hình tròn là một loại hàng đợi trong đó vị trí cuối cùng được kết nối với vị trí đầu tiên để tạo thành một vòng tròn.

Thuật toán

chèn (hàng đợi, khóa) -

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

xóa (hàng đợi) -

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

Ví dụ

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

Đầu ra

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