了解栈Stack一篇文章就够了

1. 什么是栈

栈是一种特殊的线性表，只允许一端进行数据的插入和删除，即先进后出原则。类似于弹夹先装进去的子弹后面出，后放入的子弹先出。

2. 栈的底层原理

栈是一种线性结构，所以既能使用数组实现，也能使用链表实现，我就采用数组的方法实现一下栈

public class MyStack {public int[] elem;private static final int DEFAULT_CAPACITY = 10;public MyStack() {elem = new int[DEFAULT_CAPACITY];}//既能统计栈中存储多少个有效数据，也可以作为存放元素的下标public int usedSize;//压栈public void push(int val) {//先判满，如果满了要扩容if(isFull()) {elem = Arrays.copyOf(elem, elem.length * 2);}elem[usedSize] = val;usedSize++;}private boolean isFull() {return usedSize == elem.length;}//出栈public int pop() {//先判空，如果栈为空抛出异常if(empty()) {throw new EmptyArrayException("栈为空");}int val = elem[usedSize-1];usedSize--;return val;}private boolean empty() {return usedSize == 0;}//查看栈顶元素public int peek() {if(empty()) {throw new EmptyArrayException("栈为空");}return elem[usedSize-1];}//获取栈中有多少元素public int getUsedSize() {return usedSize;}
}

使用数组的实现方式，入栈只需要elem[usedSize] = data和出栈只需要usedSize--的时间复杂度都是O（1）。
如果使用单向链表，采用头插法入栈和出栈，只需要移动head头节点，时间复杂度也是O(1);要是采用尾插法入栈和出栈，入栈和出栈都需要从头节点出发，走到尾巴，才能完成元素的入栈或出栈，时间复杂度为O（n).
如果是双向链表，那么一个节点即知道后继节点，也知道前驱节点，有头节点head也有尾节点tail，采用头插法进行入栈和出栈只需要移动head头节点，采用尾插法进行入栈和出栈也是一样，只需要移动tail尾巴节点。

3. 栈的可能出栈顺序

题目：若入栈序列为1，2，3，4，进栈的过程中可以出栈，则下面不可能的出栈序列是哪个？

A.1,4,3,2 B.2,3,4,1 C.3,1,4,2 D.3,4,2,1
方法：按题目给的入栈顺序，结合选项，加画图（熟练以后不用画图）
A选项：第一个出栈是1，所以1进栈后出栈，2进栈，3进栈（因为出栈的第二个是4，所以2，3没有出栈），4进栈。4出栈，3出栈，2出栈。所以A是可能的出栈序列
B选项：B选项第一个出栈的是2，所以1进栈2进栈，2出栈，3进栈3出栈，4进栈4出栈，此时栈还剩1，1出栈。也是可能的出栈序列
C选项：你看C选项第一个出栈的是3，所以1，2，3都进栈，3再出栈，它第二个出栈的是1，但是此时栈顶元素是2，所以这是不可能的出栈顺序
D选项：第一个出栈的是3，所以要1，2，3都入栈了，3是栈顶元素才能出栈，接着4入栈，4又出栈，然后把栈中2出栈，1出栈

有关出栈顺序的oj题： https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?tpId=13&&tqId=11174&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking

public class Solution {public boolean IsPopOrder(int [] pushA, int [] popA) {Stack<Integer> stack = new Stack<>();int index = 0;//popA数组下标//遍历压栈pushA数组for (int i = 0; i < pushA.length; i++) {stack.push(pushA[i]);//如果栈顶元素和popA[index]相等//并且要防止栈为空（空指针异常）和数组越界//使用循环可能连着多个相等while (!stack.empty() && index < popA.length && stack.peek() == popA[index]) {stack.pop();index++;}}//如果是可能的出栈序列，那么栈中的元素能全部匹配，全部被弹出//如果栈不为空，说明是不可能的出栈序列return stack.empty();}
}

4. 中缀表达式转后缀表达式

题目1：中缀表达式：2+3*6的后缀表达式？

题目2 ：中缀表达式：（2+3）*5的后缀表达式

中缀转后缀，我们是加括号，然后把操作符移到对应括号后面，再去括号。同理，中缀转前缀，就是把操作符移到括号前面

5. 求后缀表达式/逆波兰表达式的计算结果

力扣Oj: https://leetcode.cn/problems/evaluate-reverse-polish-notation/

解决方法：使用栈，将数字放入栈中，如果碰到操作符，取出栈顶的2个元素，第一个取出的放操作符右边，第二个取出放操作符左边（固定的），计算完了再放入栈中，直到遍历完该字符串数组，此时栈中元素的值就是结果

class Solution {public int evalRPN(String[] tokens) {//等会要进行运算，类型用IntegerStack<Integer> stack = new Stack<>();//遍历数组for(String x: tokens) {//判断是不是数字字符串if(! isOperation(x)) {//如果是数字字符串，入栈stack.push(Integer.parseInt(x));//转为数字}else {//碰到操作符，出栈2个数int num1 = stack.pop();int num2 = stack.pop();//根据不同操作字符，进行运算,第一个弹出放操作符右边，第二个放左边//运算完后，重新入栈switch(x) {case "+" :stack.push(num2 + num1);break;case "-" :stack.push(num2 - num1);break;case "*":stack.push(num2 * num1);break;case "/" :stack.push(num2 / num1);break;} }}//此时栈中元素就是运算结果return stack.pop();}private boolean isOperation(String x) {//字符串比较不能使用==,==是比较地址，而不是比较值//字符串重写了Object类的equals()方法，是比较值的if(x.equals("+") || x.equals("-") || x.equals("*") || x.equals("/")) {return true;//如果是操作符返回真}return false;//不是返回假}
}