?栈
?1. 栈的定义
1.1 栈的定义
类似弹夹中的子弹一样先进去，却要后出来，而后进的，反而可以先出来的数据结构
栈( stack)是限定仅在表尾进行插入和删除操作的线性表。
我们把允许插入和删除的一端称为栈顶（top)，另一端称为栈底(bottom)，不含任何数据元素的栈称为空栈。栈又称为后进先出(Last In First Out)的线性表，简称LIFO结构。
理解栈的定义需要注意:
?它的特殊之处就在于限制了这个线性表的插入和删除位置，它始终只在栈顶进行。这也就使得:栈底是固定的，最先进栈的只能在栈底。
?栈的插入操作，叫作进栈，也称压栈、入栈。类似子弹入弹夹。
?栈的删除操作，叫作出栈，也有的叫作弹栈。如同弹夹中的子弹出夹。
1.2 进栈出栈变化形式
最先进栈的元素，不一定是最后出栈的，要看什么情况。栈对线性表的插入和删除的位置进行了限制，并没有对元素进出的时间进行限制，也就是说，在不是所有元素都进栈的情况下，事先进去的元素也可以出栈，只要保证是栈顶元素出栈就可以。
?举例来说：如果我们现在是有3个整型数字元素1、2、3依次进栈，会有哪些出栈次序呢?
?第一种:1、2、3进，再3、2、1出。这是最简单的最好理解的一种，出栈次序为321。
?第二种:1进，1出，2进，2出，3进，3出。也就是进一个就出一个，出栈次序为123。
?第三种:1进，2进，2出，1出，3进，3出。出栈次序为213。
?第四种:1进,1出，2进，3进，3出，2出。出栈次序为132。
?第五种:1进，2进，2出，3进，3出，1出。出栈次序为231。
有没有可能是312这样的次序出栈呢?
答案是肯定不会。因为3先出栈，就意味着，3曾经进栈，既然3都进栈了，那也就意味着，1和2已经进栈了，此时，2一定是在1的上面，就是更接近栈顶，那么出栈只可能是321，不然不满足123依次进栈的要求，所以此时不会发生1比⒉先出栈的情况。
?2. 栈的实现
2.1 栈的Java代码实现
2.1.1 用数组实现：
用数组模拟的话，我们只能在数组的末尾进行插入和删除。
public class Main{
static int[] s = new int[100010]; // 栈
static int idx = 0; // 表示栈内有多少个元素,并指向栈顶
public static void push(int x){ // 插入元素
s[idx++] = x;
}
public static void pop(){ // 删除栈顶元素
idx --;
}
public static int peek(){//获取栈顶元素
return s[idx-1]; //注意这里是idx-1
}
public static Boolean isEmpty(){ // 判空
if(idx == 0) return true;
else return false;
}
public static void main(String[] args){
}
}
2.1.2 使用Java提供的类：
Stack<Integer> stack = new Stack<>();
如下图所示，通过常用操作「入栈 push()」,「出栈 pop()」，展示了栈的先入后出特性。
stack.push(1); // 元素 1 入栈
stack.push(2); // 元素 2 入栈
stack.pop(); // 出栈 -> 元素 2
stack.pop(); // 出栈 -> 元素 1
注意：通常情况下，不推荐使用 Java 的 Vector 以及其子类 Stack ，而一般将 LinkedList 作为栈来使用。详细说明请见：Stack，ArrayDeque，LinkedList 的区别
import java.util.LinkedList;
public class 栈 {
public static void main(String[] args) {
LinkedList<Integer> stack = new LinkedList<>();
stack.addLast(1); // 元素 1 入栈
stack.addLast(2); // 元素 2 入栈
stack.addLast(3);
stack.addLast(4);
stack.removeLast(); // 出栈 -> 元素 4
stack.removeLast(); // 出栈 -> 元素 2
//stack.size();//返回元素个数
System.out.println(stack.size());//2
// stack.peek();//获取但不移除此列表的头（第一个元素）。
System.out.println(stack.peek());//1
// stack.getLast();//返回此列表的最后一个元素
System.out.println(stack.getLast());//2
// stack.getFirst();//返回此列表的第一个元素
System.out.println(stack.getFirst());//2
// stack.isEmpty();//判空
System.out.println(stack.isEmpty());//false
}
}
2.2 栈的出入练习
?3. 栈的应用——四则运算表达式求值
3.1 后缀表达式的定义
我们先来看看，对于“9+(3-1)×3+10÷2”，如果要用后缀表示法应该是什么样子。
正常的数学表达式：9+(3-1)×3+10÷2
后缀表达式：9 3 1 - 3 * + 10 2 / +
“9 3 1 - 3 * + 10 2 / +”，这样的表达式称为后缀表达式，叫后缀的原因在于所有的符号都是在要运算数字的后面出现。显然，这里没有了括号。对于从来没有接触过后缀表达式的同学来讲，这样的表述是很难受的。不过你不喜欢，有机器喜欢，比如我们聪明的计算机。
3.2 后缀表达式的计算结果
为了解释后缀表达式的好处，我们先来看看，计算机如何应用后缀表达式计算出最终的结果20的。
后缀表达式：9 3 1 - 3 * + 10 2 / +
?规则:
从左到右遍历表达式的每个数字和符号，遇到是数字就进栈，遇到是符号，就将处于栈顶两个数字出栈，进行运算，运算结果进栈，一直到最终获得结果。
初始化一个空栈。此栈用来对要运算的数字进出使用。如左图所示。
后缀表达式中前三个都是数字，所以9、3、1进栈,如右图所示。
接下来是“一”，所以将栈中的1出栈作为减数,3出栈作为被减数，并运算3-1得到2，再将2进栈，如左图所示。
接着是数字3进栈，如右图所示。
后面是“*”，也就意味着栈中3和2出栈,2与3相乘，得到6，并将6进
栈，如左图所示。下面是“+”，所以栈中6和9出栈,9与6相加，得到15,将15进栈，如右图所示。
接着是10与2两数字进栈,如左图所示。
接下来是符号“/”，因此，栈顶的2与10出栈，10与2相除，得到5，将5
进栈,如右图所示。
最后一个是符号“+”，所以15与5出栈并相加，得到20，将20进栈，如左图所示。
结果是20出栈,栈变为空，如右图所示。
果然，后缀表达法可以很顺利解决计算的问题。现在大家应该都有同样的疑问，就是这个后缀表达式“9 3 1 - 3 * + 10 2 / +”是怎么出来的?这个问题不搞清楚，等于没有解决。所以下面，我们就来推导如何让“9+(3-1) ×3+10÷2”转化为“9 3 1 - 3 * + 10 2 / +”。
3.3 中缀表达式转后缀表达式
我们把平时所用的标准四则运算表达式，即“9+(3-1) ×3+10÷2”叫做中缀表达式。因为所有的运算符号都在两数字的中间，现在我们的问题就是中缀到后缀的转化。
中缀表达式“9+(3-1)×3+10÷2”转化为后缀表达式“9 3 1 - 3 * + 10 2 / +”。
?规则:
从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分;若是符号，则判断其与栈顶符号的优先级，是右括号或优先级低于栈顶符号（乘除优先加减)则栈顶元素依次出栈并输出，并将当前符号进载，一直到最终输出后缀表达式为止。
- 初始化一空栈，用来对符号进出栈使用。如左图所示
- 第一个字符是数字9,输出9，后面是符号“+”，进栈。如右图所
示。
- 第三个字符是“(”，依然是符号，因其只是左括号，还未配对，故进栈。如左图所示。
- 第四个字符是数字3，输出，总表达式为9 3，接着是“-”，进栈。如右图所示。
- 接下来是数字1，输出，总表达式为9 3 1 ，后面是符号“)”，此时，我们需要去匹配此前的“(”，所以栈顶依次出栈，并输出，直到“(”出栈为止。此时左括号上方只有“-”，因此输出“-”。总的输出表达式为9 3 1-。如左图所示。
- 接着是数字3，输出，总的表达式为9 3 1 - 3。紧接着是符号“×”，因为此时的栈顶符号为“+”号，优先级低于“×”，因此不输出，“*”进栈。如右图所示。
- 之后是符号“+”，此时当前栈顶元素比这个“+”的优先级高，因此栈中元素出栈并输出（没有比“+”号更低的优先级，所以全部出栈)，总输出表达式为9 3 1 - 3 * +。然后将当前这个符号“+”进栈。也就是说，前6张图的栈底的“+”是指中缀表达式中开头的9后面那个“+”，而左图中的栈底(也是栈顶)的“+”是指“9+(3-1)×3+”中的最后一个“+”。
- 紧接着数字10，输出,总表达式变为931-3 *+10。后是符号“÷”，所以“/”进栈。如右图所示。
- 最后一个数字2，输出，总的表达式为9 3 1 - 3 * + 10 2。如左图所示。
- 因已经到最后，所以将栈中符号全部出栈并输出。最终输出的后缀表达式结果为:9 3 1 - 3 * + 10 2 / +。如右图所示。
从刚才的推导中你会发现，要想让计算机具有处理我们通常的标准（中缀）表达式的能力,最重要的就是两步:
- 将中缀表达式转化为后缀表达式(栈用来进出运算的符号)。
- 将后缀表达式进行运算得出结果(栈用来进出运算的数字)。