1. 先说结论C 循环队列到底解决什么问题很多人一开始接触循环队列是在学习数据结构教材的时候但真正让我觉得“这东西必须搞明白”的是在实际项目里写网络收发缓冲区的时候。C 循环队列本质上就是一个定长数组配合两个指针或者索引来模拟先进先出的逻辑存满了再从头部覆盖空间被循环复用所以叫“循环队列”。它解决的问题非常明确线性队列用数组实现时每出队一个元素如果只是移动头指针那么头部之前的内存就永远空着入队到数组末尾之后就彻底满了明明前面还有大把空间却再也塞不进新元素。这就是经典的“假溢出”。循环队列把数组首尾相连从头到尾循环利用空间从根上消灭这个问题。适合谁来读如果你正在写嵌入式程序、网络协议栈、生产者消费者模型或者你在准备面试想彻底搞懂数据结构底层实现这篇文章可以直接抄作业。我会从设计思路讲起给完整代码再把我实际踩过的坑和排查经验一并写出来。我尽量不讲废话每个点都落在能用的层面上。你用循环队列不是为了考试是为了写出更稳的代码。2. 循环队列的核心设计front、rear 与判空判满2.1 基本数据结构与指针含义先定义一个最精简的结构template typename T class CircularQueue { private: T* data; // 底层数组 int capacity; // 队列容量实际可存储元素个数 int front; // 队头下标 int rear; // 队尾下标 int count; // 当前元素个数 public: explicit CircularQueue(int cap); ~CircularQueue(); bool push(const T value); bool pop(); T frontValue() const; bool isEmpty() const; bool isFull() const; int size() const; };这里有几个容易混淆的概念需要先掰扯清楚。front 指向队头元素pop 时取 front 位置然后 front 向后移动。rear 有两种习惯定义一种是指向队尾元素另一种是指向队尾的下一个空位。我用的是后者因为判断入队位置时非常直观新元素直接写到 data[rear]然后 rear 后移。那么当 front 和 rear 指向同一个位置时到底是空还是满这里必须靠额外信息来区分不能只看指针相等这一个条件。我上面代码里用了 count 计数这是一种方案。但也有人不用 count纯靠指针关系判断那就需要牺牲一个存储单元或者加 flag。这三种策略各有适用场景后面我单独分析。说到循环这两个字底层数组本质上还是线性的一块连续内存所谓循环是在逻辑上把数组尾部和头部连起来。具体到代码上就是下标移动时不能简单加一而要取模front (front 1) % capacity; rear (rear 1) % capacity;这样当下标走到数组末端时会自然绕回数组开头。取模操作是循环队列的灵魂几乎所有下标操作都离不开它。唯一的性能注意点是取模在嵌入式平台上可能比较慢但大部分场景下这个开销完全可以忽略。2.2 判空判满的三种策略我直接给出三种常见做法并说明各自的取舍。第一种牺牲一个存储单元。这也是教材里最常见的写法。数组长度 capacity 中只使用 capacity - 1 个位置用于存元素留出一个空位。判空条件是 front rear判满条件是 (rear 1) % capacity front。比如数组长度是 5实际最多存 4 个元素。bool isEmpty() const { return front rear; } bool isFull() const { return (rear 1) % capacity front; }这种做法的优点是连 count 都不用维护任何时刻都能区分空和满。缺点是实际可用容量比申请的数组长度少 1如果只想存 N 个元素你得多申请一个单位。省了一个 int 变量多占了一个存储单元内存敏感场景要心里有数。第二种利用计数器 count。就是我上面代码里用的方案。push 成功时 countpop 成功时 count--判空判满直接看 count 0 或 count capacity。这个方案不浪费任何数组元素代码也很直观调试的时候 count 的值一眼就能看出来。我日常写业务代码最推荐这个因为它的表达最接近人类的直觉。bool isEmpty() const { return count 0; } bool isFull() const { return count capacity; }这个方案的隐藏风险是 count 和数据可能会不同步比如 push 时数组越界了或者 pop 越过了空队列的边界count 就会失真。所以写 push 和 pop 时一定要先校验状态再操作数据最后更新 count顺序不能乱。第三种加 flag 标志位。用一个布尔变量记录最近一次操作是入队还是出队。初始化时 flag false如果最后一次操作是 push 导致 front rear说明队列满如果是 pop 导致 front rear说明队列空。bool flag; // true: 最后一次操作是push, false: 最后一次操作是pop bool isEmpty() const { return (front rear) (!flag); } bool isFull() const { return (front rear) (flag); }这个方案不浪费空间也不需要 count但逻辑上比较绕而且入队和出队的操作顺序一旦写错flag 就跟实际状态反转了。说实话我见过不少把第三种方案写出 bug 的例子效率没比 count 高多少维护成本反而更高。如果你不是在做极致的嵌入式内存优化用 count 是最好的选择。2.3 size 计算的几种写法队列元素个数看似简单实际写起来非常容易算错。我介绍两种稳妥写法。第一种直接用 countint size() const { return count; }第二种当你不维护 count 时需要用公式int size() const { return (rear - front capacity) % capacity; }这个公式要把 front 正好在 rear 前面的情况单独想清楚。比如 capacity 5front 3rear 1实际元素是 rear 绕了一圈到 front 前面的所有位置(1 - 3 5) % 5 3队列里确实有 3 个元素。只看公式可能觉得抽象我们拆开说。非循环情况下元素个数是 rear - front。一旦 rear 小于 front说明 rear 已经绕过数组尾部回到了前面那就要加上 capacity 再取模。套用上面的数值就是 (1 - 3 5) % 5 3结果是 3。这个公式我记得特别牢因为写队列的 size 函数是我早期写过最多 bug 的地方不是忘了加 capacity就是忘了取模。如果用的是牺牲一个存储单元的方案size 还要改成 (rear - front capacity) % capacity但此时 front rear 代表空所以满的时候不可能出现 front rear公式依然成立。3. 手写一个 C 循环队列完整实现与测试3.1 类模板设计光看理论不行我给你一套可以直接编译运行的完整实现。我选择用类模板这样不仅能存 int存什么自定义类型都一样能跑。关键设计点有两个。第一用 count 而不是牺牲单元法这样队列容量就是申请的内存容量不浪费第二push 和 pop 都返回 bool让调用方可以感知队满和队空而不是直接越界崩溃。构造函数和析构函数如下template typename T CircularQueueT::CircularQueue(int cap) : capacity(cap), front(0), rear(0), count(0) { if (capacity 0) { throw std::invalid_argument(Capacity must be positive); } data new T[capacity]; } template typename T CircularQueueT::~CircularQueue() { delete[] data; }这里有一个非常容易被新手忽略的点capacity 的大小写。构造参数 cap 先赋值给 capacity然后所有判满逻辑都依赖这个 capacity。有的人习惯直接在参数里写成 capacity然后在成员初始化列表里又写一次 capacity(cap)结果构造函数参数和成员变量同名产生遮蔽shadowing问题。我在初始化的写法里故意把参数命名为 cap就是为了避开这个坑。3.2 核心函数实现入队操作 pushtemplate typename T bool CircularQueueT::push(const T value) { if (isFull()) { return false; } data[rear] value; rear (rear 1) % capacity; count; return true; }出队操作 poptemplate typename T bool CircularQueueT::pop() { if (isEmpty()) { return false; } front (front 1) % capacity; count--; return true; }读取队头元素template typename T T CircularQueueT::frontValue() const { if (isEmpty()) { throw std::runtime_error(Queue is empty); } return data[front]; }完整测试代码如下#include iostream #include stdexcept int main() { CircularQueueint q(5); for (int i 1; i 5; i) { std::cout push i : q.push(i) std::endl; } // 此时队列已满第六次会失败 std::cout push 6: q.push(6) std::endl; std::cout front: q.frontValue() std::endl; while (!q.isEmpty()) { std::cout q.frontValue() ; q.pop(); } std::cout std::endl; return 0; }为什么这段代码能验证“循环”这个核心行为因为容量是 5你连续 push 5 个元素front 在 0rear 绕回 0队列显示满。接着连续 pop 5 个front 绕回 0rear 也在 0队列显示空。你再 push 连续的 6、7、8、9、10底层数组下标始终在 0 到 4 之间循环这就是循环队列在实际运行中的效果。建议你把这个测试跑起来后自己在 push 和 pop 中间穿插调用 size()直观感受一下指针的绕圈过程。3.3 参数选择和内存管理的经验关于容量参数有几个实际经验分享给你。注意capacity 一定要大于 0否则 new T[capacity] 的行为是未定义的。我的代码里用抛异常来表达这个错误这是 C 里相对稳妥的处理方式。也可以用 std::vector 替代裸数组但循环队列这种定长结构用原生数组配合 delete[] 更直观而且不需要引入额外开销。还有一点如果 T 是含有动态内存的类型比如 std::string那么 push 和 pop 之间会涉及拷贝构造和析构。循环队列本身不负责管理元素内部的资源只负责元素的存放和位置移动这是它和对象池的本质区别。写代码前想清楚你这个队列里的元素是值语义还是指针语义决定了你的 T 应该填对象还是填指针。内存碎片的担忧也不容忽视。频繁 push/pop 会导致 T 的构造和析构不断发生如果你存的是大对象性能会明显下降。一个常用优化是提前在底层数组上预留足够空间或者直接存储指针如 std::unique_ptr让队列只搬运地址不搬运内容。这个优化思路在很多高性能队列里都有体现后面扩展部分我再细说。4. 经验总结与常见问题排查4.1 常见错误速查表我把自己和身边同事实际踩过的坑整理成了一个速查表按概率从高到低排列下标没有取模。这是出现频率最高的错误来源。很多人写着写着就忘了 (front 1) % capacity 这步直接 front队列一旦满过一轮就访问越界。判空判满条件写反。比如把牺牲单元法的判满条件 (rear 1) % capacity front 错写成 (rear 1) front导致满队列判断永远为 false入队数据覆盖了未读数据。这个问题非常隐蔽因为只有当 rear 正好走到容量的最后一个位置时才触发常规测试很难发现。count 更新位置错误。push 里先 count-- 后写数据pop 里先 count 后移动指针这两种失误都会让 count 和真实数据量不一致而且越用差距越大最后 API 全部失效。用 unsigned int 存 front 和 rear然后忘掉取模。unsigned 碰到负数时的行为会让你怀疑人生比如 (front - 1) % capacity 在 unsigned 下会得到什么你根本不想知道。我的建议是循环队列的下标一律用 int反正 capacity 一般不会超过 2^31没必要给自己添麻烦。析构函数忘了 delete[]。这个属于 C 基本功但确实有人在封装循环队列时只在测试代码里 delete封装类本身忘了清理导致内存泄漏。如果你用智能指针管理 data就不会有这个问题但裸数组配合 RAII 也别忽略析构。我再补充一个很多人会忽视的性能细节。你写循环队列的 push 和 pop 时每次都会调用 isFull 或 isEmpty 做状态判断这是必要的。但你千万不要为了省这几行判断把判满逻辑直接写进 push 内部然后用 assert 断言。release 模式下 assert 会被编译掉一旦队列满数据就会覆盖到尚未读取的位置这是逻辑 bug不是性能问题。4.2 多线程环境下的改造注意点循环队列天然适合做单生产者单消费者SPSC的无锁队列模型。为什么因为生产者和消费者各自只修改一个变量生产者改 rear消费者改 front。如果加上合理的同步机制就能避免多线程读写同一个变量引发的数据竞争。真正的难点不在队列本身而在内存序。如果你的代码不用任何原子操作直接两个线程同时读写 front那么即使逻辑上没问题C 的内存模型也会让结果变得不可预测。最粗浅的改造方法是用互斥锁把 push 和 pop 都包起来std::mutex mtx; bool threadSafePush(const T value) { std::lock_guardstd::mutex lock(mtx); return push(value); }这个方案在绝大多数业务场景下已经够了。如果你非要追求极致性能可以研究无锁循环队列分别用 std::atomic 存 front 和 rear再用 acquire/release 语义来保证读写顺序。但说实话无锁队列的正确性比起锁版本复杂得多我见过太多写上瘾却根本测不出来 bug 的案例。真要上无锁必须有完善的并发测试方案否则不如用锁。还有一点多线程环境中 count 这个变量会成为热点。你用互斥锁保护的时候push 里的 count 和 pop 里的 count-- 都在锁内执行没问题。但如果用无锁方案count 的更新必须也是原子的否则数据不一致。这也是有些人宁愿用牺牲单元法也要避免 count 的原因之一。5. 循环队列的工程应用与扩展思路5.1 实际场景为什么要用循环队列教材里讲循环队列通常是为了引出数据结构的“循环利用”思想。但在工程里循环队列几乎是所有 FIFO 缓冲区的默认实现方案。举几个真实场景。嵌入式串口接收缓冲。单片机接收串口数据时中断里把字节写入缓冲主循环中再从缓冲取出来处理。这个缓冲如果不是循环的你就得在取数据时把后续数据整体前移时间复杂度直接变成 O(n)。对于实时性要求高的场景这个数据搬移的开销不可接受。循环队列把入队出队都压到 O(1)常数时间完成非常适合中断上下文。网络收发缓冲区。TCP 数据到达和上层读取是异步的你不可能每次收完包就立刻把整块数据交给上层。用循环队列把未处理的数据攒起来是最直观的方案。我写过的一个简易 TCP 客户端里接收线程不断地往队列扔字节流解析线程从队列里按协议帧切包两者通过循环队列解耦谁也不阻塞谁。音频采样数据的暂存。音频流通常是持续的但消费方处理速度可能波动。用循环队列做缓冲生产者是音频采集回调消费者是播放回调队列大小决定了你能容忍的延迟上限。如果队列满了早期设计最直接的做法就是丢掉最旧的数据或者丢新数据具体丢哪头完全取决于你的业务逻辑。这个取舍在队列设计阶段就要想清楚。5.2 常见扩展思路如果你觉得上面的实现已经能干活了但想让它更强我这里给几个我自己实际用过且效果不错的扩展方向。第一支持动态扩容。定长队列有个缺点就是容量预估不准。你可以把底层数组的扩容做成隐式行为检测到满的时候重新分配一个新数组把元素全部拷贝过去更新 front、rear 和 capacity。拷贝过程中保持原有顺序。这个逻辑不复杂但要注意扩容时 front 到 rear 的搬运方向。比如 front 3rear 2扩容后你要按队列顺序复制而不是按下标顺序复制否则元素顺序就乱了。第二支持按索引访问。循环队列通常只能访问队头和队尾但有些场景需要跨步读取比如协议解析时想直接跳过几个字节读某个偏移。你可以提供 at(offset) 方法用 (front offset) % capacity 定位元素。注意检查 offset 必须小于当前 size。第三把底层存储换成 std::vector。如果你受不了手动 delete[]用 std::vector 替换裸数组完全可行push 时直接 data[rear] valuevector 会自动处理对象的构造。唯一要注意的是 vector 的 size 必须提前初始化到 capacity不然 operator[] 访问会越界。用法如下std::vectorT data; data.resize(capacity);这样做的好处是析构函数不用再写 delete[]同时还能利用 vector 的 RAII 特性防止内存泄漏。坏处是 vector 的内存是在堆上分配的与裸数组没有本质区别只是封装更安全。第四改造成对象池。如果你反复创建销毁对象性能开销大可以把循环队列改造成对象池初始化时一次性创建 capacity 个对象push 时返回一个空闲对象的指针pop 时回收这个对象。这种模式在游戏开发的服务端逻辑中非常常见我记得自己第一次写对象池就是从循环队列变过来的。第五支持 peek 多元素。如果你需要在不解队的情况下查看最近的 N 个元素比如滑动窗口统计可以加一个 peekKthFront(k) 方法。核心计算公式依然是(front k) % capacity。这个方法在流量统计和限流算法里非常实用。这些扩展思路不需要全部实现按实际需求取舍即可。我的原则是能用循环队列解决的事情就别引入环形链表能用数组就别引入复杂容器代码越简单越不容易出 bug。但真要面对多线程、高性能需求时也别拘泥于基础版本该加锁加锁该用原子用原子。最后分享一个我个人的小体会。循环队列这个数据结构看起来简单但几乎每一次我在项目里用它都能挖出一些意想不到的细节问题要么是容量边界算错要么是线程并发没考虑周全。正式因为它的实现太贴近底层反而需要你比写业务逻辑更认真。你把这篇文章里那些边界情况都验证过一遍后面写任何缓冲区代码都会顺手很多。