一、 为什么需要循环队列从“假溢出”说起1.1 普通顺序队列的困境回顾一下普通的顺序队列基于数组我们使用两个指针front指向队头rear指向队尾的下一个位置。入队元素放入rear指向的位置rear后移。出队取出front指向的元素front后移。随着操作的进行front和rear都会不断向后移动。即使前面的元素已经出队腾出了空间但由于rear已经到达数组末尾我们无法再利用前面的空闲空间。这种现象被称为**“假溢出”**False Overflow​ 初始状态: [_, _, _, _] front0, rear0 入队A,B,C: [A, B, C, _] front0, rear3 出队A,B: [_, _, C, _] front2, rear3 此时若想入队D虽然索引0和1是空的但rear已到末尾普通队列会报错“满”这就是假溢出。 ​1.2 循环队列的解决方案循环队列的核心思想是当rear或front到达数组末尾时如果数组头部有空闲空间就绕回到数组开头。这在逻辑上将数组变成了一个环。在物理内存上它依然是一段连续的空间但在逻辑操作上我们通过**取模运算%**来实现“循环”。二、 核心原理与关键难点2.1 索引的回绕公式假设数组大小为MAX_SIZE入队后更新 rearrear (rear 1) % MAX_SIZE出队后更新 frontfront (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来保存当前的容量#includeassert.h #includestdio.h #includestdlib.h #includestring.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即可 }四、终章碎语——循环往复指针轻移队列有界思维无疆代码虽止思维未歇。循环队列最迷人之处在于它打破了线性的束缚让终点成为了新的起点。正如古诗所云“沉舟侧畔千帆过病树前头万木春” 哪怕旧的索引被覆盖新的数据依然会源源不断地涌入生生不息。愿你在未来的编程之路上既有破局而出的锐气也有周而复始的韧性。无论遇到多少Bug与瓶颈都能像这循环队列一般兜兜转转终见开阔天地