栈相关算法实现详解
目录
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;
}原文地址：https://blog.csdn.net/m0_72674633/article/details/143674980
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！