我要评论目录
0 循环队列
循环队列（circular queue）是队列的一种实现方式，它通过将队列存储空间的最后一个位置与第一个位置相连接，形成一个循环的队列结构，从而可以更加高效地利用存储空间。在循环队列中，当队尾指针到达队列存储空间的末尾时，下一个插入操作将从头开始，即实现了队列的“循环”。
1 特定条件下循环队列队/空队满判断条件
在循环队列中，判断队列是否为空或已满是一个重要的操作。由于循环队列的特性，我们不能简单地通过比较队头指针（front）和队尾指针（rear）是否相等来判断队列是否为空或已满，因为当队列为空时和当队列满时，这两个指针都可能相等。
1.1 队列为空的条件
队列为空的条件相对简单，即队头指针和队尾指针相等：
front == rear1.2 队列为满的条件
队列为满的条件需要特殊处理，因为当队列满时，队尾指针的下一个位置应该是队头指针。但是，我们不能直接比较 rear + 1 和 front 是否相等，因为 rear + 1 可能会超出数组索引的范围。因此，我们需要使用模运算 % 来确保索引在数组范围内循环。
有两种常见的实现方式：
①浪费一个空间：
在这种方法中，我们故意让队列中始终保持一个空闲位置，这样当 rear 的下一个位置是 front 时，队列就是满的。
(q.rear + 1) % max_size == q.front这种方法的好处是实现简单，缺点是浪费了一个空间。
②使用额外的变量：
我们可以使用一个额外的变量（例如 size 或 count）来跟踪队列中元素的数量。当 size 等于 max_size 时，队列就是满的。
size == max_size这种方法需要额外的空间来存储元素数量，但是空间利用率更高，没有浪费。
下面循环队列的实现将采用第一种方法。
2 循环队列的实现
循环队列通常使用一个固定大小的数组来实现，同时需要两个指针来指示队头和队尾的位置。为了区分队列是满还是空，我们可以使用以下几种方法之一：
- 设置一个标记变量：当队列为空时，该变量为某个特定值（如
false）；当队列满时，该变量为另一个特定值（如true）。 - 使用队尾指针的下一个位置：当队尾指针的下一个位置等于队头指针时，队列满；当队头指针等于队尾指针时，队列空（但需要注意区分队列空和队列满时队头队尾指针重合的情况）。
循环队列实现：
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define max_size 100
typedef struct {
int data[max_size];
int front; // 队头指针
int rear; // 队尾指针
} circularqueue;
// 初始化循环队列
void initqueue(circularqueue *q) {
q.front = q.rear = 0;
}
// 判断队列是否为空
bool isempty(circularqueue *q) {
if(q.front==q.rear)
return true;
else
return false;
}
// 判断队列是否已满
bool isfull(circularqueue *q) {
if((q.rear + 1) % max_size == q.front)
return false;
}
// 入队操作
bool enqueue(circularqueue *q, int x) {
if (isfull(q)) {
printf("queue is full\n");
return false;
}
q.data[q.rear] = x;
q.rear = (q.rear + 1) % max_size;
return true;
}
// 出队操作
bool dequeue(circularqueue *q, int &x) {
if (isempty(q)) {
printf("queue is empty\n");
return false;
}
x = q.data[q.front];
q.front = (q.front + 1) % max_size;
return true;
}
int main() {
circularqueue q;
initqueue(&q);
// 入队操作
enqueue(&q, 1);
enqueue(&q, 2);
enqueue(&q, 3);
// 出队操作
int x;
dequeue(&q, &x);
printf("dequeued: %d\n", x); // 输出 1
// ... 其他操作 ...
return 0;
}3 详解队空/队满的判定
例如：一个队列的入队顺序为 a，b，c，d，e ：
①空队；
②a，b，c入队；
③不舍弃条件下；
④牺牲一个单元条件下。
综上，在牺牲一个单元下，可以正确的判定该队列是队空还是队满。
4 注意事项
- 当队尾指针
rear到达数组的末尾时，需要将其回绕到数组的开头，这通常通过取模运算% max_size来实现。 - 类似地，当队头指针
front向前移动并到达数组的开头时，也需要将其回绕到数组的末尾（尽管在出队操作中不直接需要，但在某些情况下，如查找队中某个元素时可能会用到）。 - 在判断队列是否已满时，注意区分队列满和队列空时队头队尾指针重合的情况。在循环队列中，当队尾指针的下一个位置等于队头指针时，队列满。因此，我们使用
(q.rear + 1) % max_size == q.front来判断队列是否已满。
发表评论