当前位置: 首页 > news >正文

【数据结构】循环队列

🦄个人主页:修修修也

🎏所属专栏:数据结构

⚙️操作环境: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. 设计循环队列icon-default.png?t=N7T8https://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 地址&#xff1a;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){//先进行判断,长度是否正确…...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

Docker 运行 Kafka 带 SASL 认证教程

Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明&#xff1a;server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...

【网络安全产品大调研系列】2. 体验漏洞扫描

前言 2023 年漏洞扫描服务市场规模预计为 3.06&#xff08;十亿美元&#xff09;。漏洞扫描服务市场行业预计将从 2024 年的 3.48&#xff08;十亿美元&#xff09;增长到 2032 年的 9.54&#xff08;十亿美元&#xff09;。预测期内漏洞扫描服务市场 CAGR&#xff08;增长率&…...

(二)原型模式

原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

Cinnamon修改面板小工具图标

Cinnamon开始菜单-CSDN博客 设置模块都是做好的&#xff0c;比GNOME简单得多&#xff01; 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...

相机从app启动流程

一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

《基于Apache Flink的流处理》笔记

思维导图 1-3 章 4-7章 8-11 章 参考资料 源码&#xff1a; https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...

k8s业务程序联调工具-KtConnect

概述 原理 工具作用是建立了一个从本地到集群的单向VPN&#xff0c;根据VPN原理&#xff0c;打通两个内网必然需要借助一个公共中继节点&#xff0c;ktconnect工具巧妙的利用k8s原生的portforward能力&#xff0c;简化了建立连接的过程&#xff0c;apiserver间接起到了中继节…...

DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”

目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...

算法岗面试经验分享-大模型篇

文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer &#xff08;1&#xff09;资源 论文&a…...