栈、单调栈
本文最后更新于 125 天前,其中的信息可能已经有所发展或是发生改变。

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;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇