一种"操作受限"的线性表数据结构--栈(Stack)
栈(Stack)是限定尽在表尾部进行插入和删除操作的线性表。允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)，不含任何数据元素的栈称为空栈。支持两个基本操作：入栈push()和出栈pop()。
栈的顺序存储结构--顺序栈(Array实现)
// 基于数组实现的顺序栈
public class ArrayStack {
private String[] items; // 数组
private int count; // 栈中元素个数
private int n; // 栈的大小
// 初始化数组，申请一个大小为 n 的数组空间
public ArrayStack(int n) {
this.items = new String[n];
this.n = n;
this.count = 0;
}
// 入栈操作
public boolean push(String item) {
// 数组空间不够了，直接返回 false，入栈失败。
if (count == n) return false;
// 将 item 放到下标为 count 的位置，并且 count 加一
items[count] = item;
++count;
return true;
}
// 出栈操作
public String pop() {
// 栈为空，则直接返回 null
if (count == 0) return null;
// 返回下标为 count-1 的数组元素，并且栈中元素个数 count 减一
String tmp = items[count-1];
--count;
return tmp;
}
}
栈在入栈和出栈过程中，只需要一两个临时变量存储空间，所以时间复杂度和空间复杂度都是O(1)。
两栈共享空间
栈的顺序存储是很方便的，因为它只准栈顶进出元素，所以不存在线性表的插入和删除时需要移动元素的问题。但是他有一个很大的缺陷，就是必须实现确定数组存储空间大小，万一不够用了，就需要动态扩容数组的容量，这样会使入栈的空间复杂度和时间复杂度退化成O(n)。
思路：数组有两个端点，两个栈有两个栈底，让一个栈的栈底为数组的始端，即下标为0处，另一个栈的栈底为数组的末端，即下标为数组长度n-1处。这样两个栈如果增加元素，就是两端点向中间延伸，只要是两个栈顶指针不见面，两个栈就可以一直使用。
这样的数据结构，通常都是当两个具有相同数据类型的栈，两个栈的空间需求有相反关系时，也就是一个栈增长时另一个栈在缩短的情况。这样使用两栈共享空间存储方法才有比较大的意义
栈的链式存储结构--链式栈
一般的情况是将栈顶放在链表的头部，因为链表本身支持快速增删结点，所以在时间和空间复杂度上都是O(1)。
如果栈的使用过程中元素变化不可预料，有时很小，有时非常大，那么最后用链式栈，反之如果他的变化在可控范围内，建议使用顺序栈会更好一些。
栈的作用
在函数调用中的应用--函数调用栈
在jvm内存中，分配了一块独立的内存空间--栈，用来存储函数调用时的临时变量，每次进入一个函数，就会将临时变量作为一个栈帧入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈。
浏览器的前进与后退功能
使用两个栈，A和B，把首次浏览的页面一次压入栈A，当点击后退按钮时，再依次从栈A中出栈，并将出栈的数据依次放入栈B，这样就实现了浏览器的前进和后退功能。
栈在表达式求值中的应用
没有括号的表达式
通过两个栈来实现的，其中一个保存操作数的栈，另一个是保存运算符的栈。从左向右遍历表达式，当遇到数据，就直接压入操作数栈；当遇到运算符，就与运算符栈的栈顶元素进行比较。
如果比运算符栈顶元素的优先级高，就将当前运算符压入栈；如果比运算符栈顶元素的优先级低或者相同，从运算符栈中取栈顶运算符，从操作数栈的栈顶取2个操作数，然后进行计算，再把计算完的结果压入操作数栈，继续比较。
有括号的表达式
-先将标准四则运算表达式(中缀表达式)转成后缀表达式(逆波兰表示)
规则：从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分；若是符号，则判断其与栈顶符号的优先级，是右括号或优先级不高于栈顶符号(乘除优先加减)则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止。
-应用后缀表达式计算最终的结果
规则：从左到右遍历表达式的每个数字和符号，遇到是数字就进栈，遇到是符号，就将处于栈顶两个数字出栈，进行运算，运算结果进栈，一直到最终获得结果。
