如何在C++中管理完整的循環佇列事件？-C++-PHP中文網

如何在C++中管理完整的循環佇列事件？

WBOY

發布： 2023-09-04 18:41:03

轉載

1156 人瀏覽過

介紹

Circular Queue是對線性佇列的改進，它被引入來解決線性佇列中的記憶體浪費問題。循環佇列使用FIFO原則來插入和刪除其中的元素。在本教程中，我們將討論循環隊列的操作以及如何管理它。

什麼是循環隊列？

循環佇列是資料結構中的另一個佇列，其前端和後端相互連接。它也被稱為循環緩衝區。它的操作與線性隊列類似，那麼為什麼我們需要在資料結構中引入一個新的隊列呢？

使用線性佇列時，當佇列達到其最大限制時，尾指標之前可能會存在一些記憶體空間。這會導致記憶體損失，而良好的演算法應該能夠充分利用資源。

為了解決記憶體浪費的問題，開發人員引入了循環隊列的概念，其具有循環連結到後端和前端的能力，並且可以插入更多元素。

如何在C++中管理完整的循環佇列事件？

循環佇列的基本功能

後 − 它傳回佇列的後值。
Front − 它傳回佇列的前端值。
deQueue − 這個內建方法用來從佇列中移除元素，同時檢查佇列是否為空。
enQueue − 此方法用於在檢查佇列大小時插入新元素。

在循環佇列中，元素從後端添加，從前端移除。 deQueue和enQueue是與佇列大小無關的函數，並使用取模運算子進行實作。它們的時間複雜度為O(1)。

管理循環隊列

我們透過使用enQueue和deQueue操作來管理循環隊列。最初，循環隊列的front值為0，rear值為-1，循環隊列中的所有元素為NULL。

範例

C 程式碼，使用陣列實作循環隊列

#include <bits/stdc++.h>
using namespace std;
 
class Queue {
   //Initializing front and rear of the queue
   int rear, front;
   int sz;
   int* arr;
 
   public:
   Queue(int s) {
      front = rear = -1;
      sz = s;
      arr = new int[s];
   }
   
   void enQueue(int v);
   int deQueue();
   void displayQueue();
};
 
//Circular queue function
void Queue::enQueue(int v) {
   if ((front == 0 && rear == sz - 1)
      || (rear == (front - 1) % (sz - 1))) {
         printf("\nNo Space Queue is Full");
         return;
      }
   
      //Inserting the front element
      else if (front == -1) {
         front = rear = 0;
         arr[rear] = v;
      }
   
      else if (rear == sz - 1 && front != 0) {
         rear = 0;
         arr[rear] = v;
      }
   
      else {
         rear++;
         arr[rear] = v;
      }
}
 
//Function for deleting queue elements
int Queue::deQueue() {
   if (front == -1) {
      printf("\nQueue needs data it is empty");
      return INT_MIN;
   }
   
   int ele = arr[front];
   arr[front] = -1;
   if (front == rear) {
      front = -1;
      rear = -1;
   }
   else if (front == sz - 1)
      front = 0;
   else
      front++;
   return ele;
}
 
//Printing Circular queue elements
void Queue::displayQueue() {
   if (front == -1) {
      printf("\nQueue Empty");
      return;
   }
   printf("\nCircular Queue elements are: \n");
   if (rear >= front) {
      for (int i = front; i <= rear; i++)
      printf("%d ", arr[i]);
   } else {
      for (int i = front; i < sz; i++)
      printf("%d ", arr[i]);
   
      for (int i = 0; i <= rear; i++)
      printf("%d ", arr[i]);
   }
}
 
int main() {
   Queue q(5);
   //Pushing data in circular queue
   q.enQueue(10);
   q.enQueue(20);
   q.enQueue(3);
   q.enQueue(5);
   //Printing circular queue elements
   q.displayQueue();
   
   //Deleting front elements of circular queue
   printf("\nDeleted element = %d\n", q.deQueue());
   printf("\nDeleted element = %d", q.deQueue());
   q.displayQueue();
   q.enQueue(13);
   q.enQueue(27);
   q.enQueue(50);
   q.displayQueue();
   q.enQueue(22);
   
   return 0;
}

登入後複製

輸出

Circular Queue elements are: 
10 20 3 5 
Deleted element = 10

Deleted element = 20
Circular Queue elements are: 
3 5 
Circular Queue elements are: 
3 5 13 27 50 
No Space Queue is Full

登入後複製