【附C源码】循环队列的C语言实现队列作为基础数据结构之一在操作系统调度、消息传递、广度优先搜索等场景中均有广泛应用。本文将探讨一种基于循环数组的队列实现方案该方案在内存利用率和操作效率之间取得了较好的平衡。设计思路传统数组实现队列时若采用出队后前移所有元素的策略时间复杂度为O(n)O(n)O(n)显然无法满足性能要求。循环队列通过维护队头和队尾指针使入队和出队操作均可在O(1)O(1)O(1)时间内完成。本实现额外引入了两个设计点动态扩容机制当队列满时自动扩容避免固定容量带来的局限性数据顺序整理扩容时将数据按逻辑顺序重新排列简化后续操作数据结构定义typedefintData;typedefstruct{Data*data;// 数据存储区intfront;// 队头索引intrear;// 队尾索引intsize;// 当前元素个数intcapacity;// 队列容量}Queue;此处使用size字段记录元素个数而非通过front和rear的关系推断。这种设计消除了队满与队空的判断歧义同时使queueSize()等接口的实现更为直观。核心操作实现入队操作boolqueueEnqueue(Queue*q,Data val){if(!q)returnfalse;if(queueIsFull(q)){if(!queueGrow(q))returnfalse;}q-rear(q-rear1)%q-capacity;q-data[q-rear]val;q-size;returntrue;}入队时首先检查容量若已满则触发扩容。rear指针采用模运算实现循环移动。扩容机制staticboolqueueGrow(Queue*q){intnewCapacityq-capacity*2;Data*newData(Data*)malloc(sizeof(Data)*newCapacity);if(!newData)returnfalse;for(inti0;iq-size;i){newData[i]q-data[(q-fronti)%q-capacity];}free(q-data);q-datanewData;q-front0;q-rearq-size-1;q-capacitynewCapacity;returntrue;}扩容时将原有数据按逻辑顺序复制到新数组并重置front和rear指针。这一操作的时间复杂度为O(n)O(n)O(n)但由于扩容触发频率较低入队的均摊时间复杂度仍为O(1)O(1)O(1)。出队操作boolqueueDequeue(Queue*q){if(!q||queueIsEmpty(q))returnfalse;q-front(q-front1)%q-capacity;q-size--;returntrue;}出队仅移动front指针无需数据搬移。被出队元素所占空间将在后续入队时被覆盖或扩容时自动丢弃。辅助功能除基本操作外本实现还提供了若干实用接口queueContains()顺序查找指定元素queueCount()统计元素出现次数queuePrint()可视化输出队列状态便于调试查找类操作的时间复杂度为O(n)O(n)O(n)符合预期。测试验证main()函数中包含完整的测试用例覆盖以下场景基本入队/出队流程队头/队尾元素访问循环特性验证出队后入队自动扩容触发清空与复用运行结果示例C:\Users\anjuxi\Desktop\C语言 队列a.exe队列测试创建队列:[](size0,capacity8,front0,rear-1)入队元素10,20,30,40,50:[10,20,30,40,50](size5,capacity8,front0,rear4)队头元素:10队尾元素:50出队一次:[20,30,40,50](size4,capacity8,front1,rear4)再入队60,70:[20,30,40,50,60,70](size6,capacity8,front1,rear6)是否包含30: 是 是否包含100: 否 连续出队3次:[50,60,70](size3,capacity8,front4,rear6)入队多个元素测试扩容:[50,60,70,100,101,102,103,104,105,106,107,108](size12,capacity16,front0,rear11)清空队列:[](size0,capacity16,front0,rear-1)重新入队1,2,3:[1,2,3](size3,capacity16,front0,rear2)队列已销毁复杂度分析操作时间复杂度说明入队均摊O(1)O(1)O(1)扩容时为O(n)O(n)O(n)出队O(1)O(1)O(1)仅移动指针查看队头/队尾O(1)O(1)O(1)直接索引访问查找O(n)O(n)O(n)顺序遍历空间O(n)O(n)O(n)nnn为当前容量总结该实现通过循环数组解决了普通数组队列的效率问题同时以动态扩容机制弥补了固定容量的缺陷。代码中包含了完整的空指针检查和错误处理可作为工程实践的基础组件。完整代码已上传至仓库欢迎参考指正。⚠️源码地址https://github.com/anjuxi/C-queue/tree/main