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

数据结构--队列

一、队列是什么

队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。

总结起来两点:

  1. 一种线性表
  2. 添加操作只能在表尾,删除操作在表头(先进先出)

二、实现队列的思路

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]]);}}

相关文章:

数据结构--队列

一、队列是什么 队列是一种特殊的线性表&#xff0c;特殊之处在于它只允许在表的前端&#xff08;front&#xff09;进行删除操作&#xff0c;而在表的后端&#xff08;rear&#xff09;进行插入操作&#xff0c;队列是一种操作受限制的线性表。进行插入操作的端称为队尾&…...

Python绘图系统25:新增8种绘图函数

文章目录 常用绘图函数单选框的更改逻辑源代码 Python绘图系统&#xff1a; 前置源码&#xff1a; Python打造动态绘图系统&#x1f4c8;一 三维绘图系统 &#x1f4c8;二 多图绘制系统&#x1f4c8;三 坐 标 轴 定 制&#x1f4c8;四 定制绘图风格 &#x1f4c8;五 数据生成导…...

(二) gitblit用户使用教程

(一)gitblit安装教程 (二) gitblit用户使用教程 (三) gitblit管理员手册 目录 网页访问git客户端设置推送错误配置查看当前配置 日常使用仓库分组my profile修改上传代码简洁 网页访问 点击Advanced... 点击Accept the Risk and Contiue 初始用户名和密码都是admin,点击login…...

8.3Jmeter使用json提取器提取数组值并循环(循环控制器)遍历使用

Jmeter使用json提取器提取数组值并循环遍历使用 响应返回值例如&#xff1a; {"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、最简单的隐写 下载附件后&#xff0c;图片格式并不支持打开 根据题目提示&…...

MySql017——组合查询

一、UNION作用 可用UNION操作符来组合数条SQL查询。 二、UNION 使用规则 1、UNION的使用很简单。所需做的只是给出每条SELECT语句&#xff0c;在各条语句之间放上关键字UNION。2、UNION必须由两条或两条以上的SELECT语句组成&#xff0c;语句之间用关键字UNION分隔&#xff…...

【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. 包装器的应用场景&#xff1a;题目 - - 逆波兰表达式求值3. 成员函数 和 static 静态成员函数 使用 包装器 std::bind 适配器绑定1. 使用方法2. 调整参数 顺序3. 指定参数 / 参数个数的调整 std::function 包装器 std::function 包…...

Linux系统编程系列之线程

一、什么是线程 线程&#xff08;Thread&#xff09;是计算机中的基本执行单元&#xff0c;是操作系统调度的最小单位。线程是进程内的一个独立执行流程&#xff0c;一个进程可以包含多个线程&#xff0c;这些线程共享进程的资源&#xff0c;但每个线程都有自己的独立栈空间以及…...

CV面试知识点总结

一.卷积操作和图像处理中的中值滤波操作有什么区别&#xff1f; 1.1卷积操作 卷积操作是一种线性操作&#xff0c;通常用于特征的提取&#xff0c;通过卷积核的加权求和来得到新的像素值。1.2中值滤波 原文&#xff1a; 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&#xff0c;切换指定jdk版本 alternatives --config java按照提示输入编号即可切换&…...

JavaWeb项目:smbms(mysql)

1.准备工作&#xff0c;创建数据库 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脚本中&#xff0c;实现多线程可以使用以下方法&#xff1a; 1&#xff09;使用&符号 在Shell中&#xff0c;可以使用&符号将命令放在后台执行&#xff0c;这样就可以同时执行多个命令。例如&#xff1a; #!/bin/bash command1 & #…...

周记之反思

9.25 这篇总结我承认&#xff0c;是在26号上午写的&#xff0c;那昨天晚上又聊天了&#xff0c;但是对比之前来说好很多了&#xff0c;所以26号上午也就是今天我起了个大早&#xff0c;然后把昨天的尾巴收了一下&#xff0c;没收完&#xff0c;先说说成果&#xff1a; 完成了…...

信创办公–基于WPS的EXCEL最佳实践系列 (数据整理复制粘贴)

信创办公–基于WPS的EXCEL最佳实践系列 &#xff08;数据整理复制粘贴&#xff09; 目录 应用背景操作步骤1、数据查找与替换2、复制或粘贴数据3、使用自动填充工具4、将数据拆分到多列5、应用数字格式 应用背景 数据的整理复制粘贴等在日常的工作中经常使用。本章内容主要学习…...

二极管的直流等效电路和微变等效电路

二级管的主要参数 1.IF&#xff08;最大整流的电流&#xff09; 二极管长期工作做能够通过电流的平均最大值&#xff1a;物理意义&#xff1a;功率电流值。 2.UR 二极管最高反向工作电压 需要留有裕度&#xff0c;通常能达到一半的裕度&#xff1b;UR不能等于UBR。 3.IR 未击穿…...

Python无废话-基础知识字典Dictionary详讲

“字典Dictionary” 是一种无序、可变且可嵌套的数据类型&#xff0c;用于存储键值对。字典使用花括号{}来定义&#xff0c;并用逗号分隔键值对。本文对字典常使用方法&#xff0c;创建字典、添加字典、删除字典、如何获取字典做了知识归纳。 字典有以下几个特征&#xff1a; …...

ChatGPT多模态升级,支持图片和语音,体验如何?

一、前言 9 月 25 日&#xff0c;ChatGPT 多模态增加了新的语音功能和图像功能。这些功能提供了一种新的、更直观的界面&#xff0c;允许我们与 ChatGPT 进行语音对话或展示我们正在谈论的内容。 ChatGPT 现在可以看、听、和说话了&#xff0c;而不单单是一个文本驱动的工具了。…...

(SAR)Sentinel-1影像自动下载

基于ASF网站提供的python代码&#xff0c;实现Sentinel-1影像的自动下载&#xff1b; 1、登录ASF网站 登录Sentinel-1影像ASF网站&#xff1a;https://search.asf.alaska.edu/&#xff1b; 点击网站最右侧Sign in图标&#xff0c;进行用户注册&#xff1b; 注册完用户之后&…...

设计模式10、外观模式Facade

解释说明&#xff1a;外观模式&#xff08;Facade Pattern&#xff09;又称为门面模式&#xff0c;属于结构型模式 Faade 为子系统中的一组接口提供了一个统一的高层接口&#xff0c;该接口使得子系统更加容易使用 外观&#xff08;Facade)角色&#xff1a;为多个子系统对外提供…...

华为数通方向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 中的参数传递方式通常被称为“值传递”&#xff0c;这意味着在方法调用时&#xff0c;实际上传递给方法的是变量的副本&#xff0c;而不是变量本身。尽管这被广泛称为“值传递”&#xff0c;但需要注意的是&#xff0c;这并不意味着 Java 不支持引用传递。事实上&#xff…...

从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)

本文承接&#xff1a; https://blog.csdn.net/qq_37633855/article/details/133339254?spm1001.2014.3001.5501 重点讲解华为智能企业上网行为管理安全解决方案的部署流程。 华为智能企业上网行为管理安全解决方案&#xff08;2&#xff09; 课程地址方案部署整体流程组网规划…...

【python海洋专题九】Cartopy画地形等深线图

【python海洋专题九】Cartopy画地形等深线图 水深图基础差不多了&#xff0c;可以换成温度、盐度等 本期加上等深线 本期内容 1&#xff1a;地形等深线 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的哪个时期进行的 &#xff08;图片转载自Spring Bean的完整生命周期&#xff08;带流程图&#xff0c;好记&#xff09;&#xff09; 3.MQ如…...

UE5.1编辑器拓展【二、脚本化资产行为,快速更改资产名字,1.直接添加前缀或后缀2.通过资产类判断添加修改前缀】

目录 了解相关的函数 第一种做法&#xff1a;自定义添加选择资产的前缀或后缀 代码 效果 第二种做法&#xff1a;通过映射来获取资产类型添加前缀和修改前缀 映射代码 代码 效果 在之前一章中&#xff0c;我们创建了插件&#xff0c;用来扩展编辑器的使用&#xff1a; …...

短期风速预测|LSTM|ELM|批处理(matlab代码)

目录 1 主要内容 LSTM-长短时记忆 ELM-极限学习机 2 部分代码 3 程序结果 4 程序链接 1 主要内容 该程序是预测类的基础性代码&#xff0c;程序对河北某地区的气象数据进行详细统计&#xff0c;程序最终得到pm2.5的预测结果&#xff0c;通过更改数据很容易得到风速预测结…...

【LeetCode热题100】--102.二叉树的层序遍历

102.二叉树的层序遍历 广度优先搜索&#xff1a; 我们可以想到最朴素的方法是用一个二元组 (node, level) 来表示状态&#xff0c;它表示某个节点和它所在的层数&#xff0c;每个新进队列的节点的 level 值都是父亲节点的 level 值加一。最后根据每个点的 level 对点进行分类&…...

做网站代理拉别人赌博/手机优化软件排名

局部组件&#xff1a;局部组件的使用前提是&#xff1a;在根组件App.vue中导入&#xff0c;声明&#xff0c;引用后才能使用&#xff0c;不导入&#xff0c;则不能使用。 全局组件&#xff1a;在入口函数main.js中声明该组件为全局组件后&#xff0c;在任意子组件中可直接使用…...

宁波网站推广排名/网站建立

文章目录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文件 第一步&#xff1a;去官网下载自己系统smartsvn版本文件 下载地址:http://www.smartsvn.com/download 第二步&#xff1a;破解 &#xff08;1&#xff09; 将文件解压到系统路径&#xff1a;/opt/smartsvn (2) 打开smartsvn,选中license注册 …...

比较好的网站建设企业/百度搜索引擎seo

数据库中的变量time_of_last_update是datetime类型,我想要做的就是在表格中打印出来(下面),但理想情况下我想知道将来如何将其转换/转换为DateTime类型PHP,然后使用它上面的方法,如 – >格式等.做&#xff1a;$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日的末日之说在网上传得很历害&#xff0c;当一切变得虚虚实实之时&#xff0c;很多专业人士就开始关心刀片服务器的安全问题了&#xff0c;由其是HP惠普刀片服务器与IBM刀片服务器&#xff0c;这两家的刀片服务器一直是全球服务器市场的主流配置&#xff0c;大家只…...