前言
"循环队列"（circular queue，也叫环形缓冲区 ring buffer）是数据结构课上必讲的一个结构：用一个固定大小的数组当队列，front和tail走到数组末尾就绕回开头，从而复用被pop释放出来的空间。标题把它写成"C++ 循环队列"，需要先说清一件事：循环队列不是 C++ 标准库里的组件。标准库提供的队列是<queue>里的std::queue，它是一个容器适配器（container adapter），底层默认用std::deque实现，它的扩容行为是"动态增长"，不是"循环复用固定数组"。
这两个东西的取舍是：std::queue写起来最省事、能无限增长；循环队列容量固定、内存不增长、没有动态分配，适合嵌入式、音视频缓冲、生产者-消费者这类"缓冲区大小必须可控"的场景。
本文讲三件事：循环队列的判空判满有哪几种做法、C++ 里怎么写出一个正确可编译的版本、以及它和std::queue、std::deque的边界在哪。代码以 C++17 为基准。
一、循环队列的核心：怎么区分"空"和"满"
用数组实现队列，front指向队头元素，tail指向队尾元素的下一个位置（或者队尾元素本身，两种约定都有人用）。入队时写buf[tail]然后tail = (tail + 1) % capacity。问题来了：队列空的时候front == tail，队列满的时候如果元素占满了整个数组，front也会等于tail。同一个条件对应两种状态，没法区分。
业界有三种解决办法：
| 方案 | 判空 | 判满 | 可用容量 | 说明 |
|---|---|---|---|---|
| 浪费一个槽位 | front == tail | (tail + 1) % cap == front | cap - 1 | 实现最简单，代价是永远少存一个元素 |
| 维护计数器 | count == 0 | count == cap | cap | 空间全用上，每次操作多维护一个变量 |
| 加一个标志位 | front == tail && !full | front == tail && full | cap | 省空间，但每个分支都要记得同步标志，容易忘 |
本文选计数器方案：它的不变式（invariant）最容易验证——count就是元素个数，判空判满都是直接看它，没有"少用一个格子"的心理负担，也不像标志位那样容易忘记更新。
二、用 std::vector 做底的模板实现
// C++17，单文件：g++ -std=c++17 -Wall -Wextra circular_queue.cpp #include <cstddef> #include <iostream> #include <stdexcept> #include <string> #include <utility> #include <vector> template <class T> class CircularQueue { public: explicit CircularQueue(std::size_t capacity) : buf_(capacity), head_(0), tail_(0), count_(0) { if (capacity == 0) { throw std::invalid_argument("CircularQueue: capacity must be > 0"); } } std::size_t size() const { return count_; } std::size_t capacity() const { return buf_.size(); } bool empty() const { return count_ == 0; } bool full() const { return count_ == buf_.size(); } // 入队：满了返回 false，调用方决定怎么办（丢弃 / 阻塞 / 覆盖） bool push(const T& value) { if (full()) return false; buf_[tail_] = value; tail_ = next(tail_); ++count_; return true; } // 移动版：避免 T 的拷贝构造被调用 bool push(T&& value) { if (full()) return false; buf_[tail_] = std::move(value); tail_ = next(tail_); ++count_; return true; } // 出队到自己提供的变量里，成功返回 true bool pop(T& out) { if (empty()) return false; out = std::move(buf_[head_]); head_ = next(head_); --count_; return true; } // 看一眼队头（不出队） const T& front() const { if (empty()) throw std::out_of_range("CircularQueue::front on empty queue"); return buf_[head_]; } const T& back() const { if (empty()) throw std::out_of_range("CircularQueue::back on empty queue"); // tail_ 指向"下一个要写的位置"，往回退一格就是队尾，注意绕回 return buf_[(tail_ + buf_.size() - 1) % buf_.size()]; } void clear() { head_ = tail_ = count_ = 0; } private: std::size_t next(std::size_t i) const { return (i + 1 == buf_.size()) ? 0 : i + 1; // 条件加法比取模快，且无溢出 } std::vector<T> buf_; std::size_t head_; // 队头元素下标 std::size_t tail_; // 下一个可写位置（等价于队尾元素下标 +1） std::size_t count_; // 当前元素个数 }; int main() { CircularQueue<int> q(4); // 容量 4，可存 4 个（计数器方案不浪费槽位） std::cout << std::boolalpha << "empty=" << q.empty() << '\n'; for (int i = 1; i <= 5; ++i) { std::cout << "push(" << i << ") -> " << q.push(i) << '\n'; } std::cout << "size=" << q.size() << " full=" << q.full() << '\n'; std::cout << "front=" << q.front() << " back=" << q.back() << '\n'; int v = 0; while (q.pop(v)) std::cout << "pop -> " << v << '\n'; // 绕回验证：反复填满再清空，检查下标是否正常循环 for (int round = 0; round < 3; ++round) { for (int i = 0; i < 4; ++i) q.push(round * 10 + i); int x = 0; while (q.pop(x)) std::cout << x << ' '; std::cout << '\n'; } return 0; }几个实现上的选择值得说明：
next()用条件加法而不是取模。(i + 1) % N语义正确，但整数取模在多数硬件上是十几到几十个周期的除法指令，而i + 1 == N ? 0 : i + 1只是一个比较加一个加法。当 N 是 2 的幂时，编译器通常会把% N优化成位与，但如果 N 是运行期决定的（比如构造函数传入），它就不会做这个优化。这里只是说清原理，具体快多少请以你在目标平台上的实测为准。另外要注意：只有条件写法能彻底避免i + 1的溢出问题——i最大是buf_.size() - 1，i + 1最多等于buf_.size()，不会溢出；而如果换成一个接近SIZE_MAX的下标，(i + 1) % N里的i + 1就可能回绕。在这个类里i永不超过buf_.size()，所以两种写法都安全。
push返回bool而不是抛异常。队列满是一个预期内的正常状况，不是异常情况。返回bool把决策权交给调用方：视频流可以丢弃旧的帧，网络协议栈可以让发送方重试，实时系统可以计数丢弃率。这也和标准库的std::queue::push不同——后者永远成功（底层容器会扩容）。
push(T&&)与push(const T&)两个重载。这是 C++11 之后写容器的标准做法：右值走移动，左值走拷贝。注意buf_[tail_] = std::move(value)要求T可移动赋值；对只有拷贝的类型，std::move会退回到拷贝，不会编译失败（前提是拷贝赋值存在）。
back()里的(tail_ + buf_.size() - 1) % buf_.size()。不能写成(tail_ - 1) % size：tail_是无符号的std::size_t，当tail_ == 0时tail_ - 1会下溢成SIZE_MAX，SIZE_MAX % 4得到的不是 3。先加size再减 1 就不会下溢。无符号下溢本身不是 UB（标准规定按 2 的幂取模），但结果完全不是你要的。
三、和 std::queue 的对比
std::queue是容器适配器，声明形式（以标准为准）是template<class T, class Container = std::deque<T>> class queue。它的接口是：
| 成员函数 | 语义 |
|---|---|
push(const T&)/push(T&&) | 在队尾追加 |
emplace(args...) | 在队尾原地构造 |
pop() | 移除队头元素，返回 void，不返回被移除的值 |
front()/back() | 访问队头 / 队尾元素（引用），空队列上调用是 UB |
empty()/size() | 判空 / 元素个数 |
和本文的循环队列对比：
| 维度 | std::queue（默认基于std::deque） | 循环队列（固定数组） |
|---|---|---|
| 容量 | 动态增长，理论上不限 | 固定，构造时确定 |
| 内存分配 | 随着增长会有新的分配（具体策略由实现决定） | 构造时一次分配，此后不再分配 |
| 满时行为 | 不会满，push总是成功 | 由你决定：丢弃、拒绝、覆盖 |
| 复杂度 | push/pop均摊 O(1) | 严格 O(1)，没有均摊的尾巴 |
| 迭代 | 适配器不提供迭代器 | 同样不提供（要遍历得自己暴露接口） |
| 典型场景 | 一般业务队列 | 嵌入式、音频缓冲、无锁队列的前身 |
std::queue::pop()不返回元素，这是初学者最常抱怨的一点：必须front()和pop()分两步，中间还可能因为异常导致元素丢失。循环队列可以顺手提供"出队并返回"的接口，这也是它在实际工程里更顺手的原因之一。但要注意，pop()里的out = std::move(buf_[head_])如果T的移动赋值抛异常，队列状态就会不一致——真实工程里要么要求T的移动构造/赋值是noexcept（这也是std::vector扩容时的判断标准），要么把这一步改成"先移动构造到临时对象，成功后再推进head_"。
四、要不要"满时覆盖"的变体
环形缓冲在音视频和日志场景里常见的变体是"满了就覆盖最旧的"：
// C++17 // 满时覆盖最旧元素，永远不失败 void push_overwrite(const T& value) { if (full()) { head_ = next(head_); // 挤掉队头，count_ 不变 } else { ++count_; } buf_[tail_] = value; tail_ = next(tail_); }这个变体的语义是"只保留最近 N 个"。它比push更容易写错，因为head_、tail_、count_三者的更新顺序在"满"和"不满"两条路径里不一样。写完一定要用"反复填满再清空、检查输出顺序"的循环测一遍——本文main里的 round 循环就是这个用途。
常见坑点
坑 1：用size()当"元素个数"，但它其实是容量。
❌ 写了buf_.size()来表示队内元素个数，于是"队列有多少元素"和"最多能装多少"混在一起。
✅ 分成两个名字：capacity()返回buf_.size()，size()返回count_。这是标准库容器的命名约定（std::vector也是如此），照抄过来不容易错。
坑 2：无符号下标减 1。
❌buf_[(tail_ - 1) % buf_.size()]——tail_ == 0时tail_ - 1下溢成SIZE_MAX。
✅buf_[(tail_ + buf_.size() - 1) % buf_.size()]，先加后减。
坑 3：std::queue的pop()以为返回值。
❌int v = q.pop();——std::queue::pop()返回void，这是编译错误。
✅
int v = q.front(); q.pop();坑 4：在空队列上调用front()/back()。
❌std::queue::front()在空队列上是 UB，标准不保证任何行为（不是抛异常）。
✅ 先if (!q.empty())。自定义的循环队列则可以在front()里抛std::out_of_range，把 UB 变成可捕获的错误。
坑 5：以为循环队列天然线程安全。
❌ 一个线程push、另一个线程pop，不加锁，认为"下标操作是原子的所以没问题"。
✅ 不加同步的生产者-消费者循环队列需要仔细的内存序设计（std::atomic的 acquire/release 语义，或者std::memory_order_acquire/release配对）。朴素的std::size_t读写在这个场景下是数据竞争，是 UB。先用std::mutex把它们包起来是对的起点。
坑 6：把"满"当成异常往上抛。
❌ 在push里对满队列throw std::runtime_error("queue full")——在高频路径上抛异常代价高，而且让调用方必须写 try/catch 才能处理一个常规状况。
✅ 返回bool，或者用"覆盖最旧"的策略，把控制流交还给调用方。
坑 7：容量传 0。
❌CircularQueue<int> q(0);然后next()里做% 0——除零是 UB（整数除零在多数平台上直接触发硬件异常）。
✅ 构造函数里检查capacity == 0并抛std::invalid_argument；或者规定容量最小为 1。
坑 8：以为可以用std::queue的底层容器换成固定数组来得到循环队列。
❌std::queue<int, std::array<int, 8>> q;——std::array没有push_back/pop_front，编译不过。
✅std::queue的底层容器必须满足序列容器的要求（有back、push_back、pop_front等），std::array不是。要固定容量且不分配，就得自己写环形缓冲，或者用第三方库的boost::circular_buffer（那是 Boost，不是标准库）。
总结
| 要点 | 结论 |
|---|---|
| 判空判满 | 三种方案：浪费一个槽、计数器、标志位。计数器最易懂，容量也不浪费 |
next的写法 | i + 1 == N ? 0 : i + 1，比取模少一条除法，且天然无溢出 |
| 下标减法 | 无符号下标的减法必须"先加后减"，否则下溢 |
| 满队列的语义 | 返回bool或覆盖最旧，别抛异常；决策权交给调用方 |
与std::queue的分工 | 要"无限增长、写得省事"用std::queue；要"容量固定、零分配、严格 O(1)"用循环队列 |
| 线程安全 | 朴素实现不是线程安全的，并发访问是数据竞争（UB）；用锁或std::atomic明确内存序 |
循环队列本身的算法只值二十行代码，真正花时间的是那些边界：无符号下溢、容量为零、满队列的策略选择、以及"到底哪个下标指向有效元素"这个必须写进注释的约定。把不变式（count_恒等于有效元素个数，tail_恒指下一个可写位置）写在类的注释里，后面加接口（比如"满时覆盖"的变体）时就不容易把三条不变式拆散。
