一、模拟栈：
1.算法模板：
// tt表示栈顶 int stk[N], tt = 0; // 向栈顶插入一个数 stk[ ++ tt] = x; // 从栈顶弹出一个数 tt -- ; // 栈顶的值 stk[tt]; // 判断栈是否为空 if (tt > 0) { }
2.例题：
实现一个栈，栈初始为空，支持四种操作：
- push x – 向栈顶插入一个数 x；
- pop – 从栈顶弹出一个数；
- empty – 判断栈是否为空；
- query – 查询栈顶元素。
现在要对栈进行 M个操作，其中的每个操作 3和操作 4都要输出相应的结果。
输入格式
第一行包含整数 M，表示操作次数。
接下来 M 行，每行包含一个操作命令，操作命令为 push x，pop，empty，query 中的一种。
输出格式
对于每个 empty 和 query 操作都要输出一个查询结果，每个结果占一行。
其中，empty 操作的查询结果为 YES 或 NO，query 操作的查询结果为一个整数，表示栈顶元素的值。
数据范围
1≤M≤100000
1≤x≤10^9
所有操作保证合法。
输入样例：
10push5 query push6pop query pop empty push4 query empty
输出样例：
5 5 YES 4 NO
思路：
数组模拟栈：
用top表示栈顶所在的索引。初始时，top = -1。表示没有元素。
向栈顶插入一个数 x：push x ：栈顶所在索引往后移动一格，然后放入x。st[++top] = x。
从栈顶弹出一个数：pop : top 往前移动一格。top–。
判断栈是否为空：empty ：top 大于等于 0 栈非空，小于 0 栈空。top == -1 ? “YES” : “NO”
查询栈顶元素：query ： 返回栈顶元素。st[top]
#include<iostream> using namespace std; const int N=100010; int tt=0; int st[N]; int main() { int n; cin>>n; while(n--) { string op; int x; cin>>op; if(op=="push") { cin>>x; st[ ++ tt] = x; } else if(op=="pop") { tt--; } else if(op=="empty") { if(tt>0) cout<<"NO"<<endl; else cout<<"YES"<<endl; } else { cout<<st[tt]<<endl; } } return 0; }
二、模拟队列
1.算法模板：
A.普通队列：
// hh 表示队头，tt表示队尾 int q[N], hh = 0, tt = -1; // 向队尾插入一个数 q[ ++ tt] = x; // 从队头弹出一个数 hh ++ ; // 队头的值 q[hh]; // 判断队列是否为空 if (hh <= tt) { }
B.循环队列：
// hh 表示队头，tt表示队尾的后一个位置 int q[N], hh = 0, tt = 0; // 向队尾插入一个数 q[tt ++ ] = x; if (tt == N) tt = 0; // 从队头弹出一个数 hh ++ ; if (hh == N) hh = 0; // 队头的值 q[hh]; // 判断队列是否为空 if (hh != tt) { }
2.思路：
就是一个特殊的数组。这个数组，最前面叫队头，最后面叫队尾。只允许在最后面添加元素，只允许在最前面删除元素。
用一个数组 q 保存数据。
用 hh 代表队头，q[hh] 就是队头元素， q[hh + 1] 就是第二个元素。
用 tt 代表队尾， q[tt] 就是队尾元素， q[tt + 1] 就是下一次入队，元素应该放的位置。
[hh, tt] 左闭右闭，代表队列中元素所在的区间。
3.例题：
实现一个队列，队列初始为空，支持四种操作：
- push x – 向队尾插入一个数 x；
- pop – 从队头弹出一个数；
- empty – 判断队列是否为空；
- query – 查询队头元素。
现在要对队列进行 M个操作，其中的每个操作 3 和操作 4 都要输出相应的结果。
输入格式
第一行包含整数 M，表示操作次数。
接下来 M 行，每行包含一个操作命令，操作命令为 push x，pop，empty，query 中的一种。
输出格式
对于每个 empty 和 query 操作都要输出一个查询结果，每个结果占一行。
其中，empty 操作的查询结果为 YES 或 NO，query 操作的查询结果为一个整数，表示队头元素的值。
数据范围
1≤M≤100000
1≤x≤10^9
所有操作保证合法。
输入样例：
10 push6 empty query pop empty push 3 push 4 pop query push6
输出样例：
NO 6 YES 4
思路：
出队pop：因为 hh 代表队头，[hh, tt] 代表元素所在区间。所以出队可以用 hh++实现，hh++后，区间变为[hh + 1, tt]。
入队push：因为 tt 代表队尾，[hh, tt] 代表元素所在区间。所以入出队可以用 tt++实现，tt++后，区间变为[hh, tt + 1], 然后在q[tt+1]位置放入入队元素。
是否为空empty：[hh, tt] 代表元素所在区间，当区间非空的时候，对列非空。也就是tt >= hh的时候，对列非空。
询问队头query：用 hh 代表队头，q[hh] 就是队头元素，返回 q[hh] 即可。
#include<iostream> using namespace std; const int N=100010; //[hh, tt] 之间为队列（左闭右闭） int q[N]; int hh=0;//队头位置 int tt=-1; int main() { //操作次数 int n; cin>>n; while(n--) { //操作方式 string op; cin>>op; int x; if(op=="push") { cin>>x; q[++tt]=x;//入队：队尾先往后移动一格，再放入要插入的数据 } else if(op=="pop") { hh++;//出队：队头往后移动一格 } else if(op=="empty") { if(hh>tt)cout<<"YES"<<endl;//[hh, tt]表示队列区间,当 hh>tt时，区间不为空 else cout<<"NO"<<endl; } else { //hh指向队头，q[hh]代表队头元素 cout<<q[hh]<<endl; } } return 0; }
三、单调栈
1.算法模板：
常见模型：找出每个数左边离它最近的比它大/小的数 int tt = 0; for (int i = 1; i <= n; i ++ ) { while (tt && check(stk[tt], i)) tt -- ; stk[ ++ tt] = i; }
2.思路：
用单调递增栈，当该元素可以入栈的时候，栈顶元素就是它左侧第一个比它小的元素。
以：3 4 2 7 5 为例，过程如下：
3.例题：
给定一个长度为 N 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 −1。
输入格式
第一行包含整数 N，表示数列长度。
第二行包含 N 个整数，表示整数数列。
输出格式
共一行，包含 N个整数，其中第 i 个数表示第 i个数的左边第一个比它小的数，如果不存在则输出 −1。
数据范围
1≤N≤10^5
1≤数列中元素≤10^9
输入样例：
5 3 4 2 7 5
输出样例：
-1 3 -1 2 2
#include<iostream> using namespace std; const int N=100010; int stk[N],tt; int main() { int n; cin>>n; for(int i=0;i<n;i++) { int x; cin>>x; while(tt&&stk[tt]>=x)tt--;//如果栈顶元素大于当前待入栈元素，则出栈 if(!tt)cout<<"-1 ";//如果栈空，则没有比该元素小的值 else cout<<stk[tt]<<" ";//栈顶元素就是左侧第一个比它小的元素。 stk[++tt]=x; } return 0; }
四、单调队列：
1.算法模板：
常见模型：找出滑动窗口中的最大值/最小值 int hh = 0, tt = -1; for (int i = 0; i < n; i ++ ) { while (hh <= tt && check_out(q[hh])) hh ++ ; // 判断队头是否滑出窗口 while (hh <= tt && check(q[tt], i)) tt -- ; q[ ++ tt] = i; }
2.思路：
最小值和最大值分开来做，两个for循环完全类似，都做以下四步：
1.解决队首已经出窗口的问题;
2.解决队尾与当前元素a[i]不满足单调性的问题;
3.将当前元素下标加入队尾;
4.如果满足条件则输出结果;
需要注意的细节：
上面四个步骤中一定要先3后4，因为有可能输出的正是新加入的那个元素;
队列中存的是原数组的下标，取值时要再套一层，a[q[]];
算最大值前注意将hh和tt重置;
此题用cout会超时，只能用printf;
hh从0开始，数组下标也要从0开始。
3.例题：
给定一个大小为 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 3 1 3 -1 -3 5 3 6 7
输出样例：
-1 -3 -3 -3 3 3 3 3 5 5 6 7
题目中提到了滑动窗口，我们先以示例为例看下什么是滑动窗口？在示例中，我们从数组中第一个元素开始遍历，由于窗口的大小是3，因此当遍历到第三个元素时，窗口就形成了。
之后，继续遍历元素时，为了保持窗口的大小为3，左侧元素就需要从窗口中剔除。这样使得窗口一直在向右移动，直到考察到最后一个元素结束，这就是所谓的滑动窗口。
# include <iostream> using namespace std; const int N = 1000010; int a[N], q[N], hh, tt = -1; int main() { int n, k; cin >> n >> k; for (int i = 0; i < n; ++ i) { scanf("%d", &a[i]); if (i - k + 1 > q[hh]) ++ hh; // 若队首出窗口，hh加1 while (hh <= tt && a[i] <= a[q[tt]]) -- tt; // 若队尾不单调，tt减1 q[++ tt] = i; // 下标加到队尾 if (i + 1 >= k) printf("%d ", a[q[hh]]); // 输出结果 } cout << endl; hh = 0; tt = -1; // 重置！ for (int i = 0; i < n; ++ i) { if (i - k + 1 > q[hh]) ++ hh; while (hh <= tt && a[i] >= a[q[tt]]) -- tt; q[++ tt] = i; if (i + 1 >= k) printf("%d ", a[q[hh]]); } return 0; }
