“袖里乾坤大，壶中日月长”：循环队列的空间复用之道

2026/8/5 11:59:27

一、为什么需要循环队列？从“假溢出”说起

1.1 普通顺序队列的困境

回顾一下普通的顺序队列（基于数组）：

我们使用两个指针：front指向队头，rear指向队尾的下一个位置。

入队：元素放入rear指向的位置，rear后移。

出队：取出front指向的元素，front后移。

随着操作的进行，front和rear都会不断向后移动。即使前面的元素已经出队，腾出了空间，但由于rear已经到达数组末尾，我们无法再利用前面的空闲空间。这种现象被称为**“假溢出”**（False Overflow）

 初始状态: [_, _, _, _] front=0, rear=0 入队A,B,C: [A, B, C, _] front=0, rear=3 出队A,B: [_, _, C, _] front=2, rear=3 此时若想入队D，虽然索引0和1是空的，但rear已到末尾，普通队列会报错“满”，这就是假溢出。

1.2 循环队列的解决方案

循环队列的核心思想是：当rear或front到达数组末尾时，如果数组头部有空闲空间，就绕回到数组开头。

这在逻辑上将数组变成了一个环。在物理内存上，它依然是一段连续的空间，但在逻辑操作上，我们通过**取模运算（%）**来实现“循环”。

二、核心原理与关键难点

2.1 索引的回绕公式

假设数组大小为MAX_SIZE：

入队后更新 rear：rear = (rear + 1) % MAX_SIZE

出队后更新 front：front = (front + 1) % MAX_SIZE

取模运算保证了索引永远在[0, MAX_SIZE - 1]范围内。

2.2 最大的痛点：如何判断“队空”与“队满”？

在循环队列中，front == rear既可能表示队列为空，也可能表示队列已满。这是初学者最容易混淆的地方。

方案	描述	优点	缺点
少用一个存储单元	规定`(rear + 1) % MAX_SIZE == front`时为满	逻辑简单，无需额外变量	浪费一个数组空间
增加 size 变量	维护一个`count`记录当前元素个数	直观，空间利用率 100%	每次增删都要维护 count

本文采用业界最通用的“少用一个存储单元”方案，因为它在面试和工程实践中最为常见，且能很好地体现模运算的特性。

队空条件：front == rear

队满条件：(rear + 1) % MAX_SIZE == front

注意：这意味着长度为N的数组，循环队列最多只能存N-1个元素。

2.3 数据结构结构体定义

包括必要的头文件，宏定义初始的循环队列的容量，和每次扩容的倍数

队列结构体中，保存空间的地址(ElemType* base)用来管理堆区空间

定义两个整形变量front、rear用来管理队列的头尾下标

最后还有一个变量queuesize，来保存当前的容量

#include<assert.h> #include<stdio.h> #include<stdlib.h> #include<string.h> typedef char ElemType; #define STACKINITSIZE 5 //初始容量 #define STACKINCREMENT 2 //每次扩容的倍数 typedef struct CycleSeqQueue { ElemType* base; //管理堆区内存 int front; //队头下标 int rear; //队尾下标 size_t queuesize; //当前容量 }CycleSeqQueue, * PCycleSeqQueue;

三、核心函数的实现

初始化
判空
判满
获取队中元素个数
扩容
入队
打印
出队并获取队头元素
获取队头元素
获取队尾元素
清空
销毁

3.1 初始化、判空、判满、获取队中元素个数

void InitCycleSeqQueue(PCycleSeqQueue pq)； //初始化

bool IsEmpty(const PCycleSeqQueue pq)； //判空

bool IsFull(const PCycleSeqQueue pq)； //判满

int GetSize(const PCycleSeqQueue pq)； //获取队中元素个数

初始化：在堆区申请循环队列的空间，然后初始化结构体中的变量即可

判空：若队头尾下标一致（pq->front == pq->rear），则循环队列为空

判满：若队尾指针加一取余后与队头下标一致（(pq->rear + 1) % pq->queuesize == pq->front），则循环队列为满

获取队中元素个数：无需循环遍历，可以计算队头尾下标得到

若pq->rear > pq->front：元素个数 = 队尾下标 - 队头下标

若pq->rear < pq->front：元素个数 = （队尾下标 - 队头下标 + 当前容量）% 当前容量

//1.初始化 void InitCycleSeqQueue(PCycleSeqQueue pq) { assert(pq != NULL); ElemType* p = (ElemType*)malloc(sizeof(ElemType) * STACKINITSIZE); //申请空间 if (p == NULL)return; //判空操作 pq->base = p; pq->front = pq->rear = 0; //初始化时，置0队头尾下标 pq->queuesize = STACKINITSIZE; //初始化队列容量 } //2.判空 bool IsEmpty(const PCycleSeqQueue pq) { assert(pq != NULL); return pq->front == pq->rear; //相同则为空 } //3.判满 bool IsFull(const PCycleSeqQueue pq) { assert(pq != NULL); return (pq->rear + 1) % pq->queuesize == pq->front; //相同则为满 } //4.获取队中元素个数 int GetSize(const PCycleSeqQueue pq) { assert(pq != NULL); return (pq->rear - pq->front + pq->queuesize) % pq->queuesize; //计算获得 }

3.2 扩容、入队

bool IncMem(PCycleSeqQueue pq)； //扩容

bool Push(PCycleSeqQueue pq, ElemType val)； //入队

扩容：若是队列满了，仍要插入新数据，则就要扩容队列；扩容的话，就要用realloc扩容函数，realloc扩容时，若后续有足够的空间则直接申请使用；没有的话，则重新寻找一片满足大小的空间，并将原数据拷贝到新空间中，返回新空间的地址；这里读者可以思考一下，扩容后可以直接使用，进行数据入队吗？是否需要对队头，队尾进行修改呢？

若是队尾下标大于队头下标，则直接在扩容后的队尾进行数据的入队即可（队头至队尾连贯）；

但若是，队尾下标小于队头下标，则就要将队尾下标处及前面一段，使用memmove函数将其连接到队头下标后面一段，这是因为扩容后，可以使队头至队尾连贯，所以要对队头尾下标的大小进行判断

入队：先进行判满操作，满了就进行扩容；没满就进行数据入队，(pq->base[pq->rear++] = val)

然后重置队尾下标pq->rear %= pq->queuesize。

//1.扩容 bool IncMem(PCycleSeqQueue pq) { assert(pq != NULL); int newqueuesize = pq->queuesize * STACKINCREMENT; ElemType* p = (ElemType*)realloc(pq->base, sizeof(ElemType) * newqueuesize); if (p == NULL)return false; //扩容是否成功的判断 if (pq->rear < pq->front) { //队尾下标 < 队头下标 memmove(pq->base + pq->queuesize, pq->base, sizeof(ElemType) * pq->rear); //扩容的那片空空间 最前面的元素地址 队尾下标处不放元素 pq->rear = (pq->rear + pq->queuesize) % newqueuesize; //重置队尾下标 } pq->queuesize = newqueuesize; //重置队列当前的容量 return true; } //2.入队 bool Push(PCycleSeqQueue pq, ElemType val) { assert(pq != NULL); if (IsFull(pq)) { //判满 if (IncMem(pq) == false) { //对扩容操作是否成功的判断 return false; } } pq->base[pq->rear++] = val; //入队数据，后置++，先解引用赋值，后自增 pq->rear %= pq->queuesize; //重置队尾下标 return true; }

3.3 打印、出队并获取队头元素

void PrintfCSQueue(const PCycleSeqQueue pq)； //打印

bool Pop(const PCycleSeqQueue pq, ElemType* pval) ； //出队并获取队头元素

打印：我们循环遍历队列，从队头开始打印输出，已知队头下标（pq->front），在循环中定义一个中间变量i（初始值为pq->front），第一个要输出的元素就是（pq->base[ i ]），注意：在循环中 i 并不是单纯的自增，因为这是循环队列 i 的值自然不能超过队列的最大容量，i 的重置应该是自增后对容量取余的结果，而循环终止条件就是 i 的值等于了队尾下标的值（pq->rear），就这样依次输出即可。

出队并获取队头元素：通过解引用传入的元素地址来获取队头元素（*pval = pq->base[pq->front++]），然后将队头下标重置即可（自增后对容量取余pq->front %= pq->queuesize）

//1.打印 void PrintfCSQueue(const PCycleSeqQueue pq) { assert(pq != NULL); if (IsEmpty(pq))return; //判空 for (int i = pq->front; i != pq->rear; i = (i + 1) % pq->queuesize) { //从队头开始 不能等于队尾下标 自增后对容量取余：重置i printf("%hhd ", pq->base[i]); //输出数据 } printf("\n"); } //2.出队并获取队头元素 bool Pop(const PCycleSeqQueue pq, ElemType* pval) { //传入元素类型地址用于接收队头元素 assert(pq != NULL); if (IsEmpty(pq))return false; //判空 *pval = pq->base[pq->front++]; //后置加加:先解应用取出队头元素后，队头下标再自增 pq->front %= pq->queuesize; //重置队头下标：让队头下标对容量取余 return true; }

函数测试：

3.4 获取队头元素、获取队尾元素

bool GetFront(PCycleSeqQueue pq, ElemType* pval)； //获取队头元素

bool GetRear(PCycleSeqQueue pq, ElemType* pval)； //获取队尾元素

获取队头元素：直接解引用传入的元素地址接收队头元素即可（*pval = pq->base[pq->front]）

获取队尾元素：注意队尾下标处是没有元素的，因为为了便于进行判满操作，我们浪费了一个元素的空间，所以解应用传入的元素地址所接收的是队尾下标减一，再重置后的下标元素值（*pval = pq->base[(pq->rear - 1 + pq->queuesize) % pq->queuesize]）

//1.获取队头元素 bool GetFront(PCycleSeqQueue pq, ElemType* pval) { assert(pq != NULL); if (IsEmpty(pq))return false; //判空 *pval = pq->base[pq->front]; //直接解引用即可 return true; } //2.获取队尾元素 bool GetRear(PCycleSeqQueue pq, ElemType* pval) { assert(pq != NULL); if (IsEmpty(pq))return false; //判空 *pval = pq->base[(pq->rear - 1 + pq->queuesize) % pq->queuesize]; // 队尾下标减一 防止为负 取余重置 return true; }

函数测试：

3.5 清空、销毁

void ClearQueue(PCycleSeqQueue pq)； //清空

void DestroyQueue(PCycleSeqQueue pq)； //销毁

清空：对于顺序队列的清空，只需将队尾下标的值让其等于队头下标值即可（pq->rear = pq->front）

销毁：我们顺序队列中（pq->base）保存了这片空间的地址，销毁时将其释放即可，然后将队尾下标、队头下标、当前容量均置为0即可

//1.清空 void ClearQueue(PCycleSeqQueue pq) { assert(pq != NULL); if (IsEmpty(pq))return; //为空则无需清空 pq->rear = pq->front; //队头尾下标相等即为空 } //2.销毁 void DestroyQueue(PCycleSeqQueue pq) { assert(pq != NULL); free(pq->base); //释放并置空空间 pq->base = NULL; pq->front = pq->rear = pq->queuesize = 0; //三者均置为0即可 }