【数据结构】循环队列
🦄个人主页:修修修也
🎏所属专栏:数据结构
⚙️操作环境:Visual Studio 2022
目录
🎏队列顺序存储的不足
🎏循环队列的定义
🎏设计循环队列
结语
🎏队列顺序存储的不足
我们假设用一个可以存放为n个数据的数组arr来实现队列:
很容易可以知道:给arr中入队时时间复杂度为O(1),而出队时时间复杂度却是O(n).
按照传统方式每次出队时都要将所有元素向前挪动是非常麻烦的,我们不如在出队时让头指针也动起来,即在出队时不移动后面的元素,而是让front向后移动,指向新的队头元素:
这样出队和入队的时间复杂度都是O(1)了,但是使用这种方式,当我们入队又出队后会造成"假溢出"问题:
即数组前面有空着的空间,但因为队列入队要追加在队伍的末尾,因此只能追加在下图中9的后面,但9后面没有空间了,这时就会造成"假溢出"问题.
你想想,如果你今天去教室上课,因为是水课,后面3排都坐满了人,而前排还有很多空位,你会怎么做?直接走出教室,并告诉自己后面没有座位可坐了?
现实生活中我们不会那样做的,前面有座位,我们当然是可以坐的,除非真的满了,那才需要考虑向老师申请一个大教室.
🎏循环队列的定义
因此,解决假溢出的办法就是后面满了,就从头再开始,也即头尾相接的循环.
我们把队列的这种头尾相接的顺序存储结构称为循环队列.
在刚才的例子中,我们可以改变rear指向下标为0的位置,这样就可以继续入队元素了:
当我们继续一直入队元素,rear一直向后移动,直到将数组入满,此时rear和front重合,同时指向下标为5的位置,如图:
此时我们需要思考几个问题,我们刚才说,空队列时,front等于rear,而现在队列满时,也是front等于rear,那么该如何判断此时的队列究竟是空还是满?
- 办法一是设置一个标志flag,当front==rear,且flag=0时为队列空,当front==rear,且flag=1时为队列满.
- 办法二是当队列空时,条件是front=rear,当队列满时,我们修改其条件,保留一个元素空间.也就是说,当数组中只剩一个空闲单元时,我们就认为队列满了,如下图所示:
由于rear可能比front大,也可能比front小,所以尽管它们只相差一个位置时就是满的情况,但也可能是相差整整一圈.
所以若队列的最大尺寸为QueueSize,那么队列满的条件是(rear+1)%QueueSize==front
(这里的取模"%"的目的就是为了解决rear可能会比front大一圈的问题).
队列的长度计算也要特别注意,通用的计算队列长度公式为:
(rear-front+QueueSize)%QueueSize
有了以上关于循环队列的知识储备,我们接下来实战实现一个循环队列.
🎏设计循环队列
题目链接
622. 设计循环队列
https://leetcode.cn/problems/design-circular-queue/
题目描述
设计你的循环队列实现。 循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里,一旦一个队列满了,我们就不能插入下一个元素,即使在队列前面仍有空间。但是使用循环队列,我们能使用这些空间去存储新的值。
你的实现应该支持如下操作:
MyCircularQueue(k)
: 构造器,设置队列长度为 k 。Front
: 从队首获取元素。如果队列为空,返回 -1 。Rear
: 获取队尾元素。如果队列为空,返回 -1 。enQueue(value)
: 向循环队列插入一个元素。如果成功插入则返回真。deQueue()
: 从循环队列中删除一个元素。如果成功删除则返回真。isEmpty()
: 检查循环队列是否为空。isFull()
: 检查循环队列是否已满。
题目详情
解题思路
循环队列的设计思路其实在文章前面的简介部分我们已经阐述过了,但在具体实现时,我们仍需注意以下几点:
- 注意题目要求的返回值,如入队/出队函数要求成功返回true,失败返回false.
- 注意队列判满的条件
- 注意rear,front在持续向后移动过程中,如果数值超过了合理的数组下标范围,,则需要想办法将其修正到合理的范围内.
解题代码
综上,解题代码如下:
typedef struct
{int *arr; //存数据int front; //头指针int rear; //尾指针int k; //存个数
} MyCircularQueue;bool myCircularQueueIsEmpty(MyCircularQueue* obj)//判空,为空返回true
{return (obj->front==obj->rear);
}bool myCircularQueueIsFull(MyCircularQueue* obj)//判满,为满返回true
{return ((obj->front)==((obj->rear+1)%(obj->k+1)));
}MyCircularQueue* myCircularQueueCreate(int k)
{MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));if(obj==NULL){perror("malloc fail::");return NULL;}obj->arr=(int*)malloc(sizeof(int)*(k+1));//留空一个,便于判断if(obj->arr==NULL){perror("malloc fail::");return NULL;}obj->front=obj->rear=0;obj->k=k;return obj;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) //入队
{//队满返回falseif(myCircularQueueIsFull(obj)){return false;}//队未满尾插else{obj->arr[obj->rear]=value;obj->rear++;obj->rear%=(obj->k+1);return true;}
}bool myCircularQueueDeQueue(MyCircularQueue* obj) //出队
{//队空返回falseif(myCircularQueueIsEmpty(obj)){return false;}else//队非空则头删{obj->front++;obj->front%=(obj->k+1);return true;}
}int myCircularQueueFront(MyCircularQueue* obj)//取队头
{if(myCircularQueueIsEmpty(obj))//为空则失败{return -1;}return obj->arr[obj->front];
}int myCircularQueueRear(MyCircularQueue* obj)//取队尾
{if(myCircularQueueIsEmpty(obj))//为空则失败{return -1;}return obj->arr[(obj->rear+obj->k)%(obj->k+1)];//如果rear=0,rear-1=-1会导致越界访问
}void myCircularQueueFree(MyCircularQueue* obj)//销毁,开几个销几个
{free(obj->arr);free(obj);
}
提交运行:
结语
希望这篇有关数据结构循环队列的文章能对您有所帮助,欢迎大佬们留言或私信与我交流.学海漫浩浩,我亦苦作舟!关注我,大家一起学习,一起进步!
相关文章推荐
【数据结构】什么是线性表?
【数据结构】线性表的链式存储结构
【数据结构】什么是栈?
【数据结构】用C语言实现顺序栈(附完整运行代码)
【数据结构】深入浅出理解链表中二级指针的应用
【数据结构】10道经典面试题目带你玩转链表
数据结构栈与队列篇思维导图:
相关文章:

【数据结构】循环队列
🦄个人主页:修修修也 🎏所属专栏:数据结构 ⚙️操作环境:Visual Studio 2022 目录 🎏队列顺序存储的不足 🎏循环队列的定义 🎏设计循环队列 结语 🎏队列顺序存储的不足 我们假设用一个可以存放为n个数据…...

Docker的资源控制
Docker的资源控制: 对容器使用宿主机的资源进行限制,Docker 通过 Cgroup 来控制容器使用的资源配额,包括 CPU 内存 磁盘i/o Docker 使用Linux自带的功能cgroup,Cgroup 是 ControlGroups 的缩写 C crontrol groups是Linux内核…...

SpringBoot 自动装配原理详解
什么是 SpringBoot 自动装配? 我们现在提到自动装配的时候,一般会和 Spring Boot 联系在一起。但是,实际上 Spring Framework 早就实现了这个功能。Spring Boot 只是在其基础上,通过 SPI 的方式,做了进一步优化。 Spr…...

深度探索Linux操作系统 —— 构建initramfs
系列文章目录 深度探索Linux操作系统 —— 编译过程分析 深度探索Linux操作系统 —— 构建工具链 深度探索Linux操作系统 —— 构建内核 深度探索Linux操作系统 —— 构建initramfs 文章目录 系列文章目录前言一、为什么需要 initramfs二、initramfs原理探讨三、构建基本的init…...

使用cmake构建Qt6.6的qt quick项目,添加应用程序图标的方法
最近,在学习qt的过程中,遇到了一个难题,不知道如何给应用程序添加图标,按照网上的方法也没有成功,后来终于自己摸索出了一个方法。 1、准备一张图片作为图标,保存到工程目录下面,如logo.ico。 …...
VUE宝典之vue-dialog使用
文章目录 🍁vue-dialog概述🍁vue-dialog项目引入🍂安装Vue Dialog插件🍂引入Vue Dialog插件🍂引入 Vue Dialog 组件🍂在组件中使用Vue Dialog 🍁vue-dialog代码示例🍁vue-dialog父子…...

AWTK 串口屏开发(1) - Hello World
1. 功能 这个例子很简单,制作一个调节温度的界面。在这里例子中,模型(也就是数据)里只有一个温度变量: 变量名数据类型功能说明温度整数温度。范围 (0-100) 摄氏度 2. 创建项目 从模板创建项目,将 hmi/…...

鸿蒙Harmony开发初探
一、背景 9月25日华为秋季全场景新品发布会,余承东宣布鸿蒙HarmonyOS NEXT蓄势待发,不再支持安卓应用。网易有道、同程旅行、美团、国航、阿里等公司先后宣布启动鸿蒙原生应用开发工作。 二、鸿蒙Next介绍 HarmonyOS是一款面向万物互联,全…...

【MySQL语言汇总[DQL,DDL,DCL,DML]以及使用python连接数据库进行其他操作】
MySQL语言汇总[DQL,DDL,DCL,DML] SQL分类1.DDL:操作数据库,表创建 删除 查询 修改对数据库的操作对表的操作复制表(重点)!!!!! 2.DML:增删改表中数据3.DQL:查询表中的记录…...

解决方案:Mac 安装 pip
python3 --version 通过以下命令来下载pip: curl https://bootstrap.pypa.io/get-pip.py -o get-pip.py curl命令允许您指定一个直接下载链接。使用-o选项来设置下载文件的名称。 通过运行以下命令安装下载的包: python3 get-pip.py...

【恋上数据结构】前缀树 Tire 学习笔记
Tire 需求分析 如何判断一堆不重复的字符串是否以某个前缀开头? 用 Set\Map 存储字符串(不重复)遍历所有字符串进行判断缺点:时间复杂度 O(n) 有没有更优的数据结构实现前缀搜索? Tire(和 Tree 同音&a…...

2023五岳杯量子计算挑战赛数学建模思路+模型+代码+论文
赛题思路:12月6日晚开赛后第一时间更新,获取见文末名片 “五岳杯”量子计算挑战赛,是国内专业的量子计算大赛,也是玻色量子首次联合移动云、南方科技大学共同发起的一场“企校联名”的国际竞赛,旨在深度融合“量子计算…...
Angular中的单向和双向数据绑定
1、单向数据绑定: 单向数据绑定是指数据从组件流向视图或从视图流向组件,但数据的流动是单向的。 在Angular中,主要有以下两种形式的单向数据绑定: 从组件到视图(插值表达式): 使用插值表达式…...

【Vue】vue整合element
上一篇: vue项目的创建 https://blog.csdn.net/m0_67930426/article/details/134816155 目录 整合过程 使用: 整合过程 项目创建完之后,使用编译器打开项目 在控制器里输入如下命令 npm install element-ui 如图表示安装完毕 然后在…...

HarmonyOS应用开发者高级认证考试答案
一、判断题 云函数打包完成后,需要到AppGallery Connect创建对应函数的触发器才可以在端侧中调用(错)在column和Row容器组件中,aligntems用于设置子组件在主轴方向上的对齐格式,justifycontent用于设置子组件在交叉轴…...
6、Broker消息处理流程(六)
前面分析完Broker启动会启动RemotingServer服务同时会注册Processor处理器,接着分析Producer进行消息的发送,当Producer发送完消息后就得到Broker去接收Producer发送的消息了。 Producer发送给Broker消息时候,发送的请求code为SEND_MESSAGE(这…...

Clean 架构下的现代 Android 架构指南
Clean 架构下的现代 Android 架构指南 Clean 架构是 Uncle Bob 提出的一种软件架构,Bob 大叔同时也是 SOLID 原则的命名者。 Clean 架构图如下: 这张图描述的是整个软件系统的架构,而不是单体软件,其中至少包括服务端以及客户端…...
代码随想录算法训练营第四十六天| 139 单词拆分
目录 139 单词拆分 139 单词拆分 class Solution { public:bool wordBreak(string s, vector<string>& wordDict) {vector<bool>dp(s.size() 1);//长度为i的字符串时能否成功拆分unordered_set<string>set(wordDict.begin(),wordDict.end());dp[0] t…...

IEEE期刊论文模板
一、模板下载 1、登陆IEEE作者中心Author Center 地址:Publish with IEEE Journals - IEEE Author Center Journals 2、点击“Download a template” 3、在弹出的模板下载页面点击IEEE模板选择器“IEEE Template Selector” 4、在弹出的模板选择器页面点击“Tran…...

上位机与PLC:ModbusTCP通讯之数据类型转换
前请提要: 从PLC读取的数值,不管是读正负整数还是正负浮点数,读取过来后都会变成UInt16,也就是Ushort类型 一、ushort(UInt16)转成 Int32 源代码方法: //ushort类型转Int32类型的方法private int ushortToInt32(ushort[] date, int start){//先进行判断,长度是否正确…...
React hook之useRef
React useRef 详解 useRef 是 React 提供的一个 Hook,用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途,下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...

循环冗余码校验CRC码 算法步骤+详细实例计算
通信过程:(白话解释) 我们将原始待发送的消息称为 M M M,依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)(意思就是 G ( x ) G(x) G(x) 是已知的)࿰…...
在rocky linux 9.5上在线安装 docker
前面是指南,后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)
概述 在 Swift 开发语言中,各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过,在涉及到多个子类派生于基类进行多态模拟的场景下,…...
VTK如何让部分单位不可见
最近遇到一个需求,需要让一个vtkDataSet中的部分单元不可见,查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行,是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示,主要是最后一个参数,透明度…...

AI病理诊断七剑下天山,医疗未来触手可及
一、病理诊断困局:刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断",医生需通过显微镜观察组织切片,在细胞迷宫中捕捉癌变信号。某省病理质控报告显示,基层医院误诊率达12%-15%,专家会诊…...

vulnyx Blogger writeup
信息收集 arp-scan nmap 获取userFlag 上web看看 一个默认的页面,gobuster扫一下目录 可以看到扫出的目录中得到了一个有价值的目录/wordpress,说明目标所使用的cms是wordpress,访问http://192.168.43.213/wordpress/然后查看源码能看到 这…...

Golang——9、反射和文件操作
反射和文件操作 1、反射1.1、reflect.TypeOf()获取任意值的类型对象1.2、reflect.ValueOf()1.3、结构体反射 2、文件操作2.1、os.Open()打开文件2.2、方式一:使用Read()读取文件2.3、方式二:bufio读取文件2.4、方式三:os.ReadFile读取2.5、写…...

基于Java+VUE+MariaDB实现(Web)仿小米商城
仿小米商城 环境安装 nodejs maven JDK11 运行 mvn clean install -DskipTestscd adminmvn spring-boot:runcd ../webmvn spring-boot:runcd ../xiaomi-store-admin-vuenpm installnpm run servecd ../xiaomi-store-vuenpm installnpm run serve 注意:运行前…...

给网站添加live2d看板娘
给网站添加live2d看板娘 参考文献: stevenjoezhang/live2d-widget: 把萌萌哒的看板娘抱回家 (ノ≧∇≦)ノ | Live2D widget for web platformEikanya/Live2d-model: Live2d model collectionzenghongtu/live2d-model-assets 前言 网站环境如下,文章也主…...