本文最后更新于 125 天前,其中的信息可能已经有所发展或是发生改变。
栈是一种先入后出的数据结构,就像是一个圆柱形容器,你往里面放东西先放进去的在下面,必须把他上面的东西都拿出来才能把他也拿出来
单调栈是一个特殊的栈,他要求从栈顶到栈底是单调的(递增或递减)
//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;
}