C++循环队列

前言循环队列circular queue也叫环形缓冲区 ring buffer是数据结构课上必讲的一个结构用一个固定大小的数组当队列front和tail走到数组末尾就绕回开头从而复用被pop释放出来的空间。标题把它写成C 循环队列需要先说清一件事循环队列不是 C 标准库里的组件。标准库提供的队列是queue里的std::queue它是一个容器适配器container adapter底层默认用std::deque实现它的扩容行为是动态增长不是循环复用固定数组。这两个东西的取舍是std::queue写起来最省事、能无限增长循环队列容量固定、内存不增长、没有动态分配适合嵌入式、音视频缓冲、生产者-消费者这类缓冲区大小必须可控的场景。本文讲三件事循环队列的判空判满有哪几种做法、C 里怎么写出一个正确可编译的版本、以及它和std::queue、std::deque的边界在哪。代码以 C17 为基准。一、循环队列的核心怎么区分空和满用数组实现队列front指向队头元素tail指向队尾元素的下一个位置或者队尾元素本身两种约定都有人用。入队时写buf[tail]然后tail (tail 1) % capacity。问题来了队列空的时候front tail队列满的时候如果元素占满了整个数组front也会等于tail。同一个条件对应两种状态没法区分。业界有三种解决办法方案判空判满可用容量说明浪费一个槽位front tail(tail 1) % cap frontcap - 1实现最简单代价是永远少存一个元素维护计数器count 0count capcap空间全用上每次操作多维护一个变量加一个标志位front tail !fullfront tail fullcap省空间但每个分支都要记得同步标志容易忘本文选计数器方案它的不变式invariant最容易验证——count就是元素个数判空判满都是直接看它没有少用一个格子的心理负担也不像标志位那样容易忘记更新。二、用 std::vector 做底的模板实现// C17单文件g -stdc17 -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::vectorT buf_; std::size_t head_; // 队头元素下标 std::size_t tail_; // 下一个可写位置等价于队尾元素下标 1 std::size_t count_; // 当前元素个数 }; int main() { CircularQueueint 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() - 1i 1最多等于buf_.size()不会溢出而如果换成一个接近SIZE_MAX的下标(i 1) % N里的i 1就可能回绕。在这个类里i永不超过buf_.size()所以两种写法都安全。push返回bool而不是抛异常。队列满是一个预期内的正常状况不是异常情况。返回bool把决策权交给调用方视频流可以丢弃旧的帧网络协议栈可以让发送方重试实时系统可以计数丢弃率。这也和标准库的std::queue::push不同——后者永远成功底层容器会扩容。push(T)与push(const T)两个重载。这是 C11 之后写容器的标准做法右值走移动左值走拷贝。注意buf_[tail_] std::move(value)要求T可移动赋值对只有拷贝的类型std::move会退回到拷贝不会编译失败前提是拷贝赋值存在。back()里的(tail_ buf_.size() - 1) % buf_.size()。不能写成(tail_ - 1) % sizetail_是无符号的std::size_t当tail_ 0时tail_ - 1会下溢成SIZE_MAXSIZE_MAX % 4得到的不是 3。先加size再减 1 就不会下溢。无符号下溢本身不是 UB标准规定按 2 的幂取模但结果完全不是你要的。三、和 std::queue 的对比std::queue是容器适配器声明形式以标准为准是templateclass T, class Container std::dequeT class queue。它的接口是成员函数语义push(const T)/push(T)在队尾追加emplace(args...)在队尾原地构造pop()移除队头元素返回 void不返回被移除的值front()/back()访问队头 / 队尾元素引用空队列上调用是 UBempty()/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_。四、要不要满时覆盖的变体环形缓冲在音视频和日志场景里常见的变体是满了就覆盖最旧的// C17 // 满时覆盖最旧元素永远不失败 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()]先加后减。坑 3std::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。❌CircularQueueint q(0);然后next()里做% 0——除零是 UB整数除零在多数平台上直接触发硬件异常。✅ 构造函数里检查capacity 0并抛std::invalid_argument或者规定容量最小为 1。坑 8以为可以用std::queue的底层容器换成固定数组来得到循环队列。❌std::queueint, std::arrayint, 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_恒指下一个可写位置写在类的注释里后面加接口比如满时覆盖的变体时就不容易把三条不变式拆散。