数据结构--队列
一、队列是什么
队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作
,而在表的后端(rear)进行插入操作
,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。
总结起来两点:
- 一种线性表
- 添加操作只能在表尾,删除操作在表头(先进先出)
二、实现队列的思路
1.初始化一个空队列
初始化一个大小固定的数组,并将头指针,尾指针都指向下表为0的位置,但其实这种初始化头指针指向的是队首,尾指针指向的是队尾的后一个元素。
2.往队列里添加元素
往队列里添加元素,尾指针后移一位。
一直添加直到队列满
这个时候尾指针已经出现在数组下标外了
3.消费队列元素
每消费一个队列元素,头指针指向的元素出队,并且后移一位
再消费两个
这个时候我们想往队列里继续添加元素,尾指针后移,然后发现出现了假溢出的情况,因为尾指针无法再向后移动,而队列实际上并没有满,我们又无法继续往队列里添加数据。这个时候其实有两种解决方案。
方案一:我们每消费一个元素,其后面的元素都整体往前移动一位,就像我们生活中排队打饭一样,后面的人都往前挪一挪。但这种方案带来的后果是,带来的时间开销太大,因为基本上要操作所有的元素,所以这种方案不可行。
方案二:尾指针在指向下表为最后一个元素时,再添加元素,如果还有空位,就将尾指针重新指向0,头指针在取到下表数组末尾时,如果前面还有元素,头指针也指向0,这就是我们说的环形队列。
三、实现环形队列
1.环形队列示例图
尾指针重新指向零
再添加一个元素
连续消费三个元素,如果前面还有元素,头指针也指向0
这个时候我们发现那个原来熟悉的队列又回来了。
Acwing 829 模拟队列
理解和感悟
用数组模拟队列,比用数组模拟栈要麻烦一点,因为栈是同一边进同一边出,而队列是尾巴进,脑袋出。
举个栗子
1、先加入一个元素
a
,那么需要++tt
, 就是tt==0
, 然后要求a
出队,就是hh++
, 这时,hh=1
, 现在队列为空,hh>tt
。
2、因为数组的特点,在数组后面增加元素很方便,在头部增加元素很麻烦,所以设计了hh
在左,tt
在右的策略,出队hh++
, 入队++tt
3、使用数组模拟队列的另一个好处,就是可以遍历队列中的每一个数字,这和用数组模拟栈是一样的,这也是STL
比不了的。
普通队列解法
#include <bits/stdc++.h>using namespace std;
const int N = 1e5 + 10;
int q[N], hh, tt = -1;
int main() {int n;cin >> n;while (n--) {string op;cin >> op;if (op == "push") cin >> q[++tt];else if (op == "empty")hh > tt ? cout << "YES" << endl : cout << "NO" << endl;else if (op == "query")cout << q[hh] << endl;else hh++;}return 0;
}
循环队列解法
#include <bits/stdc++.h>using namespace std;
const int N = 1e5 + 10;
int q[N], hh, tt;
int main() {int n;cin >> n;while (n--) {string op;cin >> op;if (op == "push") {cin >> q[tt++];if (tt == N) tt = 0; // 加冒了,就回到0} else if (op == "empty")hh == tt ? cout << "YES" << endl : cout << "NO" << endl;else if (op == "query")printf("%d\n", q[hh]);else {hh++;if (hh == N) hh = 0; // 加冒了,就回到0}}return 0;
}
单调队列
单调队列:队列元素之间的关系具有单调性(从队首到队尾单调递增/递减),队首和队尾都可以进行入队出队(即插入删除)
操作
通常解决动态小区间中寻找极值问题。
一、滑动窗口
ACW 154 滑动窗口
单调队列模板题。
对于最小值来说,我们维护一个单调递增队列,
这是因为我们要让队列的头为该区间的最小值,那么后一个数要比头大,
因为是单调的,所以每一个进来的数,都应该比队列中的数大,所以是单调递增队列。
题目中还有一个限制条件, 那便是窗口大小为k, 所以我们要时刻维护队列中的数的下标大于当前下标减去k,
如果不满足该条件,就从队列头删去该数,可见单调队列是个双端队列,这也便是为什么不用栈的原因。
具体实现时,我们令head=0
表示队列头, tail=-1
表示队列尾,
那么问题来了,为什么head要为0,tail为-1呢?
试想一下,如果head不为0,那么当head=tail时,队列中到底是没有数还是有1个数呢?显然无法判断。
所以我们令head的值+1,当head<=tail时,队列中便是有值的,如果head>tail,队列便为空。
该数组为 [1 3 -1 -3 5 3 6 7],k为3。
我们用样例来模拟一下单调队列,以求最小值为例:
i=0,队列为空,1进队,[1]
i=1,3比1大,满足单调性,3进队,[1,3]
i=2,-1比3小,破坏单调性,3出队,-1比1小,1出队,队列为空,-1进队[-1],此时i>=k,输出队头,即-1
i=3,-3比-1小,-1出队,队列为空,-3进队[-3],输出-3
i=4,5比-3大,5进队,[-3,5],输出-3
i=5,3比5小,5出队,3比-3大,3进队,[-3,3],输出-3
i=6,-3下标为4,i-4=3,大于等于k,-3已不在区间中,-3出队,6比3大,6进队,[3,6],输出3
i=7,7比6大,7进队,[3,6,7],输出3
-1 -3 -3 -3 3 3
这样最小值便求完了,最大值同理,只需在判断时改变符号即可。
#include <iostream>using namespace std;/*
求最大值时,用单调队列存储当前窗口内的单调递减的元素,队头是窗口内的最大值,队尾是窗口内的最小值。
求最小值时,用单调队列存储当前窗口内的单调递增的元素,队头是窗口内的最小值,队尾是窗口内的最大值。
*/const int N = 1000010;
int a[N], que[N];int main()
{int n, k;scanf("%d%d", &n, &k);for(int i = 0; i < n; i ++) scanf("%d", &a[i]);int head = 0, tail = -1;for(int i = 0; i < n; i ++){// 下标为que[head] 的元素是否还在当前窗口的最左端,若不在,则单调队中队头为上个窗口中最小值的下标// 进行队头出队,head自动指向第一个比 a[que[head]] 小的元素下标,且在当前窗口内if(head <= tail && i - k + 1 > que[head]) head ++;// 若当前值小于等于队尾元素时,则队尾元素不可能称为窗口最小值// 则将队尾元素出队while(head <= tail && a[que[tail]] >= a[i]) tail --;// 下标入队,便于队头出队,方便处理下一个滑动窗口que[++ tail] = i;// 使用队头中的最小值if(i >= k - 1) printf("%d ", a[que[head]]);}puts("");// 求窗口最大值情况相似head = 0, tail = -1;for (int i = 0; i < n; i ++){if (head <= tail && i - k + 1 > que[head]) head ++;while (head <= tail && a[que[tail]] <= a[i]) tail --;que[++ tail] = i;if (i >= k - 1) printf("%d ", a[que[head]]);}}
相关文章:
数据结构--队列
一、队列是什么 队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,队列是一种操作受限制的线性表。进行插入操作的端称为队尾&…...
Python绘图系统25:新增8种绘图函数
文章目录 常用绘图函数单选框的更改逻辑源代码 Python绘图系统: 前置源码: Python打造动态绘图系统📈一 三维绘图系统 📈二 多图绘制系统📈三 坐 标 轴 定 制📈四 定制绘图风格 📈五 数据生成导…...
(二) gitblit用户使用教程
(一)gitblit安装教程 (二) gitblit用户使用教程 (三) gitblit管理员手册 目录 网页访问git客户端设置推送错误配置查看当前配置 日常使用仓库分组my profile修改上传代码简洁 网页访问 点击Advanced... 点击Accept the Risk and Contiue 初始用户名和密码都是admin,点击login…...
8.3Jmeter使用json提取器提取数组值并循环(循环控制器)遍历使用
Jmeter使用json提取器提取数组值并循环遍历使用 响应返回值例如: {"code":0,"data":{"totalCount":11,"pageSize":100,"totalPage":1,"currPage":1,"list":[{"structuredId":&q…...
SNERT预备队招新CTF体验赛-Misc(SWCTF)
目录 1、最简单的隐写 2、旋转我 3、is_here 4、zip伪加密 5、压缩包密码爆破 6、我就藏在照片里 7、所以我放弃了bk 8、套娃 9、来自银河的信号 10、Track_Me 11、勇师傅的奇思妙想 1、最简单的隐写 下载附件后,图片格式并不支持打开 根据题目提示&…...
MySql017——组合查询
一、UNION作用 可用UNION操作符来组合数条SQL查询。 二、UNION 使用规则 1、UNION的使用很简单。所需做的只是给出每条SELECT语句,在各条语句之间放上关键字UNION。2、UNION必须由两条或两条以上的SELECT语句组成,语句之间用关键字UNION分隔ÿ…...
【0224】源码分析RelFileNode对smgr访问磁盘表文件的重要性(2)
1. RelFileNode的角色 RelFileNode 是一个结构体数据类型,声明于relfilenode.h(src\include\storage )头文件中,该数据类型十分重要,因为它 “提供所有我们需要知道的物理访问关系表的信息。” smgr要访问磁盘上面的数据表文件,则需要此RelFileNode提供必要信息。 可以说…...
2310C++λ中完美转发
原文 C11里面就引入了完美转发概念,通过它,可按参数实际类型转发参数. 元<型名 T>空 处理(T&t){输出<<"左值\n";} 元<型名 T>空 处理(T&&t){输出<<"右值\n";} 元<型名 T>空 测试转发(T&&t){处理(前向&…...
【C++11】std::function 包装器(又叫适配器),std::bind 绑定
文章目录 std::function 包装器1. 使用方法2. 包装器的应用场景:题目 - - 逆波兰表达式求值3. 成员函数 和 static 静态成员函数 使用 包装器 std::bind 适配器绑定1. 使用方法2. 调整参数 顺序3. 指定参数 / 参数个数的调整 std::function 包装器 std::function 包…...
Linux系统编程系列之线程
一、什么是线程 线程(Thread)是计算机中的基本执行单元,是操作系统调度的最小单位。线程是进程内的一个独立执行流程,一个进程可以包含多个线程,这些线程共享进程的资源,但每个线程都有自己的独立栈空间以及…...
CV面试知识点总结
一.卷积操作和图像处理中的中值滤波操作有什么区别? 1.1卷积操作 卷积操作是一种线性操作,通常用于特征的提取,通过卷积核的加权求和来得到新的像素值。1.2中值滤波 原文: https://blog.csdn.net/weixin_51571728/article/detai…...
Centos一键安装、切换各版本JDK
查看服务中的安装的jdk rpm -qa | grep java获取jdk各版本信息 yum -y list java*查看指定版本 yum -y list java*|grep 1.8安装jdk yum install java-11-openjdk当服务器中有多个版本jdk,切换指定jdk版本 alternatives --config java按照提示输入编号即可切换&…...
JavaWeb项目:smbms(mysql)
1.准备工作,创建数据库 CREATE DATABASE smbms;USE smbms;CREATE TABLE smbms_address (id BIGINT(20) NOT NULL AUTO_INCREMENT COMMENT 主键ID,contact VARCHAR(15) COLLATE utf8_unicode_ci DEFAULT NULL COMMENT 联系人姓名,addressDesc VARCHAR(50) COLLATE u…...
shell脚本的多线程介绍
shell脚本的多线程介绍 shell脚本中,实现多线程可以使用以下方法: 1)使用&符号 在Shell中,可以使用&符号将命令放在后台执行,这样就可以同时执行多个命令。例如: #!/bin/bash command1 & #…...
周记之反思
9.25 这篇总结我承认,是在26号上午写的,那昨天晚上又聊天了,但是对比之前来说好很多了,所以26号上午也就是今天我起了个大早,然后把昨天的尾巴收了一下,没收完,先说说成果: 完成了…...
信创办公–基于WPS的EXCEL最佳实践系列 (数据整理复制粘贴)
信创办公–基于WPS的EXCEL最佳实践系列 (数据整理复制粘贴) 目录 应用背景操作步骤1、数据查找与替换2、复制或粘贴数据3、使用自动填充工具4、将数据拆分到多列5、应用数字格式 应用背景 数据的整理复制粘贴等在日常的工作中经常使用。本章内容主要学习…...
二极管的直流等效电路和微变等效电路
二级管的主要参数 1.IF(最大整流的电流) 二极管长期工作做能够通过电流的平均最大值:物理意义:功率电流值。 2.UR 二极管最高反向工作电压 需要留有裕度,通常能达到一半的裕度;UR不能等于UBR。 3.IR 未击穿…...
Python无废话-基础知识字典Dictionary详讲
“字典Dictionary” 是一种无序、可变且可嵌套的数据类型,用于存储键值对。字典使用花括号{}来定义,并用逗号分隔键值对。本文对字典常使用方法,创建字典、添加字典、删除字典、如何获取字典做了知识归纳。 字典有以下几个特征: …...
ChatGPT多模态升级,支持图片和语音,体验如何?
一、前言 9 月 25 日,ChatGPT 多模态增加了新的语音功能和图像功能。这些功能提供了一种新的、更直观的界面,允许我们与 ChatGPT 进行语音对话或展示我们正在谈论的内容。 ChatGPT 现在可以看、听、和说话了,而不单单是一个文本驱动的工具了。…...
(SAR)Sentinel-1影像自动下载
基于ASF网站提供的python代码,实现Sentinel-1影像的自动下载; 1、登录ASF网站 登录Sentinel-1影像ASF网站:https://search.asf.alaska.edu/; 点击网站最右侧Sign in图标,进行用户注册; 注册完用户之后&…...
设计模式10、外观模式Facade
解释说明:外观模式(Facade Pattern)又称为门面模式,属于结构型模式 Faade 为子系统中的一组接口提供了一个统一的高层接口,该接口使得子系统更加容易使用 外观(Facade)角色:为多个子系统对外提供…...
华为数通方向HCIP-DataCom H12-831题库(单选题:181-200)
第181题 以下关于OSPF的5类LSA中的转发地址(ForwardingAddress,FA) 的描述,正确的是哪一项? A、当FA地址为0.0.0.0时,收到该LSA的路由器认为到达目的网段的数据包应该发往对应的ABR,因此将到达ABR的下一跳地址作为这条外部路由的下一跳 B、当FA地址为0.0.0.0时,收到该LS…...
Java 中的参数传递方式
Java 中的参数传递方式通常被称为“值传递”,这意味着在方法调用时,实际上传递给方法的是变量的副本,而不是变量本身。尽管这被广泛称为“值传递”,但需要注意的是,这并不意味着 Java 不支持引用传递。事实上ÿ…...
从0开始python学习-27.selenium 简单登录页面脚本
url https://test.com.cn/login driver.get(url)# 获取登录页面需要输入账号密码进行模拟登录操作 user driver.find_element(By.XPATH,//*[id"username"]).send_keys(username) pwd driver.find_element(By.XPATH,//*[id"selfpwd"]).send_keys(123456)…...
华为智能企业上网行为管理安全解决方案(2)
本文承接: https://blog.csdn.net/qq_37633855/article/details/133339254?spm1001.2014.3001.5501 重点讲解华为智能企业上网行为管理安全解决方案的部署流程。 华为智能企业上网行为管理安全解决方案(2) 课程地址方案部署整体流程组网规划…...
【python海洋专题九】Cartopy画地形等深线图
【python海洋专题九】Cartopy画地形等深线图 水深图基础差不多了,可以换成温度、盐度等 本期加上等深线 本期内容 1:地形等深线 cf ax.contour(lon, lat, ele[:, :], levelsnp.linspace(-9000,-100,10),colorsgray, linestyles-,linewidths0.25, t…...
Java后端模拟面试,题集①
1.Spring bean的生命周期 实例化 Instantiation属性赋值 Populate初始化 Initialization销毁 Destruction 2.Spring AOP的创建在bean的哪个时期进行的 (图片转载自Spring Bean的完整生命周期(带流程图,好记)) 3.MQ如…...
UE5.1编辑器拓展【二、脚本化资产行为,快速更改资产名字,1.直接添加前缀或后缀2.通过资产类判断添加修改前缀】
目录 了解相关的函数 第一种做法:自定义添加选择资产的前缀或后缀 代码 效果 第二种做法:通过映射来获取资产类型添加前缀和修改前缀 映射代码 代码 效果 在之前一章中,我们创建了插件,用来扩展编辑器的使用: …...
短期风速预测|LSTM|ELM|批处理(matlab代码)
目录 1 主要内容 LSTM-长短时记忆 ELM-极限学习机 2 部分代码 3 程序结果 4 程序链接 1 主要内容 该程序是预测类的基础性代码,程序对河北某地区的气象数据进行详细统计,程序最终得到pm2.5的预测结果,通过更改数据很容易得到风速预测结…...
【LeetCode热题100】--102.二叉树的层序遍历
102.二叉树的层序遍历 广度优先搜索: 我们可以想到最朴素的方法是用一个二元组 (node, level) 来表示状态,它表示某个节点和它所在的层数,每个新进队列的节点的 level 值都是父亲节点的 level 值加一。最后根据每个点的 level 对点进行分类&…...
做网站代理拉别人赌博/手机优化软件排名
局部组件:局部组件的使用前提是:在根组件App.vue中导入,声明,引用后才能使用,不导入,则不能使用。 全局组件:在入口函数main.js中声明该组件为全局组件后,在任意子组件中可直接使用…...
宁波网站推广排名/网站建立
文章目录1. 批量分发密钥2. /etc/ansible/hosts主机清单3. /etc/ansible/roles下各任务3.1 elasticsearch任务3.2 four_lb 四层负载任务3.3 kafka任务3.4 lnmp任务4. /etc/ansible/roles/site.yml 任务清单1. 批量分发密钥 [rootm01 ~]# cat ssh.sh # 批量分发公钥的操作 for …...
中国核工业第二二建设有限公司是国企吗/百度seo排名优
smartsvn9破解及license文件 第一步:去官网下载自己系统smartsvn版本文件 下载地址:http://www.smartsvn.com/download 第二步:破解 (1) 将文件解压到系统路径:/opt/smartsvn (2) 打开smartsvn,选中license注册 …...
比较好的网站建设企业/百度搜索引擎seo
数据库中的变量time_of_last_update是datetime类型,我想要做的就是在表格中打印出来(下面),但理想情况下我想知道将来如何将其转换/转换为DateTime类型PHP,然后使用它上面的方法,如 – >格式等.做:$time_date $row[time_of_last_update];$time_date->format(…...
wordpress pcdotfan/百度平台推广
说明:这里仅说明单台服务器的情况.Docker Container 分别映射到不同的端口. Docker Container里通过tomcat对外提供服务. 1.如图,如果反向代理服务器发来一个请求,请求到达Nginx后,假设是匹配到Service A的Upstream,这时会根据nginx.conf里对应的分发算法,分配到端口10100或10…...
做门窗投标网站/ip域名解析查询
2012年12月21日的末日之说在网上传得很历害,当一切变得虚虚实实之时,很多专业人士就开始关心刀片服务器的安全问题了,由其是HP惠普刀片服务器与IBM刀片服务器,这两家的刀片服务器一直是全球服务器市场的主流配置,大家只…...