前段时间有小伙伴留言说“大李，能不能讲讲数据结构的知识”，由易入难，今天我们就来学学数据结构中栈（Stack）的知识。
当然，可能还有些小伙伴可能不知道什么是数据结构，这里也简单带大家了解下。
了解数据结构
数据结构是一种在程序中系统化管理数据集合的形式。它通常由以下3个概念组合而成：
数据集合：通过对象数据的本体（例如数组和结构体）保存数据集合。
规则：保证数据集合按照一定规矩进行正确操作、管理和保存的规则（例如按照顺序取出数据）。
操作：增、删、改、查等对数据集合的操作
栈及其特点
栈是一种线性数据结构，栈的特征是数据的插入和删除只能通过一端来实现，这一端称为“栈顶”，相应的另一端称为“栈底”。
用一个简单的例子来说，栈就像一个放乒乓球的圆筒，底部是封住的，如果你想拿出乒乓球，只能从顶部拿。同样的，如果你想再将乒乓球放回去，也只能从顶部放入其中。
当然生活中还有很多这样的例子，再比如食堂中的一叠盘子，我们只能从顶端一个一个的取，放盘子也只能放在最上方。
总结栈的特点为：先入后出(Last In First Out->LIFO)，即先入栈的元素要在之后入栈的元素取出来之后才能取出来。
STL模板中栈的基本使用
对于栈的使用，我们可以直接利用STL模板来实现，STL模板库中栈的基本操作如下：
头文件：#include<stack>
创建一个存放int类型数据的空栈s：stack<int> s;
s.empty() : 判断栈是否为空，为空返回true，否则返回false；
s.size(): 返回栈中元素的个数；
s.top(): 获取栈顶元素的值；
s.push(k): 向栈中添加新的元素k；
s.pop(): 删除栈s的栈顶元素。
s.push(k): 向栈中添加新的元素k；
s.pop(): 删除栈s的栈顶元素。
训练：逆波兰表达式
逆波兰表达式，又称后缀表达式，后缀表达式不包含括号，运算符(包括'+''-''*''/')放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则，如：(2 + 1) * 3 ， 即2 1 + 3 *。利用栈结构，将后缀表达式的结果计算出。
【输入描述】输入一个逆波兰表达式，字符之间用空格隔开
【输出描述】输出算式结果
【输入样例】2 1 + 3 *
【输出样例】9
参考程序
#include<iostream>
#include<stack>
using namespace std;
int main(){
int t,k;
char c;
stack<int> s;
while(cin>>c){
if(c>='0'&&c<='9')
s.push(c-'0'); //是数字就入栈
if(c=='+'){
t=s.top(); //获取栈顶数字
s.pop(); //出栈
k=s.top(); //获取新的栈顶
s.pop(); //出栈
s.push(t+k); //相加的和入栈
}
if(c=='-'){
t=s.top(); //获取栈顶
s.pop(); //出栈
k=s.top(); //获取新的栈顶
s.pop(); //出栈
s.push(k-t); //相减结果入栈，注意顺序
}
if(c=='*'){
t=s.top();
s.pop();
k=s.top();
s.pop();
s.push(t*k); //相乘的积入栈
}
if(c=='/'){
t=s.top();
s.pop();
k=s.top();
s.pop();
s.push(k/t); //相除结果入栈注意顺序
}
}
cout<<s.top();
return 0;
}
