最近学习了用数组模拟单调栈和单调队列，相较于STL，手动模拟栈和队列可以使印象更深。

下面是栈和队列的简单模拟。

首先我们理解下栈，栈是后进先出的。

即可以类似一个有底的箱子，最底部的东西是最先放入的，那么最底部的东西就会在其上的所有全部都被拿走后，才能被拿出。

如图，绿色部分即栈顶元素，橙色部分即栈底元素。

关于栈有这几个操作

skt是栈数组，tt是栈顶，即最靠近出口的部分
int skt[N], tt; 

栈的操作
1.插入元素，栈是向栈顶插入元素
skt[++tt] = x;

2.弹出元素，遵循后进先出的原则
tt--;

3.判断栈是否为空
if(tt > 0) not empty
else empty

4.取栈顶元素
skt[tt];

接下来是队列的操作，首先我们需要理解下概念，与栈有些许区别，更适合从一个横向的人的排队思路去理解

如图红色先入队列，则其先出队列。

队列两边都是通的，所定义的是先进先出，如同一个人先去比赛，则他先结束比赛。

下面是队列的操作

q是队列数组，tt是队尾，hh是队首，初始化tt为-1，hh为0，则此时队列为空
int q[N], hh, tt = -1;

队列的操作
1.插入元素（后进后出，从队尾插入
q[++tt] = x;

2.弹出元素（先进先出，从队首弹出
hh++;

3.判断队列是否为空
if(hh < tt) not empty
else empty

4.取出队首元素
q[hh];

5.由于队列可以得到首尾的值，故队尾元素也可以取到
q[tt];

1.栈的应用——单调栈的应用  Acwing 830

传送门： https://www.acwing.com/problem/content/description/832/

给定一个长度为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

**本题很显然如果通过暴力的话可能会TLE。

所以我们观察这个规律，从x左边第一个数开始判断其是否小于x，不小于则将其弹出栈，1.直到找到一个小于x的数，输出x或者2.tt已经为0，即栈已空，说明这里没有符合条件的数，则输出-1。

那么由个小疑问，比如若你弹出的数字符合条件小于x之后的数字，而这个数又比x小该怎么办

如4 3 5则依次输出-1 -1 3，这时你会发现，5前面总会有3离5更近而比5小，所以你弹出的数字一定不会符合之后数字的条件

所以就可以有**

while( tt && q[tt] >= x) tt--;

if(tt) cout << q[tt] << ' ';
else cout << -1 << ' ';

2.队列的应用—— 滑动窗口 Acwing 154（单调队列）

传送门： https://www.acwing.com/problem/content/156/

给定一个大小为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

**本题同样，暴力做法就是每次枚举一个窗口，分别找最大和最小，也可能会TLE

所以我们观察规律，发现了最小值和最大值可以通过单调性来处理，把我们的窗口处理为单调减和单调增的窗口，这样每次只要输出窗口的首元素即可。

但是这里可能有一个小疑惑，比如你删的元素若是下一个窗口的最大元素该如何

但实际上，这是不可能的。

比如有2 1 3，窗口为2，求每个窗口最小值

第一个窗口，因为1比2小，删除了2，而第二个窗口严格递增，故不需删除

再如 1 2 4 3 5，窗口为3，求每个窗口最小值

第一个窗口，1 2 4，已严格递增

第二个窗口，2 4 3， 删除4即保持严格递增

第三个窗口在第二次处理后只剩了 3 5 但是本来模样为 4 3 5，仍需要删除4，所以对其并无影响。
**

下面是标程：

#include<iostream>

using namespace std;

const int N = 1000010;

int q[N], a[N];

int main()
{
    int n, k;
    cin >> n >> k;
    for(int i = 0; i < n; i++) cin >> a[i];

    //处理最小值
    int 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) cout << a[q[hh]] << ' '; 
        //这里是保证我们的第一个窗口是q[0~k]的
    }
    cout << endl;

    //处理最大值，具体细节与上基本无差别
    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) cout << a[q[hh]] << ' ';
    }
    cout << endl;

    return 0;
}