栈 先进后出 就像一个桶一样 先进的到栈底 最后进的是栈顶
队列 先进先出

[模拟栈] [c++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
略
const int N=100010;

int stk[N],tt; tt表示栈顶下标
//插入
stk[++tt] =x;

//弹出
tt--；

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

//栈顶
stk[tt];

单调栈
很抽象 类似于删掉逆序的对 最后得到单调的栈
单调栈主要解决以下问题：
寻找下一个更大元素
寻找前一个更大元素
寻找下一个更小元素
寻找前一个更小元素 诸如此类
有点抽象 类似于删掉逆序的对 最后得到单调的栈
例 给定一个长为N的整数数列 输入每个数左边第一个比它小的数 不存在则-1

[单调栈] [c++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
const int N=100010;

int n,stk[N],tt;

int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        while(tt&stk[tt]>=x) tt--; //如果栈不为空且栈顶大于当前数 那么栈顶必不是答案了 直接删掉
        if(tt) cout<<stk[tt]<<" "; 如果这样处理了 栈不为空 那么栈顶就是答案
        else cout<<-1<<" ";

        stk[++tt]=x; //记得将新数入栈

    }
}

这样时间复杂度就超级屌 O(n)

[模拟队列] [c++]
1
2
3
4
5
6
7
8
9
10
11
12
13
//队尾插入元素 队头弹出元素
int q[N],hh,tt=-1; //hh队头 tt队尾 头在左边便于数组操作

//插入
q[++tt]=x;

//弹出
hh++; 队头指针右移一个位置

//判断是否为空
if(hh<tt) not empty
else empty

单调队列经典例题 滑动窗口 求窗口内最小值

只要前面的数比后面大 前面的数就无用了 只要存在这种逆序对 就删掉大的

[单调队列] [c++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;

const int N=1000010;
int n,k;
int a[N],q[N]; //数组a存原数列 q存的单调队列下标 注意是下标
int main()
{
    cin>>n>>k;
    ios::sync_with_stdio(false)
    cin.tie(0);
    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 因为每次只移动一次 最多就窗口左边一个位置

        while(hh<=tt&&a[q[tt]]>=a[i]) tt--; //求窗口最小值 若插入的数比队尾小 队尾一定不是答案了 就删去
        q[++tt]=i;//更新右端点 与下一个插入的a[i]比较
        if(i>=k-1) cout<<a[q[hh]];//一开始 元素不满k时不输出
    }
}