NOIP学习小站
西安交通大学附属中学航天学校

容器适配器之栈stack

一、stack简介

前面已经介绍过栈(线性表——栈),栈(stack)是一种典型的LIFO(last in first out,后进先出)线性表结构,STL中有专门的stack容器。其实stack是一种容器适配器,默认情况下内部是基于deque容器实现的。

要使用 stack,需要先引入头文件#include<stack>。虽然stack使用顺序容器实现,但它不提供顺序容器具有的大多成员函数。除了size()、empty()这两个所有容器都有的成员函数外,stack还有以下三个常用成员函数:

  1. top():返回栈顶元素;
  2. push():入栈,将新元素压入栈顶;
  3. pop():出栈,移除栈顶元素。
Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include<iostream>
#include<stack>
using namespace std;
int main()
{
stack<int> s;
cout<<s.size()<<endl; //栈中元素数量
s.push(1); //入栈
cout<<s.top()<<endl; //取栈顶元素
s.push(2);
cout<<s.top()<<endl; //取栈顶元素
s.pop(); //出栈
cout<<s.top()<<endl; //取栈顶元素
for(int i=2;i<=5;i++) s.push(i);
while(!(s.empty())){ //栈不为空
cout<<s.top()<<" ";
s.pop();
}
return 0;
}
#include<iostream> #include<stack> using namespace std; int main() { stack<int> s; cout<<s.size()<<endl; //栈中元素数量 s.push(1); //入栈 cout<<s.top()<<endl; //取栈顶元素 s.push(2); cout<<s.top()<<endl; //取栈顶元素 s.pop(); //出栈 cout<<s.top()<<endl; //取栈顶元素 for(int i=2;i<=5;i++) s.push(i); while(!(s.empty())){ //栈不为空 cout<<s.top()<<" "; s.pop(); } return 0; }
#include<iostream>
#include<stack>
using namespace std;
int main()
{	
	stack<int> s;
	cout<<s.size()<<endl;	   //栈中元素数量 
	s.push(1);				  //入栈 
	cout<<s.top()<<endl;		//取栈顶元素 
	s.push(2);
	cout<<s.top()<<endl;		//取栈顶元素
	s.pop();					//出栈 
	cout<<s.top()<<endl;		//取栈顶元素
	
	for(int i=2;i<=5;i++) s.push(i); 
	
	while(!(s.empty())){	    //栈不为空 
		cout<<s.top()<<" ";
		s.pop();
	} 
	return 0;
}

二、经典例题:进制转换

关于进制转换,可以查看这里:数组例题——进制转换。这里将十进制数转换成其他进制数,需要借助短除法,将每次的余数逆序输出。可以将每次出来的余数依次入栈,最后栈里的所有元素依次出栈,利用栈后进先出的特点,实现逆序逆序输出。

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include<iostream>
#include<stack>
using namespace std;
char a[] = {'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};
stack<int> s;
int main()
{
//求十进制数n的m进制
int n,m;
cin>>n>>m;
if(m<2 || m>16) return 0;
//特判
if(n==0 || m==10){
cout<<n<<endl;
return 0;
}
if(n<0){
cout<<"-";
n = -n;
}
//余数依次入栈
while(n>0){
s.push(n%m);
n /= m;
}
//栈里元素依次出栈
while(!(s.empty())){ //while(s.size()){
cout<<a[s.top()];
s.pop();
}
return 0;
}
#include<iostream> #include<stack> using namespace std; char a[] = {'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'}; stack<int> s; int main() { //求十进制数n的m进制 int n,m; cin>>n>>m; if(m<2 || m>16) return 0; //特判 if(n==0 || m==10){ cout<<n<<endl; return 0; } if(n<0){ cout<<"-"; n = -n; } //余数依次入栈 while(n>0){ s.push(n%m); n /= m; } //栈里元素依次出栈 while(!(s.empty())){ //while(s.size()){ cout<<a[s.top()]; s.pop(); } return 0; }
#include<iostream>
#include<stack>
using namespace std;
char a[] = {'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'}; 
stack<int> s;
int main()
{
	//求十进制数n的m进制 
	int n,m;
	cin>>n>>m;

	if(m<2 || m>16) return 0;
	//特判
	if(n==0 || m==10){
		cout<<n<<endl;
		return 0;
	}

	if(n<0){
		cout<<"-";
		n = -n;
	}

	//余数依次入栈
	while(n>0){
		s.push(n%m);
		n /= m;
	}

	//栈里元素依次出栈
	while(!(s.empty())){	//while(s.size()){ 
		cout<<a[s.top()];
		s.pop();
	}
	return 0;
}

三、经典例题:括号匹配

输入若干行表达式,表达式中只会出现小括号,判断每个表达式小括号是否匹配。

对于每个表达式,碰到左括号入栈,碰到右括号出栈。如果出栈时发现栈为空,那么括号匹配失败;如果处理结束后栈不为空,那么括号匹配也失败。

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
//检查字符串中的左右小括号是否匹配
#include<iostream>
#include<string>
#include<stack>
using namespace std;
int main()
{
string str;
while(cin>>str){
stack<char> s;
//借助迭代器遍历字符串str
auto ite=str.begin();
for(;ite!=str.end();ite++){
if(*ite=='('){ //发现左括号,入栈
s.push(*ite);
}else if(*ite==')'){ //发现右括号,出栈
if(s.empty()) break; //该出栈时发现栈已经空了,那肯定不匹配
s.pop();
}
}
//遍历结束后,发现被强制break了或者栈不为空,那就不匹配
if(ite!=str.end() || s.empty()==false){
cout<<"NO"<<endl;
}else{
cout<<"YES"<<endl;
}
}
return 0;
}
//检查字符串中的左右小括号是否匹配 #include<iostream> #include<string> #include<stack> using namespace std; int main() { string str; while(cin>>str){ stack<char> s; //借助迭代器遍历字符串str auto ite=str.begin(); for(;ite!=str.end();ite++){ if(*ite=='('){ //发现左括号,入栈 s.push(*ite); }else if(*ite==')'){ //发现右括号,出栈 if(s.empty()) break; //该出栈时发现栈已经空了,那肯定不匹配 s.pop(); } } //遍历结束后,发现被强制break了或者栈不为空,那就不匹配 if(ite!=str.end() || s.empty()==false){ cout<<"NO"<<endl; }else{ cout<<"YES"<<endl; } } return 0; }
//检查字符串中的左右小括号是否匹配 
#include<iostream>
#include<string>
#include<stack>
using namespace std;
int main()
{
	string str;
	while(cin>>str){
		stack<char> s;
		//借助迭代器遍历字符串str
		auto ite=str.begin();
		for(;ite!=str.end();ite++){ 
			if(*ite=='('){			  //发现左括号,入栈
				s.push(*ite);
			}else if(*ite==')'){		//发现右括号,出栈
				if(s.empty()) break;	//该出栈时发现栈已经空了,那肯定不匹配 
				s.pop();
			}
		}
		//遍历结束后,发现被强制break了或者栈不为空,那就不匹配 
		if(ite!=str.end() || s.empty()==false){
			cout<<"NO"<<endl;
		}else{
			cout<<"YES"<<endl;
		}
	}
	return 0;
}