容器适配器之栈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()：出栈，移除栈顶元素。

#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;
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<string>
#include<stack>
using namespace std;
int main()
{
	string str;
	while(cin>>str){
		stack<char> s;
		//借助迭代器遍历字符串str 
		string::iterator 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;
}