目录
STLstack
栈的简单应用举例
手写栈
单调栈
STLstack
stack<Type>s//定义栈,Type为数据类型
s.push(item)//把item放入栈顶
s.top()//返回栈顶的元素,但不会删除
s.pop()//删除栈顶的元素,但不会返回。在出站时需要执行两步操作
//先用top()获得栈顶元素,再使用pop()删除栈顶元素
s.size()//返回栈中元素的个数
s.empty()//检查栈是否为空,如果为空则返回true,否则返回false
栈的简单应用举例
题目:翻转字符转
#include<bits/stdc++.h>
using namespace std;
int main(){int n;cin>>n;getchar();// 读取并丢弃换行符while(n--){stack<char> s;while(true){char ch=getchar();if(ch==' '||ch=='\n'||ch==EOF){while(!s.empty()){cout<<s.top();s.pop();}if(ch=='\n'||ch==EOF){break;}cout<<" ";}else{s.push(ch);}}cout<<endl;}return 0;
}
手写栈
针对上述题目,使用手写栈来实现。
#include<bits/stdc++.h>
const int N=100100;
using namespace std;
struct mystack{char a[N];int t=0;void push(char x){a[++t]=x;}char top(){return a[t];}void pop(){t--;}int empty(){return t==0?1:0;}
}st;
int main(){int n;cin>>n;getchar();while(n--){while(true){char ch=getchar();if(ch==' '||ch=='\n'||ch=='EOF'){while(!st.empty()){cout<<st.top();st.pop();}if(ch=='\n'||ch=='EOF'){break;}cout<<" ";}else{st.push(ch);}}cout<<endl;}return 0;
}
单调栈
题目
约翰的N头奶牛站成一排,奶牛i的身高是。现在,每只奶牛都在向右看齐。对于奶牛i,如果奶牛j满足i<j且Hi<Hj,我们可以说奶牛i可以仰望奶牛j。 求出每只奶牛离她最近的仰望对象。
输入格式
6
3
2
6
1
1
2
输出格式
3
3
0
6
6
0
STL stack代码
#include<bits/stdc++.h>
using namespace std;
int h[100001],ans[100001];
int main(){int n;cin>>n;for(int i=1;i<=n;i++){cin>>h[i];}stack<int>st;for(int i=n;i>=1;i--){while(!st.empty()&&h[st.top()]<=h[i]){st.pop();}if(st.empty()){ans[i]=0;}else{ans[i]=st.top();}st.push(i);}for(int i=1;i<=n;i++){cout<<ans[i]<<endl;}return 0;
}
手写栈代码
#include<bits/stdc++.h>
using namespace std;
const int N=100100;
struct mystack{int a[N];int t=0;void push(int x){a[++t]=x;} int top(){return a[t];}void pop(){t--;}int empty(){return t==0?1:0;}
}st;
int h[N],ans[N];
int main(){int n;cin>>n;for(int i=1;i<=n;i++){cin>>h[i];}for(int i=n;i>=1;i--){while(!st.empty()&&h[st.top()]<=h[i]){st.pop();}if(st.empty()){ans[i]=0;}else{ans[i]=st.top();}st.push(i);}for(int i=1;i<=n;i++){cout<<ans[i]<<endl;}return 0;
}