数据结构--队列

一、队列是什么

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（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]]);}}