【数据结构指南】循环队列

前言：

情景展现：以"公交车厢"为示例，假设车厢内设有8个固定座位（对应普通队列的8个内存空间），其运作规则与队列完全一致。

①乘客只能从后门（队尾）上车。

②乘客必须从前门（队头）下车。

③乘客下车后，座位不会自动前移填补空位

请思考，为什么在车厢中会出现假溢出，以及如何解决假溢出问题？

一、队列假溢出

1.1 假溢出拆解：从日常场景看懂它的本质

为了回答前言中的思考题，我们逐步来拆解假溢出，一步步看 “假溢出” 是怎么发生的：

1.第一步：坐满车厢

        假设先上来 8 个人，分别坐在 1-8 号座位，此时 “队伍满了”（普通队列判断 “队满”），再有人想上车，系统会提示 “没位置了”，这是个很正常情况。

2.第二步：前排有人下车

        坐 1、2、3 号座位的人到站下车，此时 1-3 号座位空了，但因为规则限制，4-8 号座位的人不能往前挪（普通队列的队头指针只会往后移，不会 “回头” 用前面的空位置）

3.第三步：新乘客上车被拒

        这时候来了 2 个新乘客，想坐 1、2 号空座位，但系统一看 “队尾已经到 8 号了”（普通队列的队尾指针指向 8），还是提示 “没位置了”。明明有 2 个空座位，却没法用 —— 这就是普通队列的 “假溢出”，不是真的没空间，而是 “前面的空位置被浪费了”。

小结：正是因为普通队列中的 “队头指针” 和 “队尾指针” 只会单向移动，而队尾到了内存的 “末尾”，哪怕队头前面有大片空内存，也会被判定为 “队满”，这就是假溢出的本质。

1.2 假溢出的实际坑点：那些让我们卡壳的麻烦

麻烦 1：内存空间被 “隐形浪费”：

        普通队列的内存一般是 “一次性分配” 的，比如你给队列分配了能存 100 条数据的空间，想用来存用户的操作日志。

        但如果日志存满 100 条后，又删除了 50 条（队头前移 50 位），此时队列里实际只有 50 条数据，但因为假溢出，新的日志还是存不进来 —— 相当于 50% 的内存白分配了，只能频繁手动 “扩容”，既浪费资源，又会拖慢程序速度。

麻烦2：出现 “诡异 bug”，排查半天找不到原因

        当我们遇到 “存不进数据” 时，第一反应往往是 “我是不是把队列容量设小了？” “是不是判断队满的代码写错了？”。

        比如有个同学做 “消息队列” 功能，明明队列里只存了 30 条消息（容量 100），却死活存不进新消息，反复检查 “队满判断代码”，发现逻辑没问题，最后才意识到是假溢出 —— 这一来一回，可能半天时间就耗在上面了。

1.3 假溢出的空间浪费：用数据看明白浪费有多严重

        从表格能明显看出：普通队列的 “可用空间” 会随着 “出队次数” 减少，这样导致空间利用率极其低下。

二、循环队列

2.1 循环队列出现的起因

如何解决普通队列因为出队的操作，导致队列前部分的空间被浪费呢？

 -其实本质上是要解决队头指针和队尾指针只能单向移动，一旦队尾指针走到了尾部，哪怕前面通过出队腾出了大块的空间也无法进行入队操作。

 -基于这个痛点，我们通过设计循环队列就能很好的解决，即使队尾指针走到了尾部，因为循环队列逻辑结构上是环形的，所以队尾指针又会从起点开始，充分利用了前面出队腾出的大块空间，这也正是我们设计循环队列的原因。

2.2循环队列的设计

循环队列通过 “逻辑上让数组首尾相连”，直接破解 “假溢出” 问题：

1.入队时，若rear到达数组末尾，判断队头是否有空位，有空位则让rear绕回数组开头（而非直接判定满队）。      

          
2.出队时，front向后移动，当front到达数组末尾，同样绕回开头，继续利用空闲空间。

这种 “循环复用” 的设计，彻底解决了普通队列空间浪费的问题，这也是循环队列存在的核心价值。

如图所示：在逻辑结构上循环队列是环形的。

如图所示：在物理结构上循环队列是基于数组实现的，若rear到达数组末尾，进入下一个循环。

2.3循环队列实现的相关接口

2.4循环队列实现的相关文件

2.5CircularQueue.h

        CircularQueue.h头文件实现：通过结构体定义循环队列，声明循环队列的相关接口函数

#pragma once #include<stdbool.h> #include<stdlib.h> #include<stdio.h> #include<assert.h> typedef int CQDatatype; typedef struct CircularQueue { // 存储元素的数组 CQDatatype* data; //指向队头 int front; //指向队尾 int rear; //队列实际容量 int capacity; }CircularQueue; //初始化队列 void QueueInit(CircularQueue* cq,int capacity); //判断队列是否为空 bool isEmpty(CircularQueue* cq); //判断队列是否为满 bool isFull(CircularQueue* cq); //入队 bool enQueue(CircularQueue* cq, CQDatatype x); //出队 bool deQueue(CircularQueue* cq); //获取队头元素 CQDatatype getFront(CircularQueue* cq); //获取队尾元素 CQDatatype getBack(CircularQueue* cq); //销毁队列 void QueueDestroy(CircularQueue* cq); 

对于CircularQueue.h主要关注如下代码：

代码1：

typedef int CQDatatype; typedef struct CircularQueue { // 存储元素的数组 CQDatatype* data; //指向队头 int front; //指向队尾 int rear; //队列实际容量 int capacity; }CircularQueue; 

struct CircularQueue 创建循环队列的结构体

        

1.成员1为：CQDatatype* data  -存储元素的数组

        

2.成员2为：int front;  -指向队头（存储队头指向的下标）

        

3.成员3为：int rear;   -指向队尾（存储队尾指向的下标）
        

4.成员4为：int capacity;  -循环队列的容量

        

通过typedef int CQDatatype 方便以后进行修改存储在循环队列中的元素类型。

代码2：

//判断队列是否为空 bool isEmpty(CircularQueue* cq); //判断队列是否为满 bool isFull(CircularQueue* cq);

如何判断循环队列为空呢？

如图所示：当队列为空时，队头指针和队尾指针都指向同一个位置，所以用rear==head来判断。

如何判断队列为满呢？

如图所示：当队列为满时，此时队尾指针进入下一个循环，即重新回到下标为0处。此时我们发现队列为满的条件仍然是：rear==head。

这样就导致了一个问题当head（头节点指针）==rear（尾节点指针） 时，循环队列究竟是为满，还是为空呢，导致判断条件有了争议，逻辑出现了混乱。那么我们如何解决这个问题呢？

        

一般有两个思路：

        

思路一：定义一个计数器size，根据size是否为0或则size是否为队列的总容量来进行判断，这样就避免了这个问题。

        

思路二：浪费一个空间。

        

              此时当队列为空时：head==rear。

        

              此时当队列为满时：队尾指针的下一个位置是队头指针。

我们以思路二为例：演示一下循环队列为空时的判断条件，循环队列为满时的判断条件。

        

假设队列的总容量为k=6，实际我们多开辟一个空间使得队列的总容量为k+1=7。  

如图一所示：我们开辟k+1=7个空间，但循环队列可用空间为k=6，因为我们需要进行浪费一个空间，用于区别队满和队空的条件。

如图二所示：我们向循环队列中push6个元素分别为：1 2 3 4 5 6，此时循环队列为满，因为我们浪费了一个空间，实际可用空间为6，

                     队满的判断条件为：( rear + 1 ) % ( k + 1 )==head                                  

如图三所示：我们向循环队列中pop6个元素，此时队列为空.

                     队满的判断条件为：rear==head。

如图四所示：我们向循环队列中push6个元素分别为：1 2 3 4 5 6，此时循环队列为满，因为我们浪费了一个空间，实际可用空间为6。

                     队满的判断条件为：rear+1==head  <==>  ( rear + 1 ) % ( k + 1 )==head

综上所述： 通过多开辟一个空间的方式，能够区分队列为空的判定条件和队列为满的判定条件。        

         

队列为满时：（rear+1）%（k+1）== head       



队列为空时： rear==head

2.6CircularQueue.c

①循环队列的初始化

void QueueInit(CircularQueue* cq,int capacity) { assert(cq); //初始化大小为100的空间 cq->capacity = capacity; //预留一个空间 cq->data = (CQDatatype *)malloc(sizeof(CQDatatype) * (cq->capacity +1 ) ); if (cq->data == NULL) { perror("malloc fail"); return; } cq->front = cq->rear = 0; }

这里采用第二种方式：多开辟一个空间进行浪费的方式，规避队列和队满的判断条件相同。

②循环队列判断是否为空

//判断队列是否为空 bool isEmpty(CircularQueue* cq) { assert(cq); return cq->front == cq->rear; } 

队列为空时：队头指针和队尾指针指向同一个位置。

③判断队列是否为满

//判断队列是否为满 bool isFull(CircularQueue* cq) {     assert(cq);     return (cq->rear + 1) % (cq->capacity + 1)==cq->front ; }

队列为满时：队尾指针的下一个位置是队头指针     

④入队

//入队 bool enQueue(CircularQueue* cq, CQDatatype x) { assert(cq); if (isFull(cq)) { return false; } //进行入队操作 cq->data[cq->rear] = x; //更新队尾指针指向 cq->rear = (cq->rear + 1) % (cq->capacity + 1); return true; }

温馨提示：

                

①：因为rear指针指向的是队尾元素的下一个位置，所以cq->data[cq->rear]就可以正确找到要插入的元素的下标，

       如图所示：初始时rear指针和head指针都指向下标为0的位置，所以此时入队只需要cq->data[cq->rear] = x;



        

②：这里更新队尾指针指向的时候：cq->rear = (cq->rear + 1) % (cq->capacity + 1);

       因为是循环队列的原因，所以队尾指针更新需要进行取模运算，使得队尾指针在循环队列中进行循环，而不是进行单向向后。        

⑤出队

//出队 bool deQueue(CircularQueue* cq) { assert(cq); if (isEmpty(cq)) { return false; } //进行出队操作 cq->front = (cq->front + 1) % (cq->capacity + 1); return true; } 

温馨提示：

        

 这里更新队头指针指向的时候：cq->front = (cq->front + 1) % (cq->capacity + 1);

 因为是循环队列的原因，所以队头指针更新需要进行取模运算，使得队头指针在循环队列中进行循环，而不是进行单向向后。 

⑥获取队头元素

//获取队头元素 CQDatatype getFront(CircularQueue* cq) { assert(cq); //队列为空时触发 assert(!isEmpty(cq)); return cq->data[cq->front]; }

温馨提示：

        

因为队头指向的就是队头元素，所以直接通过索引就可以返回队头元素。

⑦获取队尾元素

//获取队尾元素 CQDatatype getBack(CircularQueue* cq) { assert(cq); assert(!isEmpty(cq)); return cq->rear==0? cq->data[cq->capacity] : cq->data[cq->rear-1] ; }

温馨提示：

        

①因为队尾指针，指向的是队尾元素的下一个位置，所以其索引cq->rear并不是队尾元素，其索引上一个下标位置cq->rear-1才是队尾元素。

        

        

②如图所示：对于一般情况而言cq->rear-1是队尾元素，

        

        

        

③如图所示：对于特殊情况，rear指向下标为0的位置时，此时队尾元素的下标不再是rear-1，队尾元素的下标为：rear->capacity，其中capacity为空间可用空间容量。

⑧销毁队列

//销毁队列 void QueueDestroy(CircularQueue* cq) { assert(cq); free(cq->data); cq->data = NULL; cq->capacity = cq->front = cq->rear = 0; }

2.7Test.c

#include"CircularQueue.h" #include<stdio.h> // 原基础测试 void TestBasic() { printf("=====基础功能测试=====\n"); CircularQueue q1 = { 0 }; QueueInit(&q1, 100); enQueue(&q1, 1); printf("入队1后，队头：%d，队尾：%d\n", getFront(&q1), getBack(&q1)); enQueue(&q1, 2); printf("入队2后，队头：%d，队尾：%d\n", getFront(&q1), getBack(&q1)); enQueue(&q1, 3); printf("入队3后，队头：%d，队尾：%d\n", getFront(&q1), getBack(&q1)); enQueue(&q1, 4); printf("入队4后，队头：%d，队尾：%d\n", getFront(&q1), getBack(&q1)); deQueue(&q1); printf("出队1次后，队头：%d，队尾：%d\n", getFront(&q1), getBack(&q1)); deQueue(&q1); printf("出队2次后，队头：%d，队尾：%d\n", getFront(&q1), getBack(&q1)); deQueue(&q1); printf("出队3次后，队头：%d，队尾：%d\n", getFront(&q1), getBack(&q1)); deQueue(&q1); printf("出队4次后，队列是否为空：%s\n\n", isEmpty(&q1) ? "是" : "否"); QueueDestroy(&q1); } // 测试队列满的情况 void TestFullQueue() { printf("=====队列满测试=====\n"); CircularQueue q; QueueInit(&q, 3); // 实际可存储3个元素（预留1个空间） printf("入队1：%s\n", enQueue(&q, 1) ? "成功" : "失败"); printf("入队2：%s\n", enQueue(&q, 2) ? "成功" : "失败"); printf("入队3：%s\n", enQueue(&q, 3) ? "成功" : "失败"); printf("队列是否已满：%s\n", isFull(&q) ? "是" : "否"); // 尝试入队第4个元素（应失败） printf("入队4：%s\n", enQueue(&q, 4) ? "成功" : "失败"); printf("当前队头：%d，队尾：%d\n\n", getFront(&q), getBack(&q)); QueueDestroy(&q); } // 混合入队出队测试 void TestMixedOperation() { printf("=====混合入队出队测试=====\n"); CircularQueue q; QueueInit(&q, 5); enQueue(&q, 10); enQueue(&q, 20); printf("入队10、20后，队头：%d，队尾：%d\n", getFront(&q), getBack(&q)); deQueue(&q); printf("出队1次后，队头：%d\n", getFront(&q)); enQueue(&q, 30); enQueue(&q, 40); printf("入队30、40后，队头：%d，队尾：%d\n", getFront(&q), getBack(&q)); deQueue(&q); deQueue(&q); printf("出队2次后，队头：%d，队尾：%d\n", getFront(&q), getBack(&q)); enQueue(&q, 50); enQueue(&q, 60); enQueue(&q, 70); printf("入队50、60、70后，队头：%d，队尾：%d\n", getFront(&q), getBack(&q)); printf("队列是否已满：%s\n\n", isFull(&q) ? "是" : "否"); QueueDestroy(&q); } // 空队列操作测试 void TestEmptyQueue() { printf("=====空队列操作测试=====\n"); CircularQueue q; QueueInit(&q, 2); printf("初始队列是否为空：%s\n", isEmpty(&q) ? "是" : "否"); printf("尝试出队（空队列）：%s\n", deQueue(&q) ? "成功" : "失败"); // 注意：以下两行会触发assert（空队列不能获取元素） // printf("尝试获取队头：%d\n", getFront(&q)); // printf("尝试获取队尾：%d\n", getBack(&q)); enQueue(&q, 100); printf("入队100后，是否为空：%s\n\n", isEmpty(&q) ? "是" : "否"); QueueDestroy(&q); } // 循环边界测试（队尾绕回起点） void TestCircularBoundary() { printf("=====循环边界测试=====\n"); CircularQueue q; QueueInit(&q, 2); // 实际可存2个元素 enQueue(&q, 100); enQueue(&q, 200); printf("入队100、200后，队头：%d，队尾：%d\n", getFront(&q), getBack(&q)); deQueue(&q); printf("出队1次后，队头：%d\n", getFront(&q)); enQueue(&q, 300); // 队尾会绕回数组起点 printf("入队300后，队头：%d，队尾：%d\n", getFront(&q), getBack(&q)); printf("队列是否已满：%s\n", isFull(&q) ? "是" : "否"); deQueue(&q); deQueue(&q); printf("出队2次后，是否为空：%s\n", isEmpty(&q) ? "是" : "否"); enQueue(&q, 400); printf("入队400后，队头：%d，队尾：%d\n\n", getFront(&q), getBack(&q)); QueueDestroy(&q); } int main() { TestBasic(); TestFullQueue(); TestMixedOperation(); TestEmptyQueue(); TestCircularBoundary(); return 0; }

三、实战演练

Leecode链接：循环队列

既然看到这里了，不妨点赞+收藏，感谢大家，若有问题请指正。