旅游网站开发说明,互联网营销的方式有哪些,WordPress前端上传大文件,如何建立一个网站视频教学一、队列是什么
队列是一种特殊的线性表#xff0c;特殊之处在于它只允许在表的前端#xff08;front#xff09;进行删除操作#xff0c;而在表的后端#xff08;rear#xff09;进行插入操作#xff0c;队列是一种操作受限制的线性表。进行插入操作的端称为队尾…一、队列是什么
队列是一种特殊的线性表特殊之处在于它只允许在表的前端front进行删除操作而在表的后端rear进行插入操作队列是一种操作受限制的线性表。进行插入操作的端称为队尾进行删除操作的端称为队头。
总结起来两点 一种线性表添加操作只能在表尾删除操作在表头先进先出 二、实现队列的思路
1.初始化一个空队列
初始化一个大小固定的数组并将头指针尾指针都指向下表为0的位置但其实这种初始化头指针指向的是队首尾指针指向的是队尾的后一个元素。
2.往队列里添加元素
往队列里添加元素尾指针后移一位。 一直添加直到队列满 这个时候尾指针已经出现在数组下标外了
3.消费队列元素
每消费一个队列元素头指针指向的元素出队并且后移一位
再消费两个
这个时候我们想往队列里继续添加元素尾指针后移然后发现出现了假溢出的情况因为尾指针无法再向后移动而队列实际上并没有满我们又无法继续往队列里添加数据。这个时候其实有两种解决方案。 方案一我们每消费一个元素其后面的元素都整体往前移动一位就像我们生活中排队打饭一样后面的人都往前挪一挪。但这种方案带来的后果是带来的时间开销太大因为基本上要操作所有的元素所以这种方案不可行。 方案二尾指针在指向下表为最后一个元素时再添加元素如果还有空位就将尾指针重新指向0头指针在取到下表数组末尾时如果前面还有元素头指针也指向0这就是我们说的环形队列。
三、实现环形队列
1.环形队列示例图
尾指针重新指向零 再添加一个元素
连续消费三个元素如果前面还有元素头指针也指向0 这个时候我们发现那个原来熟悉的队列又回来了。
Acwing 829 模拟队列
理解和感悟
用数组模拟队列比用数组模拟栈要麻烦一点因为栈是同一边进同一边出而队列是尾巴进脑袋出。
举个栗子 1、先加入一个元素a那么需要tt, 就是tt0, 然后要求a出队就是hh, 这时hh1, 现在队列为空hhtt。 2、因为数组的特点在数组后面增加元素很方便在头部增加元素很麻烦所以设计了hh在左tt在右的策略出队hh, 入队tt 3、使用数组模拟队列的另一个好处就是可以遍历队列中的每一个数字这和用数组模拟栈是一样的这也是STL比不了的。 普通队列解法
#include bits/stdc.husing 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.husing 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, 如果不满足该条件就从队列头删去该数可见单调队列是个双端队列这也便是为什么不用栈的原因。
具体实现时我们令head0表示队列头, tail-1表示队列尾 那么问题来了为什么head要为0tail为-1呢 试想一下如果head不为0,那么当headtail时队列中到底是没有数还是有1个数呢显然无法判断。 所以我们令head的值1当headtail时队列中便是有值的,如果headtail队列便为空。
该数组为 [1 3 -1 -3 5 3 6 7]k为3。 我们用样例来模拟一下单调队列以求最小值为例 i0队列为空1进队[1] i13比1大满足单调性3进队[1,3] i2-1比3小破坏单调性3出队-1比1小1出队队列为空-1进队[-1]此时ik输出队头即-1 i3-3比-1小-1出队队列为空-3进队[-3]输出-3 i45比-3大5进队[-3,5]输出-3 i53比5小5出队3比-3大3进队[-3,3]输出-3 i6-3下标为4i-43大于等于k-3已不在区间中-3出队6比3大6进队[3,6]输出3 i77比6大7进队[3,6,7]输出3 -1 -3 -3 -3 3 3 这样最小值便求完了最大值同理只需在判断时改变符号即可。
#include iostreamusing 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]]);}}
