讲师中心 微信公众号
AI工具推荐 视频效率加速

C++实现环形队列CircularQueue _ 数组下标取模运算【源码】

梦墨酱_8972

梦墨酱_8972

发布时间:2026-04-11 13:35:03

|

260人浏览过

|

来源于php中文网

原创

环形队列中front/rear不能直接++因需模运算绕回,但负数取模可能为负,应使用(x%n+n)%n或条件判断;空满判据不能都用front==rear,须预留冗余位或引入size;new T[n]需手动析构避免泄漏;应使用unique_ptr和construct_at/destroy_at支持移动与异常安全。

c++实现环形队列circularqueue _ 数组下标取模运算【源码】

为什么环形队列的 front 和 rear 不能直接用 ++i 后自增?

因为环形本质是数组首尾相连,下标必须始终落在 [0, capacity) 范围内。直接自增会越界,必须靠取模运算“绕回”。但取模有陷阱:C++ 中负数取模结果可能为负(如 -1 % 5 == -1),而数组下标不能为负。所以不能写 front = (front - 1) % capacity 这类表达式。

实操建议:

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

  • 统一用 (x % n + n) % n 做安全取模,确保结果恒为非负
  • 更高效的做法是用条件判断替代取模:当 rear == capacity - 1 时置 0,否则 ++rear;但会增加分支,对高频操作有微小性能影响
  • 推荐封装成内联辅助函数:inline int mod(int x, int n) { return (x % n + n) % n; }

isFull() 和 isEmpty() 的判据为什么不能都用 front == rear?

这是环形队列最易错的设计点。单靠 front == rear 无法区分空和满——两者状态完全一致。必须预留一个“冗余槽位”或引入额外字段(如计数器 size)来打破歧义。

实操建议:

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

  • 主流做法是牺牲一个元素空间:队列最大有效容量为 capacity - 1,用 (rear + 1) % capacity == front 判满,用 front == rear 判空
  • 若坚持物理满容(即 capacity 个元素),必须加 size 成员变量,此时 isFull() 直接返回 size == capacity,isEmpty() 返回 size == 0
  • 前者节省内存、逻辑简洁;后者避免容量浪费,但多一次内存访问(读 size)

构造函数里用 new T[capacity] 分配元素,为什么必须配合 std::destroy 或手动析构?

因为 new T[n] 会调用 T 的默认构造函数初始化每个元素,而环形队列实际只在入队时才真正使用某位置的元素。如果用户类型 T 构造开销大(如含 std::string 或动态分配),提前全量构造就是浪费;更严重的是,出队后该位置对象仍处于“已构造未析构”状态,再次入队前若不显式析构,会造成资源泄漏或未定义行为。

C++ 算法竞赛自动化测试数据生成与校验框架
C++ 算法竞赛自动化测试数据生成与校验框架

根据原题生成新题面、验证器及完整测试数据,自动套用 testlib 模板,用于用户要求生成测试数据时。

下载

实操建议:

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

  • 改用 std::allocator<t></t> + allocate()/construct()/destroy() 手动控制生命周期
  • 或者用 std::vector<:byte></:byte> 配合 std::construct_at 和 std::destroy_at(C++20)
  • 简单起见,也可要求 T 必须是 trivially destructible,跳过析构步骤——但需文档明确标注限制

如何让 CircularQueue 支持移动语义和异常安全?

默认生成的拷贝/移动函数对原始指针或未管理内存会失效。若内部用裸指针存数组,移动后原对象仍持有已转移的资源,析构时双重释放。

实操建议:

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

  • 用 std::unique_ptr<t></t> 管理底层数组,移动构造函数自动获得强异常安全保证
  • 入队时用 std::construct_at(&data[rear], std::move(value)),避免不必要的拷贝
  • 出队时先 std::destroy_at(&data[front]) 再更新 front,确保异常发生时对象状态一致
  • 所有修改状态的操作(如 push())应在完成资源变更后再更新索引,防止中途异常导致索引错位

多数人卡在取模符号和空满判据上,这两个点一旦写错,调试时现象极其隐蔽:队列看似正常工作,但在边界容量下突然丢数据或死锁。动手前先手算三组 capacity=3 的推演(空→push×3→pop×2→push),比看十遍源码更管用。

热门AI工具

更多
VibeKnow
VibeKnow Hot

一款AI视频创作工具,主要用于全球首个AI知识视频创作平台,文档、文章、网页,一键生成视频,适合需要提升相关任务效率的用户。

WorkBuddy

一款AI办公效率工具,主要用于腾讯云推出的AI原生桌面智能体工作台,适合需要提升相关任务效率的用户。

LibLibAI
LibLibAI Hot

一款AI视频创作工具,主要用于国内领先的AI创意平台,以海量模型、低门槛操作与“创作-分享-商业化”生态,让小白与专业创作者都能高效实现图文乃至视频创意表达,适合需要提升相关任务效率的用户。

豆包大模型

豆包大模型是一款由字节跳动推出的企业级大语言模型服务平台。

蛙蛙写作

一款AI论文写作工具,主要用于超级AI智能写作助手,适合需要提升相关任务效率的用户。

墨刀AI
墨刀AI Hot

一款AI图像与设计工具,主要用于产品经理的专属智能体,适合需要提升相关任务效率的用户。

DeepSeek

DeepSeek是一款面向对话、写作、编程和推理场景的AI大模型工具。

音述AI
音述AI Hot

一款AI音频处理工具,主要用于音述AI是一个以“用声音述说故事”为核心的 AI 音乐创作与声音分享社区,适合需要提升相关任务效率的用户。

超级简历WonderCV

一款AI办公效率工具,主要用于免费求职简历模版下载制作,应届生职场人必备简历制作神器,适合需要提升相关任务效率的用户。

相关专题

更多
string转int
string转int

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

5419

2023.08.02

string转int
string转int

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

5419

2023.08.02

int占多少字节
int占多少字节

int占4个字节,意味着一个int变量可以存储范围在-2,147,483,648到2,147,483,647之间的整数值,在某些情况下也可能是2个字节或8个字节,int是一种常用的数据类型,用于表示整数,需要根据具体情况选择合适的数据类型,以确保程序的正确性和性能。本专题为大家提供相关的文章、下载、课程内容,供大家免费下载体验。

2745

2024.08.29

c++怎么把double转成int
c++怎么把double转成int

本专题整合了 c++ double相关教程,阅读专题下面的文章了解更多详细内容。

3388

2025.08.29

C++中int的含义
C++中int的含义

本专题整合了C++中int相关内容,阅读专题下面的文章了解更多详细内容。

2425

2025.08.29

C++ 智能指针与现代内存管理
C++ 智能指针与现代内存管理

深入讲解 C++ 现代内存管理的核心工具——智能指针,涵盖 unique_ptr 独占所有权语义、shared_ptr 引用计数机制与循环引用问题、weak_ptr 弱引用的应用场景、make_unique/make_shared 工厂函数的性能优势、自定义删除器的编写、RAII 资源管理思想的实践,以及从裸指针迁移到智能指针的重构策略,帮助开发者编写安全无泄漏的现代 C++ 代码。

319

2026.04.23

PDF转图片方法
PDF转图片方法

需要把 PDF 页面用于上传、预览、分享或图片归档时,PDF 转图片方法专题整理 JPG/PNG 格式选择、逐页导出、清晰度设置、批量下载和结果检查等流程,帮助用户稳定完成 PDF 图片化处理。

0

2026.09.30

PixTV AI视频生成与无限画布创作
PixTV AI视频生成与无限画布创作

PixTV专题整理AI视频与视觉内容创作相关功能使用教程,涵盖AI生图、视频生成、无限画布、多模型创作、素材管理、声音音乐及视频剪辑等功能,帮助用户快速掌握PixTV从创意到成片的完整制作方法。

0

2026.09.29

Buffalo框架数据库开发全教程
Buffalo框架数据库开发全教程

本专题围绕Buffalo框架数据库开发,讲解database.yml多环境配置、soda与fizz迁移生成回滚、模型结构体标签、增删改查与条件查询、一对多与多对多关联、数据校验、回调钩子、事务处理及原生SQL执行能力。

200

2026.09.23

热门下载

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

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
Conan 2 Essentials 免费课程
Conan 2 Essentials 免费课程

共0课时 | 0人学习

CMake 与 Conan 集成实践
CMake 与 Conan 集成实践

共0课时 | 0人学习

Conan 2 高级依赖模型介绍
Conan 2 高级依赖模型介绍

共0课时 | 0人学习

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

Copyright 2014-2026 https://www.php.cn/ All Rights Reserved | php.cn