目录

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;
}