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()函数来显示队列中的元素。

本教程到此结束。我希望本教程能帮助你了解如何实现一个循环队列。

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程