C++ Stack（栈） – 菜鸟教程

栈是一种先入后出的数据结构，就像是一个圆柱形容器，你往里面放东西先放进去的在下面，必须把他上面的东西都拿出来才能把他也拿出来
单调栈是一个特殊的栈，他要求从栈顶到栈底是单调的（递增或递减）

//stack<数据类型>栈名称
stack<int> sta;

//判断栈是否为空，如果是空返回true，否则false
sta.empty();

//返回栈中元素个数
sta.size();

//返回栈顶元素
sta.top();
//删除栈顶元素
sta.pop();
//把元素入栈
sta.push(4);

表达式求值

AcWing 3302. 表达式求值：多图讲解运算符优先级+详细代码注释 – AcWing

/*
给定一个表达式，其中运算符仅包含 +,-,*,/（加 减 乘 整除），可能包含括号，请你求出表达式的最终值。

注意：
数据保证给定的表达式合法。
题目保证符号 - 只作为减号出现，不会作为负号出现，例如，-1+2,(2+2)*(-(1+1)+2) 之类表达式均不会出现。
题目保证表达式中所有数字均为正整数。
题目保证表达式在中间计算过程以及结果中，均不超过 2^31−1
题目中的整除是指向 0取整，也就是说对于大于 0的结果向下取整，例如 5/3=1，对于小于 0的结果向上取整，例如 5/(1−4)=−1

C++和Java中的整除默认是向零取整；Python中的整除//默认向下取整，因此Python的eval()函数中的整除也是向下取整，在本题中不能直接使用。

输入格式
共一行，为给定表达式。

输出格式
共一行，为表达式的结果。

数据范围
表达式的长度不超过 10^5

输入样例：
(2+2)*(1+1)
输出样例：
8
*/
#include<bits/stdc++.h>
using namespace std;
stack<char> c;//记录运算符
stack<int> sta;//记录数字
map<char,int>mp{{'+',1}, {'-',1}, {'*',2}, {'/',2}};
void eval(){
    int b = sta.top();//第二个数
    sta.pop();
    int a = sta.top();//第一个数
    sta.pop();
    
    char t = c.top();//运算符
    c.pop();
    
    int sum=0;
    //计算
    if(t=='+')sum=a+b;
    if(t=='-')sum=a-b;
    if(t=='*')sum=a*b;
    if(t=='/')sum=a/b;
    
    //入栈
    sta.push(sum);
}
int main(){
    string s;
    cin>>s;
    for(int i=0;i<s.size();i++){
        if(isdigit(s[i])){//数字入栈
            int num=0,j=i;
            while(j<s.size() && isdigit(s[j])){
                num=num*10+(s[j]-'0');
                j++;
            }
            sta.push(num);
            i=j-1;
        }else{
            if(s[i]=='(')c.push(s[i]);
            else if(s[i]==')'){
                while(c.top()!='('){
                    eval();
                }
                c.pop();
            }else{
                //要判断栈c是否为空里面还有没有元素，如果栈c为空还去获取栈顶元素就会报错
                while(!c.empty()&&mp[s[i]]<=mp[c.top()])eval();
                c.push(s[i]);
            }
        }
    }
    while(!c.empty())eval();//处理剩下的
    cout<<sta.top()<<endl;
    return 0;
}

单调栈

/*
给定一个长度为 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<bits/stdc++.h>
using namespace std;
typedef long long ll;

stack<ll>sta;//从栈底到栈顶是单调递增的栈

int main(){
    int n;
    cin>>n;
    while(n--){
        ll a;
        cin>>a;
        if(sta.empty()){//如果栈为空说明这个数的左边没有比他更小的数
            cout<<-1<<" ";
            sta.push(a);
        }else{
            if(a>sta.top()){//入栈元素全是再这个数左边的数，其中从栈顶到栈底第一个小于他的数就是离他最近且小于他的数
                cout<<sta.top()<<" ";
                sta.push(a);
            }else{
                //如果栈不为空且栈顶元素大于这个数就抛出栈顶，直到栈顶元素小于他或者栈为空
                //因为栈内元素都是在该元素左边的，如果后面有元素大于他前面的元素也就一定大于这个元素
                //所以这个数前面大于他的数没必要存在
                while(!sta.empty()&&a<=sta.top()){
                    sta.pop();
                }
                
                if(sta.empty())cout<<-1<<" ";
                else cout<<sta.top()<<" ";
                sta.push(a);//最后把这个数入栈
            }
        }
    }
    return 0;
}