介绍

Circular Queue是对线性队列的改进，它被引入来解决线性队列中的内存浪费问题。循环队列使用FIFO原则来插入和删除其中的元素。在本教程中，我们将讨论循环队列的操作以及如何管理它。

什么是循环队列？

循环队列是数据结构中的另一种队列，其前端和后端相互连接。它也被称为循环缓冲区。它的操作与线性队列类似，那么为什么我们需要在数据结构中引入一个新的队列呢？

使用线性队列时，当队列达到其最大限制时，尾指针之前可能会存在一些内存空间。这会导致内存损失，而良好的算法应该能够充分利用资源。

为了解决内存浪费的问题，开发人员引入了循环队列的概念，其具有循环链接到后端和前端的能力，并且可以插入更多元素。

循环队列的基本功能

• 后 − 它返回队列的后值。

• 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 = %dn", 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

结论

循环队列在内存管理和CPU调度中使用。它使用displayQueue()函数来显示队列元素。

我们已经到达了本教程的结尾。我希望这个教程能帮助你理解如何实现一个循环队列。