2、栈与队列

2.1 栈

先进后出

用tt表示栈顶指针，tt--弹出，tt > 0说明非空

stk[++tt]插入，stk[tt]就是栈顶元素

2.1.1 练手题目

2.1.2 练手答案

#include <iostream>

using namespace std;

const int N = 100010;

int m;
// tt表示栈顶指针，tt--弹出，tt > 0说明非空 
int stk[N], tt; 

int main()
{
    cin >> m;
    while (m -- )
    {
        string op;
        int x;

        cin >> op;
        if (op == "push")
        {
            cin >> x;
            stk[ ++ tt] = x;
        }
        else if (op == "pop") tt -- ;
        else if (op == "empty") cout << (tt ? "NO" : "YES") << endl;
        else cout << stk[tt] << endl;
    }

    return 0;
}

2.2 队列

先进先出

hh 表示队头，tt表示队尾，，在队尾插入元素，队头弹出元素

hh = 0, tt = -1;

// 向队尾插入一个数
q[ ++ tt] = x;

// 从队头弹出一个数
hh ++ ;

// 队头的值
q[hh];

// 队尾

q[tt];

// 判断队列是否为空
if (hh <= tt)
{

​ return "not empty"；

}

2.2.1 练手题目

2.2.2 练手答案

#include <iostream>

using namespace std;

const int N = 100010;

int m;
// 在队尾插入，队头弹出 
// hh队头，tt队尾 
int q[N], hh, tt = -1;

int main()
{
    cin >> m;

    while (m -- )
    {
        string op;
        int x;

        cin >> op;
        if (op == "push")
        {
            cin >> x;
            q[ ++ tt] = x;
        }
        else if (op == "pop") hh ++ ;
        else if (op == "empty") cout << (hh <= tt ? "NO" : "YES") << endl;
        else cout << q[hh] << endl;
    }

    return 0;
}

2.3 单调栈

一般只有这些问题：

给定一个序列，求序列中每一个数左/右边离他最近且比他小/大的数在什么位置

2.3.1 练手题目

暴力做法：

这种暴力做法用栈的思想就是：

把i前面的所有元素\(a_1,a_2,...a_{i-1}\)都放到了stack里，不断遍历

考虑单调栈优化：

暴力做法的栈里面有些元素永远都不会输出出来，我们也去遍历了

如在栈里\(a_3 \geq a_5\)，那么\(a_3\)永远都不会输出出来，那么所有满足这种关系的序列都可以删除掉。

最后获得的一定是一个严格单调的序列。

在这个情况下，当到i这个位置时，如果stk[tt]\(\geq a_i\)，那么stk[tt]就可以删除了，因为i永远都是比stk[tt]更优的解。如果stk[tt]\(< a_i\)，那么stk[tt]就是i的最优解。

2.3.2 练手答案

#include<iostream>

using namespace std;

const int N = 100010;
int n;
int stk[N],tt;

int main()
{
    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;
    }
    return 0;
}

2.4 单调队列

经典应用：求滑动窗口的最大值和最小值

如下图的框框中的最大值/最小值

能抽象出这个模型就可以使用单调队列优化

使用队列来做：

首先有一个空队列，先进来1，之后进来3，之后进来-1.

在窗口满了之后，弹出1，将下一个-3放进来.

实际就是将新元素插到队尾，同时弹出队头元素。

暴力做法：每次都遍历一次队列里的元素。O(nk),k为窗口内元素数量，n为步数，约等于O(\(n^2\)).

单调队列优化：求最小值时，如上图的窗口内，当-3进来时，第一个3一定没有用，-3在一天，这个3就永远没有用武之地这个-3还比3活得久，这个3就可以X掉，-1也同理。

总结规律：只要我前面的点比我后面的点大，那么这个前面的点就没有用

最后就可以得到一个严格单调上升的队列。

队列里存储的是下标。通过q[hh]判断是否超出了范围。

2.4.1 练手题目

https://www.acwing.com/problem/content/156/

2.4.2 练手答案

// 单调队列
// 凡是可以抽象出滑动窗口的，都可以用单调队列优化
// 这个窗口可以用队列维护，满3个就既有插入又有弹出，保证每次都是当前窗口
// 都遍历就是O(k),但我们需要的是最小的
// 只要前面有一个点比后面大，前面这个点一定就没用，把大的删掉


#include<iostream>

using namespace std;

const int N = 1000010;

int n,k;
int a[N]; // 存储数值
int q[N]; // 是队列，存储下标

int main()
{
    scanf("%d%d",&n,&k);
    for(int i = 0; i < n; i++) scanf("%d",&a[i]);

    int hh = 0,tt=-1; // 队头和队尾
    for(int i = 0; i < n; i++)
    {

        // 队列中存的是下标而不是值，判断队头下标是否超出i-k+1~i的范围
        // 超出就把队头删掉

        // 判断队头是否划出窗口，用下标判断
        // 终点是i，起点应该是i-k+1, > q[hh]说明已经出了这个口了
        if(hh <= tt && i-k+1 > q[hh]) hh++;
        while(hh <= tt && a[q[tt]] >= a[i]) tt--;

        q[++tt] = i;
        // 不足k个数就不输出了
        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]]) ;
        
    }
    puts("");
    return 0;
}