acwing算法笔记-数据结构：栈与队列

栈

先入后出的数据结构，可以使用的操作：

1. 入栈: 将元素插入栈顶
2. 出栈：将元素从栈顶弹出
3. 查询：返回栈顶元素
   时间复杂度都是$O(1)$

828. 模拟栈

---

基本思路

用数组模拟栈，不需要考虑空间的问题，这里是算法题

也就是写四个函数，代码很简短也可以直接写在main函数里
push：入栈
pop：出栈
empty：判断是否为空
query：查询栈顶元素

参考代码

#include <iostream>

using namespace std;

const int N = 100010;

int m;
int stk[N], tt;  //tt表示栈顶指针， stk栈

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; //栈指针<0,栈空
        else cout << stk[tt] << endl; //返回栈顶元素
    }

    return 0;
}

Reference

[1]. yxc
[2]. 模拟栈—代码详解
[3]. Bug-Free

3302. 表达式求值

---

基本思路

这道题有一个前置题目，Leetcode150 逆波兰表达式求值（后缀表达式求值）
这题是前缀表达式求值，它相比后缀表达式求值，需要处理括号优先级，所以更麻烦一些

还是用栈模拟中缀表达式的求值过程

开数字栈和操作符栈
若为数字，压栈
若为左括号，压栈
若为右括号，逆向计算直到遇到左括号
若为加减乘除，与操作符栈栈顶比较，如果优先级高，压栈；否则一直计算上一个运算符直到当前运算符优先级高
将剩余的操作符计算完，直到为空

参考代码

#include<iostream>
#include<cstring>
#include<stack>
#include<unordered_map>
using namespace std;
//num里面存放着运算结果以及运算的数
//op里面存放着操作符
stack<int> num;
stack<char> op;
//eval()计算目前的表达式的值
void eval()
{
    //注意因为用的是栈，所以先去出来的是b,其次是a，防止加减法出现负数
    auto b = num.top(); num.pop();
    auto a = num.top(); num.pop();
    auto c = op.top(); op.pop();
    int x;
    if(c == '+') x = a + b;
    else if(c == '-') x = a - b;
    else if(c == '*') x = a * b;
    else x = a/b;
    num.push(x);
}

int main()
{
    unordered_map<char,int> pr{{'+',1},{'-',1},{'*',2},{'/',2}};
    string str;
    cin>>str;
    for(int i = 0;i < str.size();i ++)
    {
        auto c = str[i];
        //倘若这个字符是数字 且 连续出现数字，那么就需要将数字字符组合起来形成一个数
        if(isdigit(c))
        {
            int x = 0, j = i;
            while(isdigit(str[j]) && j < str.size())
                x = x * 10 + str[j++] - '0';
            i = j - 1;//更新i的值
            num.push(x);
        }
        //倘若是左括号，那么就要入操作符
        else if(c == '(')   op.push(c);
        //若是右操作符，那么直到做操作符里所有的数，都要进行一系列的运算
        else if(c == ')')
        {
            while(op.top() != '(')  eval();
            op.pop();//且将左括号删除
        }
        //若操作的是+-/*操作符，则根据栈头与目前操作符比较大小，若栈头操作符大于等于目前操作符则进行计算
        //且将当前运算符入栈
        else
        {
            while(op.size() && pr[op.top()] >= pr[c])   eval();
            op.push(c);
        }
    }
    //将剩余的运算符进行计算
    while(op.size())    eval();
    cout<<num.top()<<endl;
    return 0;
}

Reference

[1]. yxc
[2]. 栈模拟中缀表达式求值过程的简单分析与证明
[3]. 详细注释
[4]. 简单注释
[5]. 详细步骤

单调栈

单调栈就是一种特殊的栈，也就是栈的基础上还具有单调性。
它一般用于解决下类问题
给定一个序列，求序列中的每一个数左边或右边第一个比他大或比他小的数在什么地方；

如果暴力做法是$O(n^2)$,可以用单调栈优化到$O(n)$

那么如何保证栈内具有单调性，其实也就是每次插入的时候必须要保证单调性；
如果可以满足单调性就插入，否则就弹出栈顶，直到可以满足单调性或者栈为空就插入元素

830. 单调栈

---

基本思路

求每一个数左边第一个比它小的数，所以可以用单调递增栈

注意：

1. 单调找相当于是对每个元素进行查询，所以读入序列的方式利用while循环读要方便一点，而不是直接读入数组
2. 这里是stk[tt] >= x 而不是 >,因为我们找的是左边第一个比它小的数，所以需要满足栈内严格单调递增，等于也是属于不合法的也需要pop

参考代码

#include <iostream>

using namespace std;

const int N = 100010;

int stk[N], tt;

int main()
{
    int n;
    cin >> n;
    while (n -- )
    {
        int x;
        scanf("%d", &x);
        while (tt && stk[tt] >= x) tt -- ;  //如果栈顶元素大于等于当前待入栈元素，则出栈
        if (!tt) printf("-1 ");             //如果栈空，则没有比该元素小的值。
        else printf("%d ", stk[tt]);        //否则栈顶元素就是左侧第一个比它小的元素。
        stk[ ++ tt] = x;
    }

    return 0;
}

//自己用for循环写的一个模板
#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int a[N], stk[N], tt;

int main()
{
    int n;
    cin >> n;
    
    for (int i = 0; i < n; i ++ ) cin >> a[i];
    
    //对于每一个元素，通过严格递增的单调栈找到左边第一个比它小的数
    for (int i = 0; i < n; i++ ) {
        while(tt > 0 && stk[tt] >= a[i]) tt--;  //解决栈顶不单调
        if (tt > 0) cout << stk[tt] << " ";     
        else cout << -1 << " ";
        stk[++tt] = a[i];   //找到答案后，当前元素入栈
    }
    
    return 0;
}

Reference

[1]. yxc
[2]. Hasity-图解，详细注释
[3]. 总结
[4]. 单调栈简单思想

队列

先入先出的数据结构，可以使用的操作：

1. 入队: 将元素插入队尾
2. 出队：将元素从队头弹出
3. 查询：返回队头或者是队尾

时间复杂度都是$O(1)$

829. 模拟队列

---

基本思路

用数组模拟队列，不需要考虑空间效率

注意边界：

1. 栈我们一般tt = 0
2. 队列的话，一般循环队列，tt初始化成0，队列中的所有元素是q[hh], q[hh + 1], …, q[tt - 1]；
   不循环的队列，tt一般初始化成-1，队列中的所有元素是q[hh], q[hh + 1], …, q[tt]

参考代码

#include <iostream>

using namespace std;

const int N = 100010;

int m;
int q[N], hh, tt = -1;  //hh队头 tt队尾

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;
}

Reference

[1]. yxc
[2]. 详解，一图胜千言
[3]. Bug-Free
[4]. 模拟队列

单调队列

单调队列是一种特殊的队列，它具有单调性，最经典的应用是滑动窗口

154. 滑动窗口

---

基本思路

首先朴素做法，枚举所有的区间（枚举起点 + 长度（常数）），然后每个区间找最大值和最小值，时间复杂度$O(n^2)$会超时，所以就要想办法优化。
这里是利用单调队列来优化

最小值和最大值分开来做，两个for循环完全类似，都做以下四步：

1. 解决队首已经出窗口的问题;
2. 解决队尾与当前元素a[i]不满足单调性的问题;
3. 将当前元素下标加入队尾;
4. 如果满足条件则输出结果;

注意：

1. 这里如果队列存的是下标，队列里维护的元素个数和窗口大小不需要一致，所以while里维护队列的条件是否加等于都可以
2. 如果队列里存的是值，队列里维护的元素个数和窗口大小需要一致，所以while里维护队列的条件不能加 =，这样相等的元素还是会入队列
3. 求最大值之前要重置队列
4. 单调队列我们通常做法，队列里存的是下标（利于判断队头是否出窗口），虽然存的是下标，但是维护我们维护的是值的单调性
5. 单调队列其实维护的是一个双端队列，队头队尾都可以pop，所以用stl来做的话要用deque

参考代码

# 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;
}

Reference

[1]. yxc
[2]. 精简步骤
[3]. 详细注释
[4]. 思路启发
[5]. Bug-Free deque写法