0

0

C++如何实现简单的环形队列容器_C++固定大小缓冲区逻辑实现【数据结构】

穿越時空

穿越時空

发布时间:2026-02-11 14:10:03

|

513人浏览过

|

来源于php中文网

原创

应手写环形队列而非std::queue,因其内存连续、容量可控、零拷贝且适合高性能场景;实现时需用模运算回绕索引,牺牲一个槽位区分空满,并推荐std::array与noexcept优化。

c++如何实现简单的环形队列容器_c++固定大小缓冲区逻辑实现【数据结构】

为什么不用 std::queue 而要手写环形队列

因为 std::queue 底层默认用 std::deque,内存不连续,且无法限制最大容量;而环形队列能严格控大小、零拷贝复用内存、适合嵌入式或高性能场景(如音频缓冲、日志暂存)。关键在于:它靠两个索引(headtail)在固定数组上“绕圈”,不是真的移动数据。

如何用数组实现带容量限制的环形队列

核心是模运算控制索引回绕,同时必须区分“空”和“满”状态——不能只靠 head == tail 判断,否则无法分辨。常见做法是**牺牲一个槽位**,即容量为 N 的数组,最多存 N-1 个元素。

  • size() = (tail - head + capacity) % capacity
  • 入队前检查:if (size() == capacity - 1) → 满
  • 出队前检查:if (head == tail) → 空
  • push() 后: tail = (tail + 1) % capacity
  • pop() 后: head = (head + 1) % capacity

示例片段:

template 
class RingBuffer {
    T buf[N];
    size_t head = 0, tail = 0;
public:
    bool push(const T& v) {
        if ((tail + 1) % N == head) return false; // 满
        buf[tail] = v;
        tail = (tail + 1) % N;
        return true;
    }
    bool pop(T& out) {
        if (head == tail) return false; // 空
        out = buf[head];
        head = (head + 1) % N;
        return true;
    }
};

使用 std::array 还是裸数组?要不要加 noexcept

std::array 更安全(自带边界检查调试版、明确所有权),但注意它不提供运行时大小,和环形逻辑不冲突;裸数组更轻量,适合对二进制体积敏感的场景。所有成员函数建议加 noexcept——环形队列操作全是算术+赋值,无异常路径,显式标注有助于编译器优化和调用方判断。

Flowith
Flowith

一款GPT4驱动的节点式 AI 创作工具

下载

立即学习C++免费学习笔记(深入)”;

  • 若元素类型 T 的构造/赋值可能抛异常(比如含 std::string 成员),push() 就不能无条件 noexcept
  • 避免在 pop() 中返回 T 值(引发额外拷贝),应传引用输出参数或用 std::optional(C++17+)
  • 不要用 memset 清零整个 buf——非 POD 类型会破坏对象生命周期

线程安全怎么加?别直接套锁

环形队列常用于生产者-消费者模型,但简单加 std::mutex 会严重拖慢性能。更合理的方式是:单生产者 + 单消费者场景下,用原子变量(std::atomic_size_t)管理 head/tail,配合 memory_order_acquire/release;多对多则需细粒度锁(如双锁队列)或改用无锁结构(如 Michael-Scott 队列),但复杂度陡增。

最容易被忽略的是:**读写索引必须用原子操作,且每次访问都要用 .load().store(),不能缓存在普通局部变量里**——否则编译器或 CPU 可能重排或缓存旧值,导致判断错误。

热门AI工具

更多
DeepSeek
DeepSeek

幻方量化公司旗下的开源大模型平台

豆包大模型
豆包大模型

字节跳动自主研发的一系列大型语言模型

通义千问
通义千问

阿里巴巴推出的全能AI助手

腾讯元宝
腾讯元宝

腾讯混元平台推出的AI助手

文心一言
文心一言

文心一言是百度开发的AI聊天机器人,通过对话可以生成各种形式的内容。

讯飞写作
讯飞写作

基于讯飞星火大模型的AI写作工具,可以快速生成新闻稿件、品宣文案、工作总结、心得体会等各种文文稿

即梦AI
即梦AI

一站式AI创作平台,免费AI图片和视频生成。

ChatGPT
ChatGPT

最最强大的AI聊天机器人程序,ChatGPT不单是聊天机器人,还能进行撰写邮件、视频脚本、文案、翻译、代码等任务。

相关专题

更多
string转int
string转int

在编程中,我们经常会遇到需要将字符串(str)转换为整数(int)的情况。这可能是因为我们需要对字符串进行数值计算,或者需要将用户输入的字符串转换为整数进行处理。php中文网给大家带来了相关的教程以及文章,欢迎大家前来学习阅读。

688

2023.08.02

if什么意思
if什么意思

if的意思是“如果”的条件。它是一个用于引导条件语句的关键词,用于根据特定条件的真假情况来执行不同的代码块。本专题提供if什么意思的相关文章,供大家免费阅读。

803

2023.08.22

treenode的用法
treenode的用法

​在计算机编程领域,TreeNode是一种常见的数据结构,通常用于构建树形结构。在不同的编程语言中,TreeNode可能有不同的实现方式和用法,通常用于表示树的节点信息。更多关于treenode相关问题详情请看本专题下面的文章。php中文网欢迎大家前来学习。

540

2023.12.01

C++ 高效算法与数据结构
C++ 高效算法与数据结构

本专题讲解 C++ 中常用算法与数据结构的实现与优化,涵盖排序算法(快速排序、归并排序)、查找算法、图算法、动态规划、贪心算法等,并结合实际案例分析如何选择最优算法来提高程序效率。通过深入理解数据结构(链表、树、堆、哈希表等),帮助开发者提升 在复杂应用中的算法设计与性能优化能力。

26

2025.12.22

深入理解算法:高效算法与数据结构专题
深入理解算法:高效算法与数据结构专题

本专题专注于算法与数据结构的核心概念,适合想深入理解并提升编程能力的开发者。专题内容包括常见数据结构的实现与应用,如数组、链表、栈、队列、哈希表、树、图等;以及高效的排序算法、搜索算法、动态规划等经典算法。通过详细的讲解与复杂度分析,帮助开发者不仅能熟练运用这些基础知识,还能在实际编程中优化性能,提高代码的执行效率。本专题适合准备面试的开发者,也适合希望提高算法思维的编程爱好者。

37

2026.01.06

treenode的用法
treenode的用法

​在计算机编程领域,TreeNode是一种常见的数据结构,通常用于构建树形结构。在不同的编程语言中,TreeNode可能有不同的实现方式和用法,通常用于表示树的节点信息。更多关于treenode相关问题详情请看本专题下面的文章。php中文网欢迎大家前来学习。

540

2023.12.01

C++ 高效算法与数据结构
C++ 高效算法与数据结构

本专题讲解 C++ 中常用算法与数据结构的实现与优化,涵盖排序算法(快速排序、归并排序)、查找算法、图算法、动态规划、贪心算法等,并结合实际案例分析如何选择最优算法来提高程序效率。通过深入理解数据结构(链表、树、堆、哈希表等),帮助开发者提升 在复杂应用中的算法设计与性能优化能力。

26

2025.12.22

深入理解算法:高效算法与数据结构专题
深入理解算法:高效算法与数据结构专题

本专题专注于算法与数据结构的核心概念,适合想深入理解并提升编程能力的开发者。专题内容包括常见数据结构的实现与应用,如数组、链表、栈、队列、哈希表、树、图等;以及高效的排序算法、搜索算法、动态规划等经典算法。通过详细的讲解与复杂度分析,帮助开发者不仅能熟练运用这些基础知识,还能在实际编程中优化性能,提高代码的执行效率。本专题适合准备面试的开发者,也适合希望提高算法思维的编程爱好者。

37

2026.01.06

Rust异步编程与Tokio运行时实战
Rust异步编程与Tokio运行时实战

本专题聚焦 Rust 语言的异步编程模型,深入讲解 async/await 机制与 Tokio 运行时的核心原理。内容包括异步任务调度、Future 执行模型、并发安全、网络 IO 编程以及高并发场景下的性能优化。通过实战示例,帮助开发者使用 Rust 构建高性能、低延迟的后端服务与网络应用。

1

2026.02.11

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
C# 教程
C# 教程

共94课时 | 9.1万人学习

C 教程
C 教程

共75课时 | 4.6万人学习

C++教程
C++教程

共115课时 | 17万人学习

关于我们 免责申明 举报中心 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号 技术交流群
PHP中文网订阅号
每天精选资源文章推送

Copyright 2014-2026 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号