一篇文章带你了解栈
栈
栈的定义
栈是一种运算受限的线性表，它只能从一头进入或者输出元素，具有**后进先出（LIFO）**的性质。先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH），删除则称为退栈（POP）。
栈的代码实现
栈的基本操作主要有以下几种种 ：入栈（push）、出栈（pop）、询问、判空
在信息学竞赛中比较受到选手喜欢的栈的实现方式有两种：1.用数组实现手写栈 2.利用STL中的模板stack实现
用数组实现
定义一个长度足够长的数组a[N]，以及变量hh代表指向栈顶的指针
//手写栈
#include<iostream>
using namespace std;
const int N=1e5+10;//根据题目要求设置数组长度
int stack[N],hh=0;//初始化栈,hh为指向栈顶的指针
void push(int x){//进栈
stack[++hh]=x;
}
void pop(){//出栈
if(hh!=0)//栈非空
hh--;
}
bool empty(){//判空
if(hh==0) return 1;//是空的返回1
return 0;//非空返回0
}
int query(){//询问栈顶元素
if(hh!=0) return stack[hh];//返回栈顶元素
}
int main(){
//根据题目要求对栈进行操作
push(3);//把3入栈
push(2);//把2入栈
pop();//栈顶元素出栈
if(empty()==1) cout<<"Yes"<<endl;//空栈输出yes
else cout<<"No"<<endl;
cout<<query()<<endl;//输出栈顶元素
}
用stl模板 stack实现
stack初始化
STL中的stack包含在头文件#include<stack>中，用stack<数据类型> 栈名建立一个栈，例如：
整型（int） stack<int> s
浮点型（float、double） stack<float> q stack<double> s
字符型（char） stack<char> s
字符串型（string） stack<string> s
结构体型（node(结构体的名称）） stack<node> s
stack基本操作
s.pop();//出栈
s.push(item);s.emplace(args);//压入栈顶
s.top();//返回栈顶元素，但是不将元素出栈
s.empty();//判空
s.size();//栈的大小
s.swap();//将当前栈中的元素和参数中的元素交换。参数所包含元素的类型必须和当前栈的相同。
实例
#include <algorithm>
#include<iostream>
#include<stack>
using namespace std;
int main()
{
stack <int>stk; //定义int型的栈
for(int i=0;i<10;i++){ //入栈
stk.push(i);
}
cout<<"栈的大小:"<<stk.size()<<endl;
while(!stk.empty()){ //栈不为空时
cout<<stk.top()<<" "; //输出栈顶
stk.pop(); //删除栈顶元素
}
cout<<endl;
cout<<"栈的大小:"<<stk.size()<<endl;
return 0;
}
注意：如果题目中涉及较多的进栈出栈操作，尽量手写栈，因为调用STL模板花费的时间较长容易超时
栈的应用
表达式计算
栈的一大用处是做算数表达式的计算，算数表达式通常有前缀、中缀、后缀三种表达方法
中缀表达式 ：符合人类思维习惯的的表达式 例如：（1-2）*3
前缀表达式：称为波兰式，形如“op A B”，op为运算符，A，B是另外两个前缀表达式，例如* 3 - 1 2
后缀表达式：称为逆波兰式，形如“A B op”，例如 1 2 - 3 *
前缀与后缀表达式不需要使用括号就能确定运算顺序，相比于中缀表达式后缀表达式更加方便计算机计算。因为计算机在计算后缀表达式时，只需要将逐个数字，如果遇到运算符就取出栈顶的两个数进行计算，把结果入栈，当栈中恰好剩下一个数，就是该后缀表达式的值。这种计算方法不需要考虑运算顺序，比较符合计算机的计算方式，因为人类可以一眼判断出哪个可以先计算哪个后计算，但是计算机不行，计算机只能碰到谁算谁。
所以如果想让计算机求解我们人类常用的中缀表达式的值，最快的办法就是把中缀表达式转化成后缀表达式，然后让计算机通过后缀表达式求值，这个转化可以用栈O(N)地完成。当然你也可以利用递归求解中缀表达式的值，这个时间复杂度是O(N^2)的，有兴趣的可以下去自行查找
中缀转后缀运算符
-
建立一个用于存储运算符的栈，逐一扫描该中缀表达式中的元素。
-
如果遇到数字直接输出
-
如果遇到左括号，把左括号入栈。
-
如果遇到右括号，不断取出栈顶并输出直到遇到左括号，然后把左括号出栈
-
如果遇到运算符，跟栈顶的运算符比较，如果栈顶运算符的优先级不低于该运算符就出栈并输出，直到栈顶运算符不低于该运算符，将该运算符入栈
-
当所有的元素都扫描完成后，将栈中剩余的运算符出栈并输出。
#include<iostream> #include<string> #include<stack> #include<cctype> using namespace std; string change(string s){//中缀转后缀 string tmp="";//初始化 stack<char>sta; for(int i=0;i<s.length();i++){ if(isdigit(s[i])) tmp+=s[i];//如果是数字 else if(s[i]=='(') sta.push(s[i]); else if(s[i]==')'){ while(sta.top()!='('){ tmp+=sta.top(); sta.pop(); } sta.pop(); } else{ if(s[i]=='*'||s[i]=='/'){ while((!sta.empty())&&(sta.top()=='*'||sta.top()=='/')){ tmp+=sta.top(); sta.pop(); } sta.push(s[i]); } else if(s[i]=='+'||s[i]=='-'){ while((!sta.empty())&&(sta.top()=='*'||sta.top()=='/'||sta.top()=='+'||sta.top()=='-')){ tmp+=sta.top(); sta.pop(); } sta.push(s[i]); } } } if(!sta.empty()){ while(!sta.empty()){ tmp+=sta.top(); sta.pop(); } } return tmp; } int main(){ string s; cin>>s;//输入中缀表达式 cout<<change(s); }
后缀表达式计算
-
建立一个用于存数的栈，逐一扫描该后缀表达式中的元素
-
如果遇到一个数，则把该数入栈
-
如果遇到运算符，就取出栈顶的两个数进行计算，把结果入栈。
-
扫描完成后，栈中恰好剩下一个数，就是该后缀表达式计算的值
#include<iostream> #include<string> #include<stack> #include<cctype> using namespace std; int cal(string s){//后缀表达式计算 只适用于后缀中个位数字的运算 stack<double> sta; for(int i=0;i<s.length();i++){ if(isdigit(s[i])) sta.push(s[i]-'0'); else{ int t1=sta.top();sta.pop();//后入栈的数 int t2=sta.top();sta.pop();//先入栈的数 cout<<t1<<" "<<t2<<endl; if(s[i]=='-') sta.push(t2-t1); else if(s[i]=='+') sta.push(t2+t1); else if(s[i]=='*') sta.push(t2*t1); else sta.push((double)t2/(double)t1); } } return sta.top(); } int main(){ string s; cin>>s; cout<<cal(s); }
单调栈
单调栈顾名思义里面的元素都是单调有序的，所以单调栈又分为单调递增栈和单调递减栈
- 单调递增栈：从栈顶到栈底元素从小到大
- 单调递减栈：从栈顶到栈底元素从大到小
单调栈作用
通过使用单调栈可以访问到上一个比它大或者比它小的元素，在实际应用中我们需要维护一个单调栈，单调栈能够利用单调性及时排除不可能的选项
单调递增栈：在保持栈内元素单调递增的前提下（如果栈顶元素大于要入栈的元素，将将其弹出），将新元素入栈。
单调递减栈：在保持栈内元素单调递减的前提下（如果栈顶元素小于要入栈的元素，则将其弹出），将新元素入栈。
例题：给定一个长度为 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
分析
如果用暴力的做法是从该数开始向它的左边遍历，直到找到它的左边第一个比它小的数，这种做法时间复杂度是O(N^2)的。使用单调栈的方法可以把时间复杂度降到O(N).
我们以样例 3 4 2 5 7为例，如果栈空输出-1，如果栈顶元素大于等于新元素，则出栈直到栈空或者小于新元素，此时的栈顶为新元素左边小于它的第一个数，输出栈顶元素，然后将新元素入栈。
#include<iostream>
using namespace std;
const int N=1e5+10;
int a[N],s[N],tt=0;
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
int x;
cin>>x;
while(tt&&s[tt]>=x) tt--;//如果非空或者栈顶元素大于当前元素则出栈
if(tt==0) cout<<-1<<" ";
else cout<<s[tt];
s[++tt]=x;
}
return 0;
}
本节习题