队列（queue）
队列是一种先进先出（FIFO，First In First Out） 的数据结构，类似于排队的场景。最先进入队列的元素最先被处理，而后加入的元素则排在队列的末尾。
常见的队列操作：
- 入队 (enqueue)：将元素加入队列尾部。
- 出队 (dequeue)：移除队列头部的元素。
环形队列 (Circular Queue)
环形队列是对普通队列的一种优化，它使用一个固定大小的数组来存储数据。当队列的尾部到达数组末尾时，它会“环绕”到数组的开头，从而高效地利用空间。这种设计特别适合用于空间有限的情况，比如内存受限的嵌入式系统或循环缓冲区。
环形队列具有以下特性：
- 队尾指针插入元素时，如果到达数组末尾，会回到数组的开头。
- 队头指针移除元素时，也会随着队列的移动进行循环。
通过这种方式，环形队列可以避免普通队列中可能存在的空间浪费问题。
演示环形队列的操作过程
下面将展示从空队列到满队列，以及出队和入队操作动态管理队列中的元素的状态变化。希望能狗帮助理解！
这里用数组演示，先介绍两个概念和数组初始化状态：
- front：指向队列的头部，即队列中第一个有效元素的位置。出队时将移除这个位置的元素，然后 front 移动到下一个有效元素的位置。
- rear：指向队列的尾部，即下一个可插入元素的位置。在插入新元素后，rear 将向后移动。
初始状态：
- 数组：[ _, _, _, _, _ ]，
- 数组当前容量：0
- front ：0
- rear ：0
环形队列的操作演示如下所示：
1. 入队元素 1
当前状态：
- 数组：[ 1, _, _, _, _ ]
- front = 0
- rear = 1（rear 移动到下一个位置）
2. 入队元素 2
当前状态：
- 数组：[ 1, 2, _, _, _ ]
- front = 0
- rear = 2（rear 移动到下一个位置）
3. 入队元素 3
当前状态：
- 数组：[ 1, 2, 3, _, _ ]
- front = 0
- rear = 3（rear 移动到下一个位置）
4. 出队元素 1
当前状态：
- 数组：[ _, 2, 3, _, _ ]（ front 之前指向位置上的 1 已被移除）
- front = 1（出队后，front 会移动到下一个有效元素的位置（2），此时数组中的 2 为队列的第一个有效元素的位置）
- rear = 3
5. 入队元素 4
当前状态：
- 数组：[ _, 2, 3, 4, _ ]
- front = 1
- rear = 4（rear 移动到下一个位置）
6. 入队元素 5
当前状态：
- 数组：[ _, 2, 3, 4, 5 ]
- front = 1
- rear = 0（rear 环绕到数组的开头，此时队列已满）
7. 入队元素 6（此时队列已满，入队失败）
当前状态：
- 数组：[ _, 2, 3, 4, 5 ]
- front = 1
- rear = 0
根据队列满的判断条件，此时队列已满，无法入队。
注意：也许你会发现，此时数组中索引 0 的位置空缺（在第4步已被出队），但实际上不能再插入新元素，因为队列已满。这是因为，在环形队列的实现中，队列会始终存在一个空缺位置，这是为了区分队列是满还是空的状态。这就是为什么即使队列看起来还有一个空位置，实际上它已经被视为满了。如果不保留一个空缺位置，当 front = rear 时，无法区分是队列空还是队列满
在环形队列中，当队列满时，rear 和 front 的位置关系非常特殊。此时，rear 指向下一个可插入位置，而这个位置正好是 front 的当前位置。因此，队列满的判断条件是：
(rear + 1) % capacity == front具体例子：假设队列容量为 5，当前状态为：
- 数组：[ 6, 2, 3, 4, 5 ]
- front = 1（指向元素 2）
- rear = 0（下一次插入应该在数组开头的 6 的位置）
判断队列是否满：
计算条件： (rear + 1) % capacity == front
得：rear + 1 = 0 + 1 = 1
(1 % 5) == 1，条件成立，说明队列已满。
题目要求
实现一个环形队列（Circular Queue）。该队列需要支持如下基本操作：
- 入队 (enqueue): 向队列的末尾插入元素。
- 出队 (dequeue): 从队列的头部移除元素。
- 获取队头元素 (front): 返回队列头部的元素。
- 获取队尾元素 (rear): 返回队列尾部的元素。
- 检查队列是否为空 (isEmpty): 判断队列是否为空。
- 检查队列是否已满 (isFull): 判断队列是否已满。
环形队列是一种利用数组实现的队列。与普通队列不同的是，环形队列的末尾与头部相连，使得当队列满时，队列可以循环使用。队列中有两个指针，分别指向头部和尾部，以方便入队和出队操作。
做题思路
环形队列的核心在于其“环形”特性。要实现这一特性，需要对数组的下标进行循环处理。使用两个指针 front 和 rear 来标记队列的头部和尾部，同时注意如何处理这些指针的更新逻辑。
- 入队操作：在尾部插入元素时，rear 指针应该向前移动，并在数组末尾时绕回到头部。需要注意队列已满的情况。
- 出队操作：在头部移除元素时，front 指针也应该向前移动，并同样处理绕回到头部的情况。
- 判断队列满和空的条件：环形队列已满的条件是 (rear + 1) % capacity == front，而空的条件是 front == rear。
过程解析
- 初始化：分配一个固定大小的数组，用于存储队列中的元素。初始化 front 和 rear ，并提供队列的容量。
- 入队操作：在队尾插入新元素，并更新 rear 指针。
- 出队操作：移除队头元素，并更新 front 指针。
- 辅助操作：实现队列满、队列空、返回队头元素和队尾元素的操作。
运用到的知识点
- 数组操作：环形队列本质上是基于数组的实现，了解如何使用数组的下标进行操作是关键。
- 模运算：使用模运算 (
%) 来实现队列的“环形”效果，保证队列头尾指针可以循环使用数组的空间。 - 队列操作：理解队列的基本操作，包括入队、出队、判断空满等，是数据结构中的基础知识。
- 环形结构理解。
- 边界条件处理。
示例代码
C 实现：
#include <stdio.h> // 引入标准输入输出库，用于打印输出
#include <stdbool.h> // 引入布尔类型库，用于表示真/假
#define MAX_SIZE 5 // 定义队列的最大容量为5
// 定义循环队列的结构体
typedef struct {
int data[MAX_SIZE]; // 队列数组，用于存储队列元素
int front; // 队头指针，指向队列的第一个元素
int rear; // 队尾指针，指向队列的下一个插入位置（非当前最后一个元素）
} CircularQueue;
// 初始化队列，设置队头和队尾指针为0
void initQueue(CircularQueue* queue) {
queue->front = 0;
queue->rear = 0;
}
// 判断队列是否为空，当队头和队尾指针相等时为空
bool isEmpty(CircularQueue* queue) {
return queue->front == queue->rear;
}
// 判断队列是否已满，根据循环队列的特性，当队尾指针的下一个位置是队头指针时，队列已满
bool isFull(CircularQueue* queue) {
return (queue->rear + 1) % MAX_SIZE == queue->front;
}
// 入队操作，将元素插入队列尾部
bool enqueue(CircularQueue* queue, int value) {
if (isFull(queue)) { // 如果队列已满，打印提示信息并返回false
printf("队列已满，无法入队。\n");
return false;
}
queue->data[queue->rear] = value; // 在队尾插入元素
queue->rear = (queue->rear + 1) % MAX_SIZE; // 更新队尾指针，实现循环
return true;
}
// 出队操作，从队列头部移除元素
bool dequeue(CircularQueue* queue, int* value) {
if (isEmpty(queue)) { // 如果队列为空，打印提示信息并返回false
printf("队列为空，无法出队。\n");
return false;
}
*value = queue->data[queue->front]; // 取出队头元素
queue->front = (queue->front + 1) % MAX_SIZE; // 更新队头指针，实现循环
return true;
}
// 获取队头元素，如果队列为空，打印提示信息并返回-1
int front(CircularQueue* queue) {
if (isEmpty(queue)) {
printf("队列为空，无法获取队头元素。\n");
return -1; // 返回一个无效值
}
return queue->data[queue->front];
}
// 获取队尾元素，注意队尾指针指向的是下一个插入位置，因此需要回退一个位置
int rear(CircularQueue* queue) {
if (isEmpty(queue)) {
printf("队列为空，无法获取队尾元素。\n");
return -1; // 返回一个无效值
}
// 计算实际队尾元素的索引位置
int rearIndex = (queue->rear - 1 + MAX_SIZE) % MAX_SIZE;
return queue->data[rearIndex];
}
// 测试代码
int main()
{
CircularQueue queue; // 声明一个循环队列变量
initQueue(&queue); // 初始化队列
enqueue(&queue, 10); // 入队操作，插入元素10
enqueue(&queue, 20); // 入队操作，插入元素20
enqueue(&queue, 30); // 入队操作，插入元素30
enqueue(&queue, 40); // 入队操作，插入元素40
printf("队头元素: %d\n", front(&queue)); // 打印队头元素
printf("队尾元素: %d\n", rear(&queue)); // 打印队尾元素
int value;
dequeue(&queue, &value); // 出队操作，移除队头元素，并打印出队元素
printf("出队元素: %d\n", value);
enqueue(&queue, 50); // 入队操作，插入元素50
printf("队头元素: %d\n", front(&queue)); // 再次打印队头元素
printf("队尾元素: %d\n", rear(&queue)); // 再次打印队尾元素
return 0;
}C++ 实现：
#include <iostream> // 引入输入输出流库，用于输入输出操作
using namespace std; // 使用std命名空间，避免每次调用标准库时都需要加std::前缀
#define MAX_SIZE 5 // 定义队列的最大容量为5
// 定义循环队列类
class CircularQueue {
private:
int data[MAX_SIZE]; // 队列数组，用于存储队列中的元素
int front; // 队头指针，指向队列的第一个元素
int rear; // 队尾指针，指向队列中下一个将要插入元素的位置（非当前最后一个元素）
public:
// 构造函数，初始化队列的队头和队尾指针
CircularQueue() {
front = 0;
rear = 0;
}
// 判断队列是否为空
bool isEmpty() {
return front == rear; // 当队头和队尾指针相等时，队列为空
}
// 判断队列是否已满
bool isFull() {
return (rear + 1) % MAX_SIZE == front; // 根据循环队列的特性，当队尾指针的下一个位置是队头指针时，队列已满
}
// 入队操作，将元素插入队列尾部
bool enqueue(int value) {
if (isFull()) { // 如果队列已满，打印提示信息并返回false
cout << "队列已满，无法入队。" << endl;
return false;
}
data[rear] = value; // 在队尾插入元素
rear = (rear + 1) % MAX_SIZE; // 更新队尾指针，实现循环
return true; // 入队成功返回true
}
// 出队操作，从队列头部移除元素
bool dequeue(int &value) {
if (isEmpty()) { // 如果队列为空，打印提示信息并返回false
cout << "队列为空，无法出队。" << endl;
return false;
}
value = data[front]; // 取出队头元素
front = (front + 1) % MAX_SIZE; // 更新队头指针，实现循环
return true; // 出队成功返回true
}
// 获取队头元素
int getFront() {
if (isEmpty()) { // 如果队列为空，打印提示信息并返回一个无效值
cout << "队列为空，无法获取队头元素。" << endl;
return -1; // 返回一个无效值
}
return data[front]; // 返回队头元素
}
// 获取队尾元素
int getRear() {
if (isEmpty()) { // 如果队列为空，打印提示信息并返回一个无效值
cout << "队列为空，无法获取队尾元素。" << endl;
return -1; // 返回一个无效值
}
int rearIndex = (rear - 1 + MAX_SIZE) % MAX_SIZE; // 计算实际队尾元素的索引位置
return data[rearIndex]; // 返回队尾元素
}
};
// 测试代码
int main()
{
CircularQueue queue; // 声明一个循环队列对象
queue.enqueue(10); // 入队操作，插入元素10
queue.enqueue(20); // 入队操作，插入元素20
queue.enqueue(30); // 入队操作，插入元素30
queue.enqueue(40); // 入队操作，插入元素40
cout << "队头元素: " << queue.getFront() << endl; // 打印队头元素
cout << "队尾元素: " << queue.getRear() << endl; // 打印队尾元素
int value;
queue.dequeue(value); // 出队操作，移除队头元素，并将出队元素的值赋给value
cout << "出队元素: " << value << endl; // 打印出队元素的值
queue.enqueue(50); // 入队操作，插入元素50
cout << "队头元素: " << queue.getFront() << endl; // 再次打印队头元素
cout << "队尾元素: " << queue.getRear() << endl; // 再次打印队尾元素
return 0; // 程序正常结束
}
![[自动化测试：Selenium]：环境部署和Webdriver的使用](https://i-blog.csdnimg.cn/direct/773bc8aa8d9d4adf890e544ca62554c6.png)
