C++ 如何实现一个循环队列

C++ 如何实现一个循环队列

循环队列是一种改进的队列数据结构，通过将队列的首尾相连，有效解决了线性队列中可能出现的内存浪费问题。本文将详细介绍循环队列的基本概念、操作方法，并通过一个完整的C++代码示例，展示如何实现循环队列的入队和出队操作。

什么是循环队列

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

对于线性队列，当队列达到最大极限时，有可能在后点之前出现一些内存空间。这导致了内存的浪费，而一个好的算法是能最大限度地利用资源的算法。

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

循环队列的基本功能

• Rear- 它返回队列的后端值。

• Front – 它返回队列的前端值。

• deQueue – 这个内置方法用于从队列中删除元素，同时检查它是否为空。

• enQueue – 这个方法用于向队列插入新的元素，同时检查其大小。

在一个循环队列中，元素在后端被添加，而从前端删除元素。deQueue和enQueue是与队列大小无关的函数，使用modulo运算符来实现。它们的时间复杂度是O(1)。

管理一个循环队列

我们通过使用enQueue和deQueue操作来管理一个循环队列。最初，一个循环队列的前部值为0，后部值为-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

结论

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