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()函数来显示队列中的元素。
本教程到此结束。我希望本教程能帮助你了解如何实现一个循环队列。