文章和代码曾经归档至【Github仓库：https://github.com/timerring/algorithms-notes 】或者【AIShareLab】回复 算法笔记 也可获取。
队列算法模板
// hh 示意队头，tt示意队尾int q[N], hh = 0, tt = -1;// 向队尾插入一个数q[ ++ tt] = x;// 从队头弹出一个数hh ++ ;// 队头的值q[hh];// 对尾的值q[tt];// 判断队列是否为空/* if(hh <= tt) not empty else empty*/if (hh <= tt){}例题：滑动窗口
枯燥队列的利用：求滑动窗口中的最大值和最小值
第一步把新元素插入队尾，第二步把滑进来的元素从队首弹出来。
给定一个大小为 $n≤10^6$ 的数组。
有一个大小为 k 的滑动窗口，它从数组的最右边挪动到最左边。
你只能在窗口中看到 k 个数字。
每次滑动窗口向右挪动一个地位。
以下是一个例子：
该数组为 [1 3 -1 -3 5 3 6 7]，k 为 3。
| 窗口地位 | 最小值 | 最大值 |
|---|---|---|
| [1 3 -1] -3 5 3 6 7 | -1 | 3 |
| 1 [3 -1 -3] 5 3 6 7 | -3 | 3 |
| 1 3 [-1 -3 5] 3 6 7 | -3 | 5 |
| 1 3 -1 [-3 5 3] 6 7 | -3 | 5 |
| 1 3 -1 -3 [5 3 6] 7 | 3 | 6 |
| 1 3 -1 -3 5 [3 6 7] | 3 | 7 |
你的工作是确定滑动窗口位于每个地位时，窗口中的最大值和最小值。
输出格局
输出蕴含两行。
第一行蕴含两个整数 n 和 k，别离代表数组长度和滑动窗口的长度。
第二行有 n 个整数，代表数组的具体数值。
同行数据之间用空格隔开。
输入格局
输入蕴含两个。
第一行输入，从左至右，每个地位滑动窗口中的最小值。
第二行输入，从左至右，每个地位滑动窗口中的最大值。
输出样例：
8 31 3 -1 -3 5 3 6 7输入样例：
-1 -3 -3 -3 3 33 3 5 5 6 7求最小值的过程相当于保护了一个升序的序列，每次队尾插入的值会使原队尾大于它的值始终弹出，最初输入时就会弹出该区间的最小值。
思路：
最小值和最大值离开来做，都做以下四步：
- 队首是否出窗口;
- 解决队尾与以后元素a[i]不满足枯燥性;
- 将以后元素下标退出队尾;(肯定要先3后4，因为有可能输入的正是新退出的那个元素;)
- 如果满足条件则输入后果;
须要留神的细节：
队列中存的是原数组的下标，取值时要再套一层，a[q[]];
算最大值前留神将hh和tt重置;
此题用cout会超时，只能用printf;
hh从0开始，数组下标也要从0开始。
尽管有两个循环，然而工夫复杂度是O(N)的，因为while那里判断条件最多执行常数次，比方新退出一个最小值，哪怕始终弹出到队首，队列长度才k个，k是常数，所以while最多执行k次，合起来就是O(kN)，化简就是O(N)。
code
# include <iostream>using namespace std;const int N = 1000010;int a[N], q[N];int main(){ int n,k; scanf("%d%d", &n, &k); for(int i = 0; i < n; i ++) scanf("%d", &a[i]); int hh = 0, tt = -1; // i是以后枚举的右端点，k是区间的长度 // 队列q[]中存的是下标 // 寻找最小值 for(int i = 0; i < n; i ++) { // 判断队头是否应该滑出窗口 // 因为每次窗口只挪动一位，因而这里写if即可，不必写while // q[tt]（队尾序号）的失常范畴在i-k+1到i之间 你能够画图模仿一下，很简略 if(hh <= tt && i - k + 1 > q[hh]) hh ++; // 如果新插入的数比队尾数要小的话，就将该队尾弹出 // 可能会始终弹出到队首，也可能不会(队首比他还小) // 相当于保护了一个升序的序列 while(hh <= tt && a[q[tt]] >= a[i]) tt --; // 而后将i存入q中的队尾 q[ ++ tt] = i; // 如果i比区间长度大的话，打印q队头的序号的元素值，因为如果i从左向右挪动还有余k个，那么就不必输入。只有队列目前没有超过 i - k + 1 > q[hh] 的限度，就始终输入队首的最小值。 // 留神 i 是从 0 开始的，例如k = 3， 因而向右挪动三次就是2，k - 1 = 2 if(i >= k - 1) printf("%d ", a[q[hh]]); } puts(""); // 最大值是一个齐全对称的写法 hh = 0, tt = -1; for(int i = 0; i < n; i ++) { if(hh <= tt && i - k + 1 > q[hh]) hh ++; // 这里把大于改成小于即可 // 相当于保护了一个降序的序列 while(hh <= tt && a[q[tt]] <= a[i]) tt --; q[ ++ tt] = i; if(i >= k - 1)printf("%d ", a[q[hh]]); } return 0;}