循环队列（顺序循环队列） 核心原理 + 代码全解析

前言在学习队列时我们会发现普通顺序队列存在一个致命缺陷假溢出。数组明明还有空闲空间却提示队列已满导致内存利用率极低。为了解决这个问题循环队列应运而生。它把数组的头尾逻辑相连形成一个环形结构让空间可以重复利用。一、循环队列是什么循环队列 用数组实现的、逻辑上首尾相连的队列解决了顺序队列的 3 大痛点假溢出入队 / 出队时间复杂度保持 O (1)空间重复利用核心规则队头 front出队端队尾 rear入队端指针移动(pos 1) % MAX_SIZE牺牲一个格子用于区分空与满二、循环队列三大核心难点必懂你代码里写的注释非常经典这是循环队列最关键的 3 个考点① 入队、出队达到 O (1)入队在队尾出队在队头不移动元素只移动指针 →O(1)② 判空 判满冲突最经典为了不混淆空和满采用牺牲一个格子的方案判空front rear判满(rear 1) % MAX_SIZE front③ 计算有效长度通用公式length (rear - front MAX_SIZE) % MAX_SIZE无论 rear 在 front 前还是后都能正确计算长度。三、结构体设计简洁标准#pragma once #define MAX_SIZE 10 typedef int ELEM_TYPE; typedef struct CQueue { ELEM_TYPE* base; // 动态数组用来接收malloc的返回值 int front; // 队头指针 int rear; // 队尾指针 } CQueue;四、完整接口清单// 初始化 void Init_Circle_Queue(struct CQueue* pcq); // 入队 bool Push(struct CQueue* pcq, ELEM_TYPE val); // 出队 bool Pop(struct CQueue* pcq); // 获取队头 ELEM_TYPE Front(struct CQueue* pcq); // 查找 int Search(struct CQueue* pcq, ELEM_TYPE val); // 判空、判满 bool IsEmpty(struct CQueue* pcq); bool IsFull(struct CQueue* pcq); // 获取长度 int Get_Size(struct CQueue* pcq); // 清空、销毁、打印 void Clear(struct CQueue* pcq); void Destroy(struct CQueue* pcq); void Show(struct CQueue* pcq);五、核心函数逐行精讲1. 初始化void Init_Circle_Queue(struct CQueue* pcq) { pcq-base (ELEM_TYPE*)malloc(MAX_SIZE * sizeof(ELEM_TYPE)); pcq-front 0; pcq-rear 0; }申请空间队头队尾都指向 0表示空队列。2. 入队Pushbool Push(struct CQueue* pcq, ELEM_TYPE val) { if (IsFull(pcq)) return false; pcq-base[pcq-rear] val; pcq-rear (pcq-rear 1) % MAX_SIZE; return true; }先判满赋值队尾指针循环移动O (1) 高效3. 出队Popbool Pop(struct CQueue* pcq) { if (IsEmpty(pcq)) return false; pcq-front (pcq-front 1) % MAX_SIZE; return true; }只移动队头指针不删除数据高效、简洁O(1)4. 获取队头元素ELEM_TYPE Front(struct CQueue* pcq) { if (IsEmpty(pcq)) exit(1); return pcq-base[pcq-front]; }5. 查找int Search(struct CQueue* pcq, ELEM_TYPE val) { //0.安全性处理 for (int i pcq-front; i ! pcq-rear; i (i 1) % MAX_SIZE) { if (pcq-base[i] val) return i; } return -1; }6. 判空 判满最经典bool IsEmpty(struct CQueue* pcq) { return pcq-front pcq-rear; } bool IsFull(struct CQueue* pcq) { return (pcq-rear 1) % MAX_SIZE pcq-front; }7. 获取有效长度int Get_Size(struct CQueue* pcq) { return (pcq-rear - pcq-front MAX_SIZE) % MAX_SIZE; }8. 清空、销毁、打印void Clear(struct CQueue* pcq) { pcq-front pcq-rear; } void Destroy(struct CQueue* pcq) { assert(NULL ! pcq); free(pcq-base); pcq-base NULL; pcq-front pcq-rear 0; } void Show(struct CQueue* pcq) { for (int i pcq-front; i ! pcq-rear; i (i 1) % MAX_SIZE) { printf(%d , pcq-base[i]); } printf(\n); }六、测试主函数int main() { struct CQueue head; Init_Circle_Queue(head); Push(head, 1); Push(head, 2); Push(head, 3); Show(head); Pop(head); Push(head, 4); Show(head); Push(head, 5); Push(head, 6); Push(head, 7); Push(head, 8); Push(head, 9); Push(head, 10); Show(head); Push(head, 11); Show(head); Pop(head); Push(head, 111); Show(head); printf(队头元素值%d\n, Front(head)); return 0; }运行结果七、循环队列 VS 普通顺序队列特性普通顺序队列循环队列假溢出存在不存在空间利用率低极高判空判满易冲突完美解决入队出队O(1)O(1)工程使用极少极多八、高频 10 题必背循环队列解决了什么问题假溢出。循环队列为什么牺牲一个格子区分空队列和满队列。判空条件front rear判满条件(rear1)%MAX_SIZE front长度计算公式(rear-frontMAX_SIZE)%MAX_SIZE入队时间复杂度O(1)出队时间复杂度O(1)循环队列是物理循环吗不是是逻辑循环。front 指向什么队头元素下标。rear 指向什么下一个可入队的位置。