【数据结构】队列——循环队列（详解）_数据结构

0 循环队列

循环队列（circular queue）是队列的一种实现方式，它通过将队列存储空间的最后一个位置与第一个位置相连接，形成一个循环的队列结构，从而可以更加高效地利用存储空间。在循环队列中，当队尾指针到达队列存储空间的末尾时，下一个插入操作将从头开始，即实现了队列的“循环”。

1 特定条件下循环队列队/空队满判断条件

在循环队列中，判断队列是否为空或已满是一个重要的操作。由于循环队列的特性，我们不能简单地通过比较队头指针（front）和队尾指针（rear）是否相等来判断队列是否为空或已满，因为当队列为空时和当队列满时，这两个指针都可能相等。

1.1 队列为空的条件

队列为空的条件相对简单，即队头指针和队尾指针相等：

front == rear

1.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 来判断队列是否已满。