队列这个东西背概念容易真正实现起来才见功夫。我见过不少同学在纸上能把“先进先出”写得清清楚楚真到用数组写代码的时候却总是绕不明白那两个指针该什么时候动、动的顺序有没有讲究。这次就把“C/C数据结构之用数组实现队列”这件事从头到尾拆开讲透从为什么用数组、环形队列怎么设计、代码怎么一步步写出来到常见的坑和排查技巧一篇讲完。这篇文章适合刚学数据结构的学生也适合准备技术面试的开发者就算你之前完全没写过队列跟着走一遍手里的C和C就都能跑出一个像模像样的队列。1. 整体设计与思路拆解1.1 队列的本质与工作场景队列是一种线性表但它的操作被限制在两端只允许在队尾插入元素只允许在队首删除元素。这个约束直接带来一个特性——先进先出也就是FIFOFirst In First Out。我们日常排队买早餐就是这个逻辑先到的人先买到后来的人站到队伍末尾。计算机里到处都是这种场景比如操作系统的任务调度、消息中间件的消息堆积、网络数据包的缓冲、打印任务的排队底层数据结构全是队列。为什么非要限制操作位置因为很多业务逻辑天然就是“先来先处理”如果允许随机插入和删除规则就乱了。所以队列的本质不是存储数据而是用结构约束数据流动的顺序。1.2 为什么偏偏选数组实现队列有两大流派数组和链表。这里重点讲数组不是因为它简单而是因为数组在不少场景下比链表更合适。数组的好处首先是内存连续。连续内存意味着更少的碎片、更好的CPU缓存命中率以及下标访问的O(1)能力。虽然队列不需要随机访问但内存连续性对频繁读写队首队尾的场景非常有价值。其次数组不需要为每个元素额外分配节点指针内存开销更小。链表每个节点都要存一个next指针数据量一大这笔开销就很可观了。还有一个容易被忽略的点数组实现可以做到非常“稳定”。链表频繁malloc和free会产生内存碎片也可能因为分配失败而中断服务数组在初始化时一次性分配好空间之后的操作不涉及动态内存运行期表现非常可预测。这也是为什么很多嵌入式系统、实时系统里更倾向用数组实现的队列。当然数组实现也有明显短板——容量固定扩容麻烦这个后面专门讲。1.3 数组实现的头号敌人假溢出普通数组实现队列最经典的问题是“假溢出”。假设开一个容量5的数组入队4个元素后队尾指针rear指向4接着出队3个元素队首指针front指向3。此时数组前3个位置已经空出来了但rear已经顶到数组边界再入队走投无路直接报“队列已满”。这就是假溢出数组明明有空位却因为队尾走到尽头而无法使用。很多初学的人在这里卡住误以为队列真的满了。解决思路有两个方向一是每次出队把所有元素集体前移确保队尾永远不顶到头二是干脆把数组逻辑上“首尾相接”制作环形队列。第一种方向实现简单但每次出队都要搬动所有剩余元素出队操作退化为O(n)完全违背了队列O(1)操作的设计初衷。所以正规军基本都走环形路线。环形队列不是数据结构本身变了而是取模运算让“越过数组末尾”这个动作变成了“回到数组开头”数组的物理结构没有变但逻辑上首尾相连了。这个思想是数组实现队列的真正分水岭理解了它后面的代码就顺理成章了。2. 核心细节解析与实操要点2.1 三个关键变量容量、队首、队尾数组队列的核心变量其实就三个capacity数组容量也就是最多能装多少元素。front队首下标指向队列第一个元素。rear队尾下标指向下一个要插入的空位。很多人会把rear理解成“最后一个元素的位置”这个偏差会导致一系列边界问题。我建议从一开始就统一rear永远指向“下一个可用空位”。初始时队列为空front为0rear也为0两者相等插入第一个元素放在下标0的位置然后rear变成1。这样约定的好处是入队时“先放元素后移rear”出队时“先取元素后移front”操作语义非常干净。如果用“rear指向最后一个元素”的定义判断空和满的条件会变得极其别扭后续所有取模运算都要跟着-1再1特别容易出错。还有一个细节front和rear用什么类型。容量不大的时候int就行但如果队列可能超过INT_MAX就要考虑size_t或者long long。实际工程里更建议用size_t一方面语义上“下标”天然是非负的另一方面和数组下标类型保持一致。唯一要注意的是size_t做减法容易踩坑比如 front - rear 可能出现无符号下溢后面排查章节会专门讲。2.2 判空判满的三种主流策略环形队列绕不开一个哲学问题空和满的时候front和rear都相等怎么区分三种主流策略各有取舍。策略一牺牲一个存储单元。队列最多允许放 capacity - 1 个元素留一个空位做“哨兵”。判满条件变成 (rear 1) % capacity front判空条件保持 front rear。这个策略判断简单不用额外变量是教科书上最经典的做法。缺点是数组明明capacity大小却只能装capacity - 1个元素白费一个槽位。策略二引入计数器count。每次入队count加1出队count减1。判空看count 0判满看count capacity。这个方案所有空间都能用判断也非常直观。代价是需要一个额外的变量并且每次操作都要同步维护它。好处是还能顺手用count做遍历次数计算非常方便。策略三引入标志位flag。入队操作后把flag置为1出队操作后置为0判满条件是 front rear flag 1判空条件是 front rear flag 0。原理是区分“上一次操作是入队还是出队”。这个方案存在一个隐患连续多次入队导致满之后如果又把队首元素出队再入队flag的维护需要特别小心状态容易混乱实际用得少。我个人更推荐在初学阶段用策略一因为它能强迫你理解模运算和指针移动的本质工程阶段用策略二因为容量利用率高代码可读性好。以下表格方便对比策略判空条件判满条件最大元素数额外开销适用场景牺牲一格front rear(rear 1) % capacity frontcapacity - 1无教学、基础实现计数器count 0count capacitycapacity1个变量工程通用标志位front rear flag 0front rear flag 1capacity1个变量特殊场景2.3 取模运算这个灵魂细节环形队列的一切都建立在取模运算上。入队时 rear (rear 1) % capacity出队时 front (front 1) % capacity遍历时下标 (front i) % capacity。我见过很多人写代码漏掉取模结果数组越界程序直接崩。取模的本质是“绕圈”容量是5时下标的合法范围是0到4rear从4再往后就该回到0(4 1) % 5 就等于 0。还有一个隐藏坑C语言的 % 运算是“余数运算”结果符号与被除数一致。如果 front 或 rear 不小心被折腾成负数比如 -1 % 5在C里结果是 -1 而不是 4访问 arr[-1] 就是越界。所以务必保证 front 和 rear 永远非负。常见做法是把指针移动写成统一顺序先加1再取模不要写 (rear % capacity) 1 这种形式后者在rear恰好等于capacity - 1时会越界。3. 实操过程与核心环节实现3.1 结构体设计与初始化先用C语言写一个基于“计数器”方案的数组队列。为什么不用牺牲一格的方案做最终代码因为完整代码直接面向实用计数器的语义更直白容量也能全部用上。两种方案的判断逻辑在前面表格里已经列了代码里我会写清楚怎么切换。#include stdio.h #include stdlib.h #include stdbool.h typedef struct { int *data; // 动态数组存放元素 int capacity; // 数组容量 int front; // 队首下标指向第一个元素 int rear; // 队尾下标指向下一个插入位置 int count; // 当前元素个数 } ArrayQueue;初始化函数负责分配内存并把所有指针归位ArrayQueue *queue_init(int capacity) { if (capacity 0) { return NULL; } ArrayQueue *q (ArrayQueue *)malloc(sizeof(ArrayQueue)); if (q NULL) { return NULL; } q-data (int *)malloc(sizeof(int) * capacity); if (q-data NULL) { free(q); return NULL; } q-capacity capacity; q-front 0; q-rear 0; q-count 0; return q; }初始化里最容易犯的错就是只分配了结构体忘了给内部的数组data分配内存后面一写数据就段错误。还有一点malloc之后一定要检查返回值尤其在容灾要求高的场景分配失败返回NULL是要被上层处理的直接往下跑就是在埋雷。3.2 入队操作的完整实现入队前要先判满满了就不能再放。计数器方案的判满条件是 count capacity。判满之后就不能再放了可以返回 false 或者打印错误。bool enqueue(ArrayQueue *q, int value) { if (q NULL || q-count q-capacity) { return false; } q-data[q-rear] value; q-rear (q-rear 1) % q-capacity; q-count; return true; }入队的顺序非常重要先写入元素再移动rear指针最后更新count。如果先移动rear再写入就会把元素写到错误的位置。还要注意rear移动必须用取模否则第一个元素写到末尾后再来一个数组直接越界。比如capacity为5数据依次放进下标0、1、2、3、4后rear变成(4 1) % 5 0后面的元素从头开始循环存放。这里再强调一次“rear指向下一个插入位置”的约定。队里有5个元素、rear指向某个空位时新元素永远落在rear当前指向的位置这个位置一定是空位不会覆盖已有元素因为满的条件已经提前拦截了。3.3 出队操作与遍历打印出队要判空空的队列什么都不给。先取队首元素再移动front指针最后count减一。bool dequeue(ArrayQueue *q, int *out) { if (q NULL || q-count 0) { return false; } *out q-data[q-front]; q-front (q-front 1) % q-capacity; q-count--; return true; }出队的核心是先保存返回值再移动指针。很多人图省事先移动front再取值结果取到的是第二个元素第一个元素白白丢了。严格来说如果不care被删除的那个值的去处先移动也无所谓但标准接口至少要让人拿到被删元素所以顺序必须固定取值、移指针、改count。遍历打印是调试时最常用到的功能。因为数组是循环的不能直接for从front扫到rear得借助count控制次数void queue_print(const ArrayQueue *q) { if (q NULL) { return; } printf(queue: [); for (int i 0; i q-count; i) { int idx (q-front i) % q-capacity; printf(%d, q-data[idx]); if (i ! q-count - 1) { printf(, ); } } printf(]\n); }打印时从front出发按“前进i步再取模”的方式算下标。现实中我见过最惨的调试事故就是有人直接 printf(%d, q-data[i]) 从头扫到尾把环形结构当成线性数组打印输出完全对不上。遍历思路一定要从“绝对下标”切换成“相对偏移”这是环形队列的核心思维。销毁队列时别忘了释放两层内存先释放data再释放结构体本身。void queue_destroy(ArrayQueue *q) { if (q NULL) { return; } free(q-data); free(q); }3.4 C模板化写法C语言的实现直接用int类型只能存整数C里可以写一个模板类让队列支持任意类型。核心逻辑和C版本一致但是用类和模板封装起来使用体验会好很多。#include iostream #include vector template typename T class ArrayQueue { private: std::vectorT data; int capacity; int front; int rear; int count; public: explicit ArrayQueue(int cap) : capacity(cap), front(0), rear(0), count(0) { data.resize(capacity); } bool enqueue(const T value) { if (count capacity) { return false; } data[rear] value; rear (rear 1) % capacity; count; return true; } bool dequeue(T out) { if (count 0) { return false; } out data[front]; front (front 1) % capacity; --count; return true; } int size() const { return count; } bool empty() const { return count 0; } bool full() const { return count capacity; } };C版本用vector代替裸指针会自动管理内存写起来轻松不少。有人会问vector扩容后迭代器可能失效但这里我们从不使用迭代器只通过下标操作所以完全安全。模板化后你可以实例化成ArrayQueue 、ArrayQueue std::string 一套代码到处用。当然模板的代价是编译时体积变大但对学习项目来说完全不是问题。4. 常见问题与排查技巧实录4.1 容量与总数纠缠不清很多人把capacity和count混在一起。capacity是数组最多能存多少元素count是当前存了多少元素两者完全不同。用牺牲一格方案时容量为5的数组最多只能装4个元素这个4很容易让人犯迷糊。我的经验是多定义一个宏或者常量来记录“最大可用元素数”比如 MAX_ITEMS CAPACITY - 1然后所有判满逻辑都用 MAX_ITEMS减少心算成本。还有一个经典问题出队操作之后front前进此时front可能大于rear。如果你下意识用 front rear 判断队列是否还有元素就会误判为空。比如front变成3、rear变成1按线性思维这很反常但在环形队列里完全正常因为rear已经“绕”到前面去了。判断空和满的唯一标准就是前面表格里的公式不要凭直觉。4.2 遍历顺序踩过的坑遍历环形队列时有人从rear开始倒着打印以为能还原“入队顺序”结果发现顺序是反的。队列的遍历顺序应该是从front开始按入队先后顺序依次访问。因为入队的顺序是rear向前移动最早入队的元素在front最晚的在rear前面的位置。实际调试中我经常用一个“容量5、最多装5个元素”的计数器方案队列做测试入队1、2、3、4、5打印结果是1、2、3、4、5出队一个后打印结果是2、3、4、5。如果打印结果第一个元素不是2而是5说明遍历时取模方向算错了。还有一点取模运算的优先级要特别注意(front i) % capacity 这组括号如果漏掉写成 front i % capacity那只有i会参与取模下标直接越界这种错误编译器不会报错运行时才会炸。4.3 动态扩容时的元素搬运固定数组容量是天生短板但你完全可以给队列加入动态扩容能力。扩容的核心不是简单地把数组变大而是处理环形结构导致的“逻辑顺序”和“物理顺序”不一致的问题。假设容量5的队列里有3个元素front为2元素物理上存放在下标2、3、4逻辑顺序也是元素A(2)、B(3)、C(4)。扩容到10后不能直接把旧数组数据拷贝到新数组就完事因为新队列的front规定为0rear按照count来定位。正确做法是申请新数组按逻辑顺序遍历旧队列依次把元素放到新数组的头、中、尾最后把front置0rear置count。bool queue_resize(ArrayQueue *q, int new_capacity) { if (q NULL || new_capacity q-count) { return false; } int *new_data (int *)malloc(sizeof(int) * new_capacity); if (new_data NULL) { return false; } for (int i 0; i q-count; i) { int idx (q-front i) % q-capacity; new_data[i] q-data[idx]; } free(q-data); q-data new_data; q-capacity new_capacity; q-front 0; q-rear q-count; return true; }扩容倍数一般选择1.5倍或者2倍。扩容太大浪费内存扩容太小频繁触发搬迁。如果旧队列几乎满的扩容会带来整体O(n)的搬运成本但这个成本摊到每一次入队上是可接受的类似vector的摊还分析。实际项目中队列容量往往是启动配置里指定的不太频繁扩容遇到消息洪峰时扩容能力则是救命的。4.4 速查表写出健壮队列的十条经验症状可能原因对策入队后打印为空rear移动但count没加检查count维护是否在同一操作内完成出队总是取到同一个值front没有被取模移动出队函数里front (front 1) % capacity打印顺序逆序从rear往前遍历从front开始用相对偏移遍历数组越界但编译通过取模运算漏括号确保 (front i) % capacity 的括号存在队列满还继续入队判满公式写错检查是否用了(capacity-1)方案却忘了留位count变成负数出队时多减、重复出队出队前强制判空并打印count跟踪前端显示已满实际是空front和rear混乱打印front和rear的当前值手工模拟几步动态扩容后数据乱序直接memcpy旧数组按逻辑顺序遍历重建新数组内存泄漏只free结构体没free数据先free data再free q5. 从固定数组到工程可用还得再往前走一步5.1 环形缓冲区的价值边界数组队列本质上就是循环缓冲区ring buffer这个概念在工程界应用非常广泛。Linux内核的环形缓冲区、消息队列的存储层、日志系统的高速写入、音频数据的采样缓冲都是类似的结构。它最大的特点是无锁读写的潜力在单生产者单消费者模式下只要写入方只修改rear和count读取方只修改front和count配合内存屏障就能做到无锁并发这是链表队列很难做到的。当然它不是万能的。多生产者多消费者场景下多个线程同时修改count就会出现竞争需要加锁或者使用原子操作。容量动态扩容时也不能有并发操作否则整个缓冲区的状态会瞬间混乱。所以工业级的队列往往会区分“无锁环形缓冲区”和“带锁的大队列”两套方案前者处理高频小数据量后者处理低频大数据量。5.2 关于数组队列我最后想说的回过头看数组实现队列这个题目看起来小但它里面藏了不少算法设计的核心思想用约束换效率、用模运算换连续性、用指针移动换空间复用。我前前后后写过很多版本的队列每次重写都有新理解。如果你是初学建议把三种判满策略都亲手写一遍再用容量为3的小数组手工推演十几次入队出队把front、rear、count每一步的变化画在纸上。这一步做扎实了后面什么环形数组、滑动窗口、生产者消费者模型都会轻松很多。最后分享一个调试小技巧写队列测试的时候刻意把容量设成3或者5这种小数字入队出队时必须打印“当前front、rear、count”三个值。很多坑不是逻辑多复杂而是指针状态看不见、摸不着一旦把状态暴露出来问题基本一眼就能定位。这个习惯我保持到现在换个新环境写数据结构第一件事就是把状态调试打印捋清楚能省下一大半排查时间。
