循环队列是那种看起来很简单、写起来全是坑的数据结构。我在平时的项目里用它做过网络收发缓冲、日志落盘缓冲、音频采样缓存甚至嵌入式设备上的按键事件队列。用不好就出现丢数据、死锁、内存越界用好了性能比std::queue高一个量级。今天不聊教科书里那种只讲背定义的内容我把多年实战中总结的循环队列设计思路、模板实现、性能对比和典型 bug 全部整理出来凡是应该动手的部分都给了可直接跑的代码和避坑经验。无论你是刚开始学数据结构还是已经在业务代码里被并发队列折磨过这篇文章应该都能给你一些新的视角。1. 先搞清楚为什么普通队列做不到“循环”1.1 线性队列的“假溢出”问题所有接触过数据结构的人都知道队列是“队头出、队尾入”。但如果你直接用一个固定数组、两个下标front和rear来实现很快就会遇到一个尴尬局面明明数组前面一大半空间是空的rear 却已经指向数组末尾新元素再也入不了队。这就是经典的“假溢出”——队列没满却因为线性排列方式无法利用前面的空间来容纳新元素。假设数组长度是 8你连续入队 8 个元素front0rear8此时确实满了。但如果你先出队 5 个元素再入队 2 个元素rear 还是 8想继续入队就不行了可数组下标 0 到 4 明明是空的。这很浪费。最简单的补救办法是入队时整体把数据往前搬出队时整体把数据往前搬但每次搬移都是 O(n) 的操作。如果队列里存的是上万个包这种搬运很快就变成性能瓶颈。循环队列的核心思想就是让 rear 在到达数组末尾后自动绕回头部从逻辑上把数组首尾连接成环。下标不再是简单递增而是通过(rear 1) % capacity计算下一个位置这样前面空出来的位置就能被继续使用。这个看起来很聪明的做法实际落地时牵扯到边界判断、取模性能、扩容策略等一堆细节。1.2 “绕圈”之后带来的两个隐藏问题把数组变成环之后第一个问题就是“怎么判断队列是空还是满”。因为front rear这个条件在空队列时成立在满队列时也成立如果不做特殊处理。教科书里给过三种策略预留一个空格不存数据、增加一个计数器、用size字段单独记录。这三种我全都试过各有取舍我后面会单独开一节详细对比。第二个问题是取模运算的代价。(rear 1) % capacity在只知道容量是 2 的幂时可以直接用位运算替代但如果你使用的是运行时传入的任意容量那么取模指令会消耗不少 CPU 周期。在流量很大的场景下这个开销可能成为热点。更麻烦的是如果你设计的循环队列支持动态扩容那么“capacity 是 2 的幂”这个假设会与“可以任意扩容”冲突你在设计初期就必须做出选择。2. 核心原理与设计权衡别急着写代码2.1 队空/队满判断的三种策略对比先说最简单、也最常用的“预留一个槽位”策略。这种方案里队列最大容量是capacity - 1判断条件固定为队空front rear队满(rear 1) % capacity front我用这种方式写过很多队列最爽的是连size字段都不用维护入队出队时不涉及计数器的加减和内存同步单线程场景下非常干净。缺点就是“明明申请了 N 个格子实际只能用 N-1 个”在嵌入式内存紧张的时候会有点心疼。第二种方案是加一个count计数器。每次入队count出队count--判断满用count capacity。这样做的好处是可以完整利用所有槽位对外可以直接提供size()接口不需要通过公式间接计算。代价是计数器本身需要精确维护而且在多线程环境下它将成为一致性问题最容易出错的地方。我记得有一次排查问题时就是因为size和front、rear不是同时更新的导致线程读到了“半新半旧”的状态出现虚假空满判断。第三种方案是设置一个last_op标志位标记最后一次操作是入队还是出队。当front rear时如果最后一次操作是入队则说明满是出队则说明空。这个方案我很少用因为它需要每次操作都写一个布尔标志而且在某些并发场景下标志位的可见性会成为新的坑。除非你极度缺内存否则我不推荐这个方案。下面用表格总结一下方案最大可用容量是否需额外字段多线程友好度实际推荐度预留一个槽位capacity - 1无较友好推荐单线程和中低并发count 计数器capacity是int/atomic需要关心同步适合需要直接知道 size 的场景last_op 标志位capacity是bool/atomic较差几乎不推荐2.2 索引计算的性能陷阱索引计算是循环队列最热的路径之一。假设容量是cap每次入队写rear (rear 1) % cap这个取模运算在 CPU 上可能会被编译成一条除法指令耗时会比普通加法高几十倍。虽然现代 CPU 有优化但在每秒几百万次入队出队的循环里这点差异会被放大。我的习惯是如果队列容量固定且是 2 的幂就直接用capacity - 1做掩码把%换成rear (rear 1) (capacity - 1);但这里有个大坑capacity - 1作为掩码只有在 capacity 是 2 的幂时才成立。如果你在 4.0 版本允许了任意扩容到了 5.0 又引入了一个不满足 2 的幂的扩容因子那么之前所有位运算都会静默失效问题极其隐蔽——它不会立刻崩溃只会偶尔出现索引越界或者元素被覆盖。如果容量不是 2 的幂我又不想写%可以不用取模而是用“超过就减”的技巧。由于入队出队每次只移动一步所以可以用rear; if (rear capacity) rear 0;替代%。这样避免了除法指令而且逻辑非常直白。当然现代编译器在capacity是常量时可能会自动优化取模但我们的队列经常是运行时传入的参数编译器无法预知所以还是老老实实写成条件跳转更稳。2.3 动态扩容的三种思路循环队列是否需要动态扩容取决于你的使用场景。如果数据量峰值预先可知比如传感器采集缓存、按键事件队列我会直接固定容量做成无动态内存分配、无异常触发的严格版本。但如果你做一个通用工具库用户可能入队几千条也可能突然入队几百万条固定容量就不好用了。我试过三种扩容方案第一逐个元素搬到新数组。这是最容易理解的把front作为起点循环每个元素。但由于我们是循环结构搬运时要注意元素顺序不能错。很多人在这一步踩坑因为从front一直搬到rear步数应该是size()或capacity - 1预留槽位法而不是盲目搬capacity个。第二重新构造新队列对象然后循环push。代码最简洁但会产生重复的边界判断和可能的数据拷贝。如果旧队列很大性能较差。第三利用std::move在扩容时搬运尽可能避免深拷贝。这个方法最复杂但对非平凡类型比如存储了std::string效果显著。我会在下一节的实际实现里给出一个完整示例包含移动语义和异常安全。3. 从零实现一个可直接落地的模板循环队列3.1 接口设计与成员变量我不会用标准库容器当底层存储而是直接用裸指针加std::allocator自己管理内存。虽然std::vector可以省事但循环队列的重点恰恰在于精确控制内存布局和索引裸指针更能透明展示内部逻辑。这里我选择预留槽位法因为它在单线程、无锁场景下最简单可靠。先给出基础定义template typename T, typename Allocator std::allocatorT class CircularQueue { public: using value_type T; using allocator_type Allocator; using reference T; using const_reference const T; using size_type size_t; private: T* data_; size_type capacity_; size_type head_; size_type tail_; // 指向下一个入队位置 Allocator alloc_; };其中tail_表示下一个新元素要存放的位置。队空条件为head_ tail_队满条件为(tail_ 1) % capacity_ head_。因此capacity_必须至少为 1且实际可以存储的元素数量是capacity_ - 1。构造函数里我建议把capacity_设置为用户传入capacity加 1这样用户理解上的“队列容量”就是实际能存的元素个数不用去记忆“还要预留一个空格”。这个细节很影响 API 的易用性我在项目里就这样做使用者传入100就表示能装 100 个元素内部申请 101 个槽位。3.2 关键操作实现与细节讲解入队操作push需要处理异常安全。如果元素类型是std::string这类可能抛异常的类型我们先构造新元素再更新tail_防止发生异常时队列状态不一致。template typename U bool push(U value) { if (full()) return false; // 或者抛异常根据场景决定 alloc_.construct(data_ tail_, std::forwardU(value)); tail_ (tail_ 1) % capacity_; return true; }这里关键点是alloc_.construct(data_ tail_, ...)必须在修改tail_之前执行。如果先改了tail_再构造元素时抛异常队列就会处在一个“位置已经前进了但数据不存在”的坏状态。出队操作pop则相反先返回队头值的拷贝/移动然后调用析构函数最后移动head_。注意顺序也不能反因为一旦head_改变front()就不再指向旧元素了。T pop() { if (empty()) throw std::logic_error(queue is empty); T value std::move(data_[head_]); alloc_.destroy(data_ head_); head_ (head_ 1) % capacity_; return value; }这里std::move会把元素移出析构旧位置的值。返回类型如果是T可以配合返回值优化减少一次拷贝。如果你希望提供pop时不用抛异常可以改成std::optionalT但这样会产生额外开销另一种方式是返回布尔值并通过出参返回元素我在性能敏感的地方就是这么干bool pop(T out) { if (empty()) return false; out std::move(data_[head_]); alloc_.destroy(data_ head_); head_ (head_ 1) % capacity_; return true; }3.3 容易被忽略的拷贝与移动问题如果你只是写一个只存int的队列上面代码够了。但一旦存储类型变成std::string、自定义对象你就会遇到拷贝构造和移动构造的问题。容器在扩容时需要搬运所有剩余元素。如果元素类型是可移动的我们应该尽量使用移动语义避免深拷贝。下面是一段扩容函数template typename U void reallocate(size_type new_capacity) { T* new_data alloc_.allocate(new_capacity); size_type index 0; size_type count size(); for (size_type i 0; i count; i) { new_data[i] std::move(data_[(head_ i) % capacity_]); } // 销毁旧元素 for (size_type i 0; i count; i) { alloc_.destroy(data_ (head_ i) % capacity_); } alloc_.deallocate(data_, capacity_); data_ new_data; head_ 0; tail_ count; capacity_ new_capacity; }这段代码有三个容易忽略的点。第一搬运顺序不能乱因为循环中(head_ i) % capacity_算出来的位置会跨越数组首尾但输出到新数组时必须是连续从[0, count)排列。第二count必须先算出来不能在搬运过程中动态变化否则被移动后的旧元素可能丢失。第三如果移动赋值本身抛出异常新数据已经部分搬过去了旧数据还在队列会进入“半旧半新”状态。想在移动赋值可能抛异常的情况下保持强异常安全就很麻烦了。我实际项目中会要求存储类型满足“移动不抛异常”这不只是为了效率更是为了边界安全。如果你要处理的是移动可能抛异常的对象我建议干脆禁止自动扩容容量不够时直接丢弃或返回 false才最稳妥。另一个容易被忽略的是队列的拷贝赋值。如果两个队列容量不同拷贝时需要重新分配内存如果容量相同可以逐个元素拷贝。但要特别注意std::allocator在 C11 之后可以不等于而alloc_.deallocate必须使用同一个分配器实例。所以我实现的拷贝赋值会先检查两层东西分配器是否满足传播语义容量是否足够。这里代码比较啰嗦我不会全部展开但你写通用容器时这两点必须考虑。4. 实战三种典型应用场景与性能对比4.1 生产者-消费者模型中的无锁尝试循环队列最常见的场景就是“生产者-消费者”。我初学时的第一版就是给队列加一把互斥锁。这是正确的但性能不太好。如果生产者偶尔放数据消费者偶尔取数据锁竞争很小其实无所谓但如果两边都在高频操作锁的开销就会非常大。后来我改用“单生产者单消费者”的无锁方式。条件很苛刻只能有一个生产者线程一个消费者线程且他们不能同时读写同一个变量。入队线程只修改tail_和写入数据出队线程只修改head_和读取数据。两者都会读对方的变量但不能写对方的变量。在 C 里必须将head_和tail_声明为std::atomicsize_t并且要处理好内存序。我的经验是真正生产环境里很少自己写底层无锁队列因为内存序问题很容易出错。但理解这种设计有助于你正确使用别人写的并发队列。如果你只是想要一个线程安全的有界队列可以使用“互斥锁 条件变量 循环队列存储”的组合循环队列在这里的好处是不需要频繁分配释放内存长度可控不会无限制增长。下面是一个简单的多线程安全包装思路template typename T class ThreadSafeCircularQueue { private: CircularQueueT queue_; mutable std::mutex mutex_; std::condition_variable not_full_; std::condition_variable not_empty_; // ... public: bool push(const T item) { std::unique_lock lock(mutex_); while (queue_.full()) { not_full_.wait(lock); } queue_.push(item); not_empty_.notify_one(); return true; } bool pop(T item) { std::unique_lock lock(mutex_); while (queue_.empty()) { not_empty_.wait(lock); } queue_.pop(item); not_full_.notify_one(); return true; } };这里我用while而不是if来做条件等待是因为条件变量可能被虚假唤醒。很多人第一次写都会漏掉这个细节导致队列空时仍然继续出队。4.2 日志系统中的环形缓冲日志系统是高吞吐场景不能每写一条日志就开一次文件、刷一次磁盘。我做过一个日志缓冲模块主线程将格式化好的日志字符串通过循环队列写入一个缓冲池后台线程负责从队列取出并批量写入文件。在这种场景下循环队列的核心价值在于控制内存上限。如果某项业务突然故障日志量暴增使用std::queue作为缓冲会因为无限增长而吃光内存。循环队列有固定容量超过容量的日志可以选择丢弃或者覆盖最旧日志。覆盖模式甚至不需要判断满——直接入队新的覆盖旧的。对跟踪故障来说保留最新的日志往往比保留最老的更有效。我当时实现了一个bool overwrite标志在满的时候如果该标志为真则直接把head_向后移动一步再写入这本质上就是一个“ring buffer”。此外日志场景里队列元素往往是已经格式化好的字符串。我用上文提到的push(std::move(string))后台线程pop时再移动配合内存池和reserve策略可以把频繁的小字符串分配变成较少的、可预测的大内存块分配整体性能提升明显。4.3 与 std::queue 的性能对比实测我专门写了一个对比测试入队 1000 万个整数再全部出队。底层容器std::queueint使用std::dequeint循环队列使用固定容量10485762 的 20 次方。测试环境是普通桌面 CPU开启-O2优化。std::deque的入队出队并不慢因为deque是分段连续内存不需要一个个节点分配。但它的每次push和pop都可能有分支和潜在的内存预分配我的循环队列在掩码索引下计算开销更低。实测结果循环队列大约能跑出 1.2 倍到 2 倍的优势。在并发场景加上锁之后差距还会缩小。所以如果你的性能瓶颈不在队列本身不要盲目优化。我在一次网络转发项目里把原来的std::queue换成固定容量循环队列主要目的是限制内存使用而不是追求那一两倍的吞吐。循环队列真正的优势是“内存固定、延迟可预测”这一点在高实时性系统中远比吞吐量重要。如果你想观察性能建议测试时加上perf或valgrind --toolcachegrind看缓存命中率。循环队列因为数据紧密连续cache 命中率比链式队列高很多这个特性在数据量大时尤其明显。5. 常见问题与排查技巧实录5.1 满/空判断失效的经典bug我遇到过一个特别隐蔽的 bug使用预留槽位法但是在入队判断时写成了tail_ 1 head_忘记对容量取模。当尾部绕过头到数组开头时这个条件永远不成立队列会一直写入覆盖掉还没有出队的数据。排查时现象表现为“数据错乱”、size()值大于实际可存储数量。解决方案很简单所有索引更新和满空判断必须使用同一个取模策略。我建议封装两个私有函数size_type advance(size_type index) const noexcept { return (index 1 capacity_) ? 0 : index 1; } bool full() const noexcept { return advance(tail_) head_; }这样以后复用就不会出现“一处取模一处不取模”的问题。我在代码审查里看到过类似的 bug 不下三次每次都在满队列边界。另一个常见 bug 是size()的计算。当tail_ head_时size tail_ - head_当tail_ head_时size capacity_ - head_ tail_。有很多人直接写abs(tail_ - head_)这显然是错的因为循环跨越了数组边界。我习惯统一写成size_type size() const noexcept { if (tail_ head_) return tail_ - head_; return capacity_ - head_ tail_; }5.2 多线程下的内存可见性陷阱在单线程代码里你不用担心head_和tail_的顺序但一旦进入多线程即使使用了互斥锁也可能遇到内存可见性问题。锁本身会建立内存屏障但前提是你要把锁理解成“同步点”而不是只保护临界区内代码。更隐蔽的是无锁单生产者单消费者队列。假设消费者先检查empty()发现tail_ head_于是认为空。但此时生产者刚刚写入数据正在更新tail_由于没有正确同步消费者可能看不到最新的tail_。即使tail_是std::atomicsize_t如果你用的是默认的memory_order_seq_cst问题不大但如果你为性能改为memory_order_relaxed就会踩坑。我的建议生产者写数据和更新tail_之间必须用release语义消费者读取tail_并访问数据之间必须用acquire语义。这是底层无锁循环队列正确性的关键。标记为std::atomic并显式指定内存序tail_.store(new_tail, std::memory_order_release); head_.load(std::memory_order_acquire);如果你不确定不要自行用原子操作老老实实加锁。在我见过的实际项目中无锁队列带来的性能提升往往被复杂的调试成本抵消。5.3 缓存命中率与内存布局优化数据结构的 cache 友好程度在特定业务下决定了性能上限。链式队列每个节点分配在堆上节点地址跳跃遍历时容易 cache miss循环队列的底层数组是连续内存从head_到tail_遍历时大部分访问都集中在相邻地址cache 命中率远高于链式。你再进一步优化让capacity_设置为 2 的 N 次方后索引可以用位运算而且数组大小刚好不会超出某个 cache line 边界太多。如果数据结构容纳的是固定大小的小对象可以考虑把数组按“8 字节对齐”分配在某些平台上能提高读写的组合效率。但注意不要过度。我遇到过有人为了对齐把队列元素从 24 字节变成 32 字节结果内存占用上升cache 能容纳的元素数反而下降了性能没提升还变差。内存布局优化要基于真实 profile而不是直觉。我在优化网络收包缓冲时首先用perf stat观察 cache-misses然后才决定是否把容量改成 2 的幂、是否调整元素结构体字段顺序。在没有 profile 的前提下做的“优化”很可能只是自我安慰。6. 快速选型清单与实用心得如果你现在需要在自己的项目里使用循环队列我建议按以下清单快速决策问题建议单线程容量固定预留槽位法裸数组 条件判断取代模单线程容量可变模板循环队列 扩容存储类型最好可移动不抛异常多线程要求安全但不要求极限性能互斥锁 条件变量包装循环队列多线程单生产者单消费者极致性能原子变量 显式内存序的无锁循环队列务必做充分测试多线程多生产者多消费者考虑分片/多队列或使用成熟的并发容器不建议自己写锁我在实际使用中最深的体会是循环队列不难难的是把所有边界条件和生命周期管理做对。“预留一个槽位”让代码简单但你需要花时间向团队成员解释为什么有效容量是 capacity-1如果团队新人多我会选择count方案直白明了代价是多维护一个变量。没有绝对最佳只有和团队认知水平匹配的设计。最后再分享一个小技巧如果你在嵌入式或无异常环境里使用循环队列把push和pop的“失败”设计成返回bool而不是抛异常调用方可以直接忽略返回值代码不会因为try-catch膨胀。并且固定容量循环队列可以在栈上分配底层数组用std::arrayT, N实例化完全不需要堆分配。像这样template typename T, size_t N class StaticCircularQueue { std::arrayT, N 1 storage_; size_t head_ 0, tail_ 0; // ... };这个形态很适合单片机或实时音频处理我经常在延迟要求苛刻的处理链里这么用。持续运行几个月也不会产生内存碎片这是循环队列最大的隐藏价值。 
长河君 · 2026/10/21 23:08:42 · 阅读 1.2k 循环队列从原理到实战：模板实现、性能对比与踩坑避坑指南
循环队列是那种看起来很简单、写起来全是坑的数据结构。我在平时的项目里用它做过网络收发缓冲、日志落盘缓冲、音频采样缓存甚至嵌入式设备上的按键事件队列。用不好就出现丢数据、死锁、内存越界用好了性能比std::queue高一个量级。今天不聊教科书里那种只讲背定义的内容我把多年实战中总结的循环队列设计思路、模板实现、性能对比和典型 bug 全部整理出来凡是应该动手的部分都给了可直接跑的代码和避坑经验。无论你是刚开始学数据结构还是已经在业务代码里被并发队列折磨过这篇文章应该都能给你一些新的视角。1. 先搞清楚为什么普通队列做不到“循环”1.1 线性队列的“假溢出”问题所有接触过数据结构的人都知道队列是“队头出、队尾入”。但如果你直接用一个固定数组、两个下标front和rear来实现很快就会遇到一个尴尬局面明明数组前面一大半空间是空的rear 却已经指向数组末尾新元素再也入不了队。这就是经典的“假溢出”——队列没满却因为线性排列方式无法利用前面的空间来容纳新元素。假设数组长度是 8你连续入队 8 个元素front0rear8此时确实满了。但如果你先出队 5 个元素再入队 2 个元素rear 还是 8想继续入队就不行了可数组下标 0 到 4 明明是空的。这很浪费。最简单的补救办法是入队时整体把数据往前搬出队时整体把数据往前搬但每次搬移都是 O(n) 的操作。如果队列里存的是上万个包这种搬运很快就变成性能瓶颈。循环队列的核心思想就是让 rear 在到达数组末尾后自动绕回头部从逻辑上把数组首尾连接成环。下标不再是简单递增而是通过(rear 1) % capacity计算下一个位置这样前面空出来的位置就能被继续使用。这个看起来很聪明的做法实际落地时牵扯到边界判断、取模性能、扩容策略等一堆细节。1.2 “绕圈”之后带来的两个隐藏问题把数组变成环之后第一个问题就是“怎么判断队列是空还是满”。因为front rear这个条件在空队列时成立在满队列时也成立如果不做特殊处理。教科书里给过三种策略预留一个空格不存数据、增加一个计数器、用size字段单独记录。这三种我全都试过各有取舍我后面会单独开一节详细对比。第二个问题是取模运算的代价。(rear 1) % capacity在只知道容量是 2 的幂时可以直接用位运算替代但如果你使用的是运行时传入的任意容量那么取模指令会消耗不少 CPU 周期。在流量很大的场景下这个开销可能成为热点。更麻烦的是如果你设计的循环队列支持动态扩容那么“capacity 是 2 的幂”这个假设会与“可以任意扩容”冲突你在设计初期就必须做出选择。2. 核心原理与设计权衡别急着写代码2.1 队空/队满判断的三种策略对比先说最简单、也最常用的“预留一个槽位”策略。这种方案里队列最大容量是capacity - 1判断条件固定为队空front rear队满(rear 1) % capacity front我用这种方式写过很多队列最爽的是连size字段都不用维护入队出队时不涉及计数器的加减和内存同步单线程场景下非常干净。缺点就是“明明申请了 N 个格子实际只能用 N-1 个”在嵌入式内存紧张的时候会有点心疼。第二种方案是加一个count计数器。每次入队count出队count--判断满用count capacity。这样做的好处是可以完整利用所有槽位对外可以直接提供size()接口不需要通过公式间接计算。代价是计数器本身需要精确维护而且在多线程环境下它将成为一致性问题最容易出错的地方。我记得有一次排查问题时就是因为size和front、rear不是同时更新的导致线程读到了“半新半旧”的状态出现虚假空满判断。第三种方案是设置一个last_op标志位标记最后一次操作是入队还是出队。当front rear时如果最后一次操作是入队则说明满是出队则说明空。这个方案我很少用因为它需要每次操作都写一个布尔标志而且在某些并发场景下标志位的可见性会成为新的坑。除非你极度缺内存否则我不推荐这个方案。下面用表格总结一下方案最大可用容量是否需额外字段多线程友好度实际推荐度预留一个槽位capacity - 1无较友好推荐单线程和中低并发count 计数器capacity是int/atomic需要关心同步适合需要直接知道 size 的场景last_op 标志位capacity是bool/atomic较差几乎不推荐2.2 索引计算的性能陷阱索引计算是循环队列最热的路径之一。假设容量是cap每次入队写rear (rear 1) % cap这个取模运算在 CPU 上可能会被编译成一条除法指令耗时会比普通加法高几十倍。虽然现代 CPU 有优化但在每秒几百万次入队出队的循环里这点差异会被放大。我的习惯是如果队列容量固定且是 2 的幂就直接用capacity - 1做掩码把%换成rear (rear 1) (capacity - 1);但这里有个大坑capacity - 1作为掩码只有在 capacity 是 2 的幂时才成立。如果你在 4.0 版本允许了任意扩容到了 5.0 又引入了一个不满足 2 的幂的扩容因子那么之前所有位运算都会静默失效问题极其隐蔽——它不会立刻崩溃只会偶尔出现索引越界或者元素被覆盖。如果容量不是 2 的幂我又不想写%可以不用取模而是用“超过就减”的技巧。由于入队出队每次只移动一步所以可以用rear; if (rear capacity) rear 0;替代%。这样避免了除法指令而且逻辑非常直白。当然现代编译器在capacity是常量时可能会自动优化取模但我们的队列经常是运行时传入的参数编译器无法预知所以还是老老实实写成条件跳转更稳。2.3 动态扩容的三种思路循环队列是否需要动态扩容取决于你的使用场景。如果数据量峰值预先可知比如传感器采集缓存、按键事件队列我会直接固定容量做成无动态内存分配、无异常触发的严格版本。但如果你做一个通用工具库用户可能入队几千条也可能突然入队几百万条固定容量就不好用了。我试过三种扩容方案第一逐个元素搬到新数组。这是最容易理解的把front作为起点循环每个元素。但由于我们是循环结构搬运时要注意元素顺序不能错。很多人在这一步踩坑因为从front一直搬到rear步数应该是size()或capacity - 1预留槽位法而不是盲目搬capacity个。第二重新构造新队列对象然后循环push。代码最简洁但会产生重复的边界判断和可能的数据拷贝。如果旧队列很大性能较差。第三利用std::move在扩容时搬运尽可能避免深拷贝。这个方法最复杂但对非平凡类型比如存储了std::string效果显著。我会在下一节的实际实现里给出一个完整示例包含移动语义和异常安全。3. 从零实现一个可直接落地的模板循环队列3.1 接口设计与成员变量我不会用标准库容器当底层存储而是直接用裸指针加std::allocator自己管理内存。虽然std::vector可以省事但循环队列的重点恰恰在于精确控制内存布局和索引裸指针更能透明展示内部逻辑。这里我选择预留槽位法因为它在单线程、无锁场景下最简单可靠。先给出基础定义template typename T, typename Allocator std::allocatorT class CircularQueue { public: using value_type T; using allocator_type Allocator; using reference T; using const_reference const T; using size_type size_t; private: T* data_; size_type capacity_; size_type head_; size_type tail_; // 指向下一个入队位置 Allocator alloc_; };其中tail_表示下一个新元素要存放的位置。队空条件为head_ tail_队满条件为(tail_ 1) % capacity_ head_。因此capacity_必须至少为 1且实际可以存储的元素数量是capacity_ - 1。构造函数里我建议把capacity_设置为用户传入capacity加 1这样用户理解上的“队列容量”就是实际能存的元素个数不用去记忆“还要预留一个空格”。这个细节很影响 API 的易用性我在项目里就这样做使用者传入100就表示能装 100 个元素内部申请 101 个槽位。3.2 关键操作实现与细节讲解入队操作push需要处理异常安全。如果元素类型是std::string这类可能抛异常的类型我们先构造新元素再更新tail_防止发生异常时队列状态不一致。template typename U bool push(U value) { if (full()) return false; // 或者抛异常根据场景决定 alloc_.construct(data_ tail_, std::forwardU(value)); tail_ (tail_ 1) % capacity_; return true; }这里关键点是alloc_.construct(data_ tail_, ...)必须在修改tail_之前执行。如果先改了tail_再构造元素时抛异常队列就会处在一个“位置已经前进了但数据不存在”的坏状态。出队操作pop则相反先返回队头值的拷贝/移动然后调用析构函数最后移动head_。注意顺序也不能反因为一旦head_改变front()就不再指向旧元素了。T pop() { if (empty()) throw std::logic_error(queue is empty); T value std::move(data_[head_]); alloc_.destroy(data_ head_); head_ (head_ 1) % capacity_; return value; }这里std::move会把元素移出析构旧位置的值。返回类型如果是T可以配合返回值优化减少一次拷贝。如果你希望提供pop时不用抛异常可以改成std::optionalT但这样会产生额外开销另一种方式是返回布尔值并通过出参返回元素我在性能敏感的地方就是这么干bool pop(T out) { if (empty()) return false; out std::move(data_[head_]); alloc_.destroy(data_ head_); head_ (head_ 1) % capacity_; return true; }3.3 容易被忽略的拷贝与移动问题如果你只是写一个只存int的队列上面代码够了。但一旦存储类型变成std::string、自定义对象你就会遇到拷贝构造和移动构造的问题。容器在扩容时需要搬运所有剩余元素。如果元素类型是可移动的我们应该尽量使用移动语义避免深拷贝。下面是一段扩容函数template typename U void reallocate(size_type new_capacity) { T* new_data alloc_.allocate(new_capacity); size_type index 0; size_type count size(); for (size_type i 0; i count; i) { new_data[i] std::move(data_[(head_ i) % capacity_]); } // 销毁旧元素 for (size_type i 0; i count; i) { alloc_.destroy(data_ (head_ i) % capacity_); } alloc_.deallocate(data_, capacity_); data_ new_data; head_ 0; tail_ count; capacity_ new_capacity; }这段代码有三个容易忽略的点。第一搬运顺序不能乱因为循环中(head_ i) % capacity_算出来的位置会跨越数组首尾但输出到新数组时必须是连续从[0, count)排列。第二count必须先算出来不能在搬运过程中动态变化否则被移动后的旧元素可能丢失。第三如果移动赋值本身抛出异常新数据已经部分搬过去了旧数据还在队列会进入“半旧半新”状态。想在移动赋值可能抛异常的情况下保持强异常安全就很麻烦了。我实际项目中会要求存储类型满足“移动不抛异常”这不只是为了效率更是为了边界安全。如果你要处理的是移动可能抛异常的对象我建议干脆禁止自动扩容容量不够时直接丢弃或返回 false才最稳妥。另一个容易被忽略的是队列的拷贝赋值。如果两个队列容量不同拷贝时需要重新分配内存如果容量相同可以逐个元素拷贝。但要特别注意std::allocator在 C11 之后可以不等于而alloc_.deallocate必须使用同一个分配器实例。所以我实现的拷贝赋值会先检查两层东西分配器是否满足传播语义容量是否足够。这里代码比较啰嗦我不会全部展开但你写通用容器时这两点必须考虑。4. 实战三种典型应用场景与性能对比4.1 生产者-消费者模型中的无锁尝试循环队列最常见的场景就是“生产者-消费者”。我初学时的第一版就是给队列加一把互斥锁。这是正确的但性能不太好。如果生产者偶尔放数据消费者偶尔取数据锁竞争很小其实无所谓但如果两边都在高频操作锁的开销就会非常大。后来我改用“单生产者单消费者”的无锁方式。条件很苛刻只能有一个生产者线程一个消费者线程且他们不能同时读写同一个变量。入队线程只修改tail_和写入数据出队线程只修改head_和读取数据。两者都会读对方的变量但不能写对方的变量。在 C 里必须将head_和tail_声明为std::atomicsize_t并且要处理好内存序。我的经验是真正生产环境里很少自己写底层无锁队列因为内存序问题很容易出错。但理解这种设计有助于你正确使用别人写的并发队列。如果你只是想要一个线程安全的有界队列可以使用“互斥锁 条件变量 循环队列存储”的组合循环队列在这里的好处是不需要频繁分配释放内存长度可控不会无限制增长。下面是一个简单的多线程安全包装思路template typename T class ThreadSafeCircularQueue { private: CircularQueueT queue_; mutable std::mutex mutex_; std::condition_variable not_full_; std::condition_variable not_empty_; // ... public: bool push(const T item) { std::unique_lock lock(mutex_); while (queue_.full()) { not_full_.wait(lock); } queue_.push(item); not_empty_.notify_one(); return true; } bool pop(T item) { std::unique_lock lock(mutex_); while (queue_.empty()) { not_empty_.wait(lock); } queue_.pop(item); not_full_.notify_one(); return true; } };这里我用while而不是if来做条件等待是因为条件变量可能被虚假唤醒。很多人第一次写都会漏掉这个细节导致队列空时仍然继续出队。4.2 日志系统中的环形缓冲日志系统是高吞吐场景不能每写一条日志就开一次文件、刷一次磁盘。我做过一个日志缓冲模块主线程将格式化好的日志字符串通过循环队列写入一个缓冲池后台线程负责从队列取出并批量写入文件。在这种场景下循环队列的核心价值在于控制内存上限。如果某项业务突然故障日志量暴增使用std::queue作为缓冲会因为无限增长而吃光内存。循环队列有固定容量超过容量的日志可以选择丢弃或者覆盖最旧日志。覆盖模式甚至不需要判断满——直接入队新的覆盖旧的。对跟踪故障来说保留最新的日志往往比保留最老的更有效。我当时实现了一个bool overwrite标志在满的时候如果该标志为真则直接把head_向后移动一步再写入这本质上就是一个“ring buffer”。此外日志场景里队列元素往往是已经格式化好的字符串。我用上文提到的push(std::move(string))后台线程pop时再移动配合内存池和reserve策略可以把频繁的小字符串分配变成较少的、可预测的大内存块分配整体性能提升明显。4.3 与 std::queue 的性能对比实测我专门写了一个对比测试入队 1000 万个整数再全部出队。底层容器std::queueint使用std::dequeint循环队列使用固定容量10485762 的 20 次方。测试环境是普通桌面 CPU开启-O2优化。std::deque的入队出队并不慢因为deque是分段连续内存不需要一个个节点分配。但它的每次push和pop都可能有分支和潜在的内存预分配我的循环队列在掩码索引下计算开销更低。实测结果循环队列大约能跑出 1.2 倍到 2 倍的优势。在并发场景加上锁之后差距还会缩小。所以如果你的性能瓶颈不在队列本身不要盲目优化。我在一次网络转发项目里把原来的std::queue换成固定容量循环队列主要目的是限制内存使用而不是追求那一两倍的吞吐。循环队列真正的优势是“内存固定、延迟可预测”这一点在高实时性系统中远比吞吐量重要。如果你想观察性能建议测试时加上perf或valgrind --toolcachegrind看缓存命中率。循环队列因为数据紧密连续cache 命中率比链式队列高很多这个特性在数据量大时尤其明显。5. 常见问题与排查技巧实录5.1 满/空判断失效的经典bug我遇到过一个特别隐蔽的 bug使用预留槽位法但是在入队判断时写成了tail_ 1 head_忘记对容量取模。当尾部绕过头到数组开头时这个条件永远不成立队列会一直写入覆盖掉还没有出队的数据。排查时现象表现为“数据错乱”、size()值大于实际可存储数量。解决方案很简单所有索引更新和满空判断必须使用同一个取模策略。我建议封装两个私有函数size_type advance(size_type index) const noexcept { return (index 1 capacity_) ? 0 : index 1; } bool full() const noexcept { return advance(tail_) head_; }这样以后复用就不会出现“一处取模一处不取模”的问题。我在代码审查里看到过类似的 bug 不下三次每次都在满队列边界。另一个常见 bug 是size()的计算。当tail_ head_时size tail_ - head_当tail_ head_时size capacity_ - head_ tail_。有很多人直接写abs(tail_ - head_)这显然是错的因为循环跨越了数组边界。我习惯统一写成size_type size() const noexcept { if (tail_ head_) return tail_ - head_; return capacity_ - head_ tail_; }5.2 多线程下的内存可见性陷阱在单线程代码里你不用担心head_和tail_的顺序但一旦进入多线程即使使用了互斥锁也可能遇到内存可见性问题。锁本身会建立内存屏障但前提是你要把锁理解成“同步点”而不是只保护临界区内代码。更隐蔽的是无锁单生产者单消费者队列。假设消费者先检查empty()发现tail_ head_于是认为空。但此时生产者刚刚写入数据正在更新tail_由于没有正确同步消费者可能看不到最新的tail_。即使tail_是std::atomicsize_t如果你用的是默认的memory_order_seq_cst问题不大但如果你为性能改为memory_order_relaxed就会踩坑。我的建议生产者写数据和更新tail_之间必须用release语义消费者读取tail_并访问数据之间必须用acquire语义。这是底层无锁循环队列正确性的关键。标记为std::atomic并显式指定内存序tail_.store(new_tail, std::memory_order_release); head_.load(std::memory_order_acquire);如果你不确定不要自行用原子操作老老实实加锁。在我见过的实际项目中无锁队列带来的性能提升往往被复杂的调试成本抵消。5.3 缓存命中率与内存布局优化数据结构的 cache 友好程度在特定业务下决定了性能上限。链式队列每个节点分配在堆上节点地址跳跃遍历时容易 cache miss循环队列的底层数组是连续内存从head_到tail_遍历时大部分访问都集中在相邻地址cache 命中率远高于链式。你再进一步优化让capacity_设置为 2 的 N 次方后索引可以用位运算而且数组大小刚好不会超出某个 cache line 边界太多。如果数据结构容纳的是固定大小的小对象可以考虑把数组按“8 字节对齐”分配在某些平台上能提高读写的组合效率。但注意不要过度。我遇到过有人为了对齐把队列元素从 24 字节变成 32 字节结果内存占用上升cache 能容纳的元素数反而下降了性能没提升还变差。内存布局优化要基于真实 profile而不是直觉。我在优化网络收包缓冲时首先用perf stat观察 cache-misses然后才决定是否把容量改成 2 的幂、是否调整元素结构体字段顺序。在没有 profile 的前提下做的“优化”很可能只是自我安慰。6. 快速选型清单与实用心得如果你现在需要在自己的项目里使用循环队列我建议按以下清单快速决策问题建议单线程容量固定预留槽位法裸数组 条件判断取代模单线程容量可变模板循环队列 扩容存储类型最好可移动不抛异常多线程要求安全但不要求极限性能互斥锁 条件变量包装循环队列多线程单生产者单消费者极致性能原子变量 显式内存序的无锁循环队列务必做充分测试多线程多生产者多消费者考虑分片/多队列或使用成熟的并发容器不建议自己写锁我在实际使用中最深的体会是循环队列不难难的是把所有边界条件和生命周期管理做对。“预留一个槽位”让代码简单但你需要花时间向团队成员解释为什么有效容量是 capacity-1如果团队新人多我会选择count方案直白明了代价是多维护一个变量。没有绝对最佳只有和团队认知水平匹配的设计。最后再分享一个小技巧如果你在嵌入式或无异常环境里使用循环队列把push和pop的“失败”设计成返回bool而不是抛异常调用方可以直接忽略返回值代码不会因为try-catch膨胀。并且固定容量循环队列可以在栈上分配底层数组用std::arrayT, N实例化完全不需要堆分配。像这样template typename T, size_t N class StaticCircularQueue { std::arrayT, N 1 storage_; size_t head_ 0, tail_ 0; // ... };这个形态很适合单片机或实时音频处理我经常在延迟要求苛刻的处理链里这么用。持续运行几个月也不会产生内存碎片这是循环队列最大的隐藏价值。