数据结构与算法学习笔记九---循环队列的表示和实现(C++)
目录
前言
1.为什么要使用循环队列
2.队列的顺序存储方式的实现
1.定义
2.队列初始化
3.销毁
4.清空队列
5.队列是否为空
6.队列长度
7.队头
8.入队
9.出队
10.遍历队列
11.完整代码
3.参考资料
前言
这篇文章介绍循环队列的表示和用法。
1.为什么要使用循环队列
在上一篇文章中,我们知道了顺序的循环表示和实现方法。但是我们会发现当我们在操作顺序链表的时候,我们频繁的操作顺序队列,而队列又不为空的时候,出队列的一些存储空间会变得不可用。
如下图所示,当我rear=3,front=2的时候,顺序队列中至少有连个存储空间空间是不可以使用的,这无疑会浪费一些存储空间。那么有没有办法让我们在出队列之后,重复利用之前存储空间呢,答案是有的。

图1.顺序队列的出队列和入队列操作示意图
这里借鉴了网上老师的三种解决方案:
1.使用计数器记录队列中的元素个数
2.加标志位,删除的时候标志位置1,插入置0,当front = rear并且标志位为0,表示队列为空,当front=rear并且标志位为1的时候,表示队列经满。
3.认为浪费一个存储空间,改成一个循环队列来实现。
这里下面代码的表示和实现采用的第三种方案。
关于循环队列的理解,感觉严蔚敏老师的讲解还是不错的,直接贴个图吧。

图2.严蔚敏老师数据结构与算法中关于循环队列的思路
2.队列的顺序存储方式的实现
1.定义
struct CircularQueue {int *base;int front;int rear;int maxSize; // 队列的最大容量
};
2.队列初始化
// 队列初始化
Status initQueue(CircularQueue &circularQueue, int maxSize) {circularQueue.base = new int[maxSize]; // 为循环队列分配内存if (!circularQueue.base) {return 0; // 内存分配失败}circularQueue.front = circularQueue.rear = 0; // 初始化队首和队尾指针circularQueue.maxSize = maxSize;return 1; // 初始化成功
}
3.销毁
// 销毁队列
void destroyQueue(CircularQueue &circularQueue) {if (circularQueue.base) {delete[] circularQueue.base; // 释放内存circularQueue.base = nullptr; // 将指针置为空}
}
4.清空队列
// 清空队列
void clearQueue(CircularQueue &circularQueue) {circularQueue.front = circularQueue.rear = 0; // 重置队首和队尾指针
}
5.队列是否为空
// 判断队列是否为空
bool isEmptyQueue(CircularQueue &circularQueue) {return circularQueue.front == circularQueue.rear; // 当队首和队尾指针相同时,队列为空
}
6.队列长度
// 获取队列长度
int queueLength(CircularQueue &circularQueue) {return (circularQueue.rear - circularQueue.front + circularQueue.maxSize) % circularQueue.maxSize;
}
7.队头
// 获取队首元素
Status getQueueFront(CircularQueue &circularQueue, int &frontElement) {if (isEmptyQueue(circularQueue)) {return 0; // 队列为空}frontElement = circularQueue.base[circularQueue.front];return 1; // 成功获取队首元素
}
8.入队
// 入队
bool enQueue(CircularQueue &circularQueue, int element) {// 检查队列是否已满if ((circularQueue.rear + 1) % circularQueue.maxSize == circularQueue.front) {return false; // 队列已满}// 入队操作circularQueue.base[circularQueue.rear] = element;circularQueue.rear = (circularQueue.rear + 1) % circularQueue.maxSize; // 移动队尾指针return true; // 入队成功
}
9.出队
// 出队
bool deQueue(CircularQueue &circularQueue, int &element) {// 检查队列是否为空if (isEmptyQueue(circularQueue)) {return false; // 队列为空,无法出队}// 出队操作element = circularQueue.base[circularQueue.front];circularQueue.front = (circularQueue.front + 1) % circularQueue.maxSize; // 移动队首指针return true; // 出队成功
}
10.遍历队列
// 遍历队列
void traverseQueue(CircularQueue &circularQueue) {// 遍历队列并打印元素int i = circularQueue.front;while (i != circularQueue.rear) {cout << circularQueue.base[i] << " ";i = (i + 1) % circularQueue.maxSize;}cout << endl;
}
11.完整代码
#include <iostream>
using namespace std;typedef int Status;struct CircularQueue {int *base;int front;int rear;int maxSize; // 队列的最大容量
};// 队列初始化
Status initQueue(CircularQueue &circularQueue, int maxSize) {circularQueue.base = new int[maxSize]; // 为循环队列分配内存if (!circularQueue.base) {return 0; // 内存分配失败}circularQueue.front = circularQueue.rear = 0; // 初始化队首和队尾指针circularQueue.maxSize = maxSize;return 1; // 初始化成功
}// 销毁队列
void destroyQueue(CircularQueue &circularQueue) {if (circularQueue.base) {delete[] circularQueue.base; // 释放内存circularQueue.base = nullptr; // 将指针置为空}
}// 清空队列
void clearQueue(CircularQueue &circularQueue) {circularQueue.front = circularQueue.rear = 0; // 重置队首和队尾指针
}// 判断队列是否为空
bool isEmptyQueue(CircularQueue &circularQueue) {return circularQueue.front == circularQueue.rear; // 当队首和队尾指针相同时,队列为空
}// 获取队列长度
int queueLength(CircularQueue &circularQueue) {return (circularQueue.rear - circularQueue.front + circularQueue.maxSize) % circularQueue.maxSize;
}// 获取队首元素
Status getQueueFront(CircularQueue &circularQueue, int &frontElement) {if (isEmptyQueue(circularQueue)) {return 0; // 队列为空}frontElement = circularQueue.base[circularQueue.front];return 1; // 成功获取队首元素
}// 入队
bool enQueue(CircularQueue &circularQueue, int element) {// 检查队列是否已满if ((circularQueue.rear + 1) % circularQueue.maxSize == circularQueue.front) {return false; // 队列已满}// 入队操作circularQueue.base[circularQueue.rear] = element;circularQueue.rear = (circularQueue.rear + 1) % circularQueue.maxSize; // 移动队尾指针return true; // 入队成功
}// 出队
bool deQueue(CircularQueue &circularQueue, int &element) {// 检查队列是否为空if (isEmptyQueue(circularQueue)) {return false; // 队列为空,无法出队}// 出队操作element = circularQueue.base[circularQueue.front];circularQueue.front = (circularQueue.front + 1) % circularQueue.maxSize; // 移动队首指针return true; // 出队成功
}// 遍历队列
void traverseQueue(CircularQueue &circularQueue) {// 遍历队列并打印元素int i = circularQueue.front;while (i != circularQueue.rear) {cout << circularQueue.base[i] << " ";i = (i + 1) % circularQueue.maxSize;}cout << endl;
}int main() {CircularQueue circularQueue;int maxSize = 10; // 队列的最大容量initQueue(circularQueue, maxSize); // 初始化循环队列// 测试入队for (int i = 1; i <= 5; ++i) {enQueue(circularQueue, i * 10);}// 输出队列元素cout << "队列元素:";traverseQueue(circularQueue);// 获取队首元素int frontElement;if (getQueueFront(circularQueue, frontElement)) {cout << "队首元素:" << frontElement << endl;}// 测试出队int element;for (int i = 0; i < 3; ++i) {if (deQueue(circularQueue, element)) {cout << "出队元素:" << element << endl;}}// 输出队列元素cout << "队列元素:";traverseQueue(circularQueue);// 判断队列是否为空if (isEmptyQueue(circularQueue)) {cout << "队列为空" << endl;} else {cout << "队列不为空" << endl;}// 获取队列长度cout << "队列长度:" << queueLength(circularQueue) << endl;// 清空队列clearQueue(circularQueue);// 判断清空后队列是否为空if (isEmptyQueue(circularQueue)) {cout << "清空队列后,队列为空" << endl;} else {cout << "清空队列后,队列不为空" << endl;}// 销毁队列destroyQueue(circularQueue);return 0;
}
3.参考资料
1.B站上看到的一个老师的讲解
2.数据结构C语言版(1997年清华大学出版社出版的图书)_百度百科
相关文章:
数据结构与算法学习笔记九---循环队列的表示和实现(C++)
目录 前言 1.为什么要使用循环队列 2.队列的顺序存储方式的实现 1.定义 2.队列初始化 3.销毁 4.清空队列 5.队列是否为空 6.队列长度 7.队头 8.入队 9.出队 10.遍历队列 11.完整代码 3.参考资料 前言 这篇文章介绍循环队列的表示和用法。 1.为什么要使用循环队…...
Mysql获取当前时间
1、今天开始时间和结束时间 SELECT DATE_FORMAT(NOW(),’%Y-%m-%d 00:00:00’) AS ‘今天开始’; SELECT DATE_FORMAT(NOW(),’%Y-%m-%d 23:59:59’) AS ‘今天结束’;2、昨天的开始时间和结束时间 SELECT DATE_FORMAT( DATE_SUB(CURDATE(), INTERVAL 1 DAY), ‘%Y-%m-%d 00:…...
计算机服务器中了locked勒索病毒怎么解决,locked勒索病毒解密恢复工具
在网络技术飞速发展的时代,通过网络开展各项工作业务成为众多企业的首选,网络也为企业的生产运营提供了极大便利,大大提升了企业办公效率,但是利用网络避免不了网络威胁的存在,数据安全问题一直是企业关心的主要话题。…...
基于springboot实现的在线动漫信息平台
开发语言:Java 框架:springboot JDK版本:JDK1.8 服务器:tomcat7 数据库:mysql 5.7(一定要5.7版本) 数据库工具:Navicat11 开发软件:eclipse/myeclipse/idea Maven…...
C# Winform+Halcon结合标准视觉工具
介绍 winform与halcon结合标准化工具实例 软件架构 软件架构说明 基于NET6 WINFORMHALCON 实现标准化视觉检测工具 集成相机通讯 集成PLC通讯 TCP等常见通讯 支持常见halcon算子 图形采集blob分析高精度匹配颜色提取找几何体二维码提取OCR识别等等 。。。 安装教程 …...
英语单词量测试
网址:https://preply.com/en/learn/english/test-your-vocab 测试结果: 细节:英语母语者有20000-35000个单词的词汇量,8岁孩子的词汇量在8000个左右。而不是我们教育系统里说的,6000个单词足够用了。足够用࿰…...
三、安装node_exporter
目录 一、简介 二、下载安装 一、简介 Exporter是Prometheus的指标数据收集组件。它负责从目标Jobs收集数据,并把收集到的数据转换为Prometheus支持的时序数据格式。 和传统的指标数据收集组件不同的是,他只负责收集,并不向Server端发送数据…...
kafka基础知识
kafka架构 producer -> kafka cluster(broker>topic>partition) -> consumer -> zookeeper kafka压测 kafka-producer-perf-test.sh kafka-consumer-perf-test.sh kafka日志保存位置及消息保存时间 /tpdata/client/Kafka/kafka/config/server.properties log.…...
华为昇腾310B1平台视频解码失败[ERROR] Send frame to vdec failed, errorno:507018
目录 1 [ERROR] Send frame to vdec failed, errorno:507018 2 bug解决尝试1 3 bug解决尝试2 4 最终解决方法 参考文献: 1 [ERROR] Send frame to vdec failed, errorno:507018 某项目中的代码运行报错 [ERROR] Send frame to vdec failed, errorno:507018 Ac…...
Flutter 中的 SwitchListTile 小部件:全面指南
Flutter 中的 SwitchListTile 小部件:全面指南 在Flutter的Material组件库中,SwitchListTile是一个包含开关(Switch)的列表项,非常适合用来创建带有标题、副标题以及开关的列表项,常用于设置界面ÿ…...
详细分析Vue3中的defineExpose(附Demo)
目录 前言1. 基本知识2. Demo3. 实战 前言 其基本知识可参考官网:Vue3中的defineExpose 1. 基本知识 defineExpose 是 Vue 3 的 Composition API 中一个新的实用函数,用于在 <script setup> 语法下显式暴露组件的公共属性和方法 这在处理子组件…...
合合信息:TextIn文档解析技术与高精度文本向量化模型再加速
文章目录 前言现有大模型文档解析问题表格无法解析无法按照阅读顺序解析文档编码错误 诉求文档解析技术技术难点技术架构关键技术回根溯源 文本向量化模型结语 前言 随着人工智能技术的持续演进,大语言模型在我们日常生活中正逐渐占据举足轻重的地位。大模型语言通…...
Git与Gitlab
第1章Git概述 Git是一个免费的、开源的分布式版本控制系统,可以快速高效地处理从小型到大型的各种项目。 代码托管中心,记录每个版本的代码,从项目创建到现在使用的代码,中间所有的修改都有记录。 1. 何为版本控制 版本控制是…...
MySQL数据库从入门到精通(下)
对表做了修改之后,记得点击对应图标按钮重新执行一下。 1.创建角色表 数据库一开始就要设计好,轻易不要改动。一个账号下可能有多个角色,所以我们单独再创建另一个表role用来存储所有的角色信息。其中idrole表示角色id,name表示名…...
从融媒到智媒,小程序框架可助力传媒企业在AI实践下的服务变现
过去5年,媒体行业一直都在进行着信息化建设向融媒体平台建设的转变。一些融媒体的建设演变总结如下: 新闻终端的端侧内容矩阵建设,如App新闻端,社交平台上的官方媒体等 新闻本地生活双旗舰客户端,兼顾主流媒体核心宣传…...
MES系统在电线电缆行业生产上的应用
MES系统在线缆行业的应用可以带来多重价值,包括提高生产效率、降低生产成本、提高产品质量、优化库存管理、改善生产环境和提高企业竞争力等方面。因此,在电线电缆行业中广泛应用MES系统可以提高企业的经济效益和社会效益,推动企业发展和行业…...
怎么把图片上的字去掉
将图片上的字去掉通常需要使用图像编辑软件或在线工具。以下是一些常用的方法和步骤: 使用Adobe Photoshop: 打开Photoshop,导入需要编辑的图片。 选择“橡皮擦工具”或“克隆图章工具”。 如果使用“橡皮擦工具”,调整橡皮擦的…...
BFS和DFS优先搜索算法
1. BFS与DFS 1.1 BFS DFS即Depth First Search,深度优先搜索。它是一种图遍历算法,它从一个起始点开始,逐层扩展搜索范围,直到找到目标节点为止。 这种算法通常用于解决“最短路径”问题,比如在迷宫中找到从起点到终…...
python将两张图片对齐
目录 需要对齐的照片如下: 源码: 结果: 需要对齐的照片如下: 源码: import cv2 import numpy as np from matplotlib import pyplot as plt# 读取两张图片 imgA cv2.imread(./out/out/3.png) imgB cv2.imread(./…...
Linux修炼之路之初识操作系统+基础指令(1)
目录 引言 一:对操作系统(OS)的简单了解 1.操作系统(OS) 是什么 2.操作系统好坏的衡量标准 3.操作系统存在的重要性 4.理解所有在计算机上的操作 二:Linux与windows操作的特点区别 三:基础指令 1.ls 指令 1.使用 2.常用选项 2.…...
基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真
目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销,平衡网络负载,延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...
简易版抽奖活动的设计技术方案
1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...
ffmpeg(四):滤镜命令
FFmpeg 的滤镜命令是用于音视频处理中的强大工具,可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下: ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜: ffmpeg…...
爬虫基础学习day2
# 爬虫设计领域 工商:企查查、天眼查短视频:抖音、快手、西瓜 ---> 飞瓜电商:京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空:抓取所有航空公司价格 ---> 去哪儿自媒体:采集自媒体数据进…...
【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具
第2章 虚拟机性能监控,故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令:jps [options] [hostid] 功能:本地虚拟机进程显示进程ID(与ps相同),可同时显示主类&#x…...
聊一聊接口测试的意义有哪些?
目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开,首…...
Map相关知识
数据结构 二叉树 二叉树,顾名思义,每个节点最多有两个“叉”,也就是两个子节点,分别是左子 节点和右子节点。不过,二叉树并不要求每个节点都有两个子节点,有的节点只 有左子节点,有的节点只有…...
学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”
2025年#高考 将在近日拉开帷幕,#AI 监考一度冲上热搜。当AI深度融入高考,#时间同步 不再是辅助功能,而是决定AI监考系统成败的“生命线”。 AI亮相2025高考,40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕,江西、…...
#Uniapp篇:chrome调试unapp适配
chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器:Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...
音视频——I2S 协议详解
I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议,专门用于在数字音频设备之间传输数字音频数据。它由飞利浦(Philips)公司开发,以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...
