栈
概念
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中数据元素遵守先进后出的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶
出栈：栈的删除操作叫做出栈。出数据在栈顶
通俗的讲栈其实就是一种数据结构，特点是：先进后出
此时
JVM stack只是JVM当中的一块内存，该内存一般用来存放例如：局部变量
调用函数的时候，我们会为这个函数开辟一块内存，叫做栈帧，在哪里开辟那？
JVM stack
什么是栈帧：
就是程序在调用方法的时候，为方法开辟的内存
使用刚刚的概念特点：
看几个题来了解栈到底是怎么实现的。
我们可以想每个输出序列的第一个元素应该是输入的最后一个，因为栈的特点是先进后出
A选项
所以出栈序列可以是A选项
B 选项
选项中第一个出现的是d说明一口气入栈到d，先让d出栈，然后在让e入栈在出栈，最后按照顺序出栈就可以
后面选项都一样，不再一 一列举
再看看这个题，加深理解
Stack中的方法
拓展
中缀表达式转后缀表达式
如图就是一个中缀表达式
我们要把它转为后缀表达式，方式：
我们把每个括号里的运算符放到括号外边
后边变为：
只要将将数字放到栈里，碰到运算符计算，将计算后的数字放进栈里就可以了
后缀表达式又叫逆波兰表达式
逆波兰表达式：
逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。
平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。
逆波兰表达式主要有以下两个优点：
去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中
思路
1.判断是否是运算符
2.如果不是就将字符变为数字放入栈中
3.如果是运算符就将两个数字运算
4.运算后的数字继续放入栈中，
5.重复以上操作直到数组为空
代码如下
import java.util.Stack; class Solution { public boolean check(String str) { String ch = str; if(ch.equals("+") || ch.equals("-") || ch.equals("*") || ch.equals("/")) { return true; } return false; } public int evalRPN(String[] tokens) { Stack<Integer> stack = new Stack<>(); for(int i = 0; i < tokens.length; i ++) { if(! check(tokens[i])) { stack.push(Integer.parseInt(tokens[i])); }else { int result = 0; int num2 = stack.pop(); int num1 = stack.pop(); switch(tokens[i]) { case "+" : result = num1 + num2; stack.push(result); break; case "-" : result = num1 - num2; stack.push(result); break; case "*" : result = num1 * num2; stack.push(result); break; case "/" : result = num1 / num2; stack.push(result); break; } } } return stack.pop(); } }
题目的大意是输入两个整数序列，第一个序列是栈的压入顺序，第二个是弹出顺序，判断是不是
这题大致思路，就像我们之前在概念中做的题目一样，首先找到出栈序列的第一个，如果后面的相同，就弹出，如果不同的话，将第一个入栈顺序继续加判断是否相同，到最后判断辅助栈是否为空就可以了
import java.util.*; import java.util.ArrayList; public class Solution { public boolean IsPopOrder(int [] pushA,int [] popA) { Stack<Integer> stack = new Stack<Integer>(); int j = 0; for(int i = 0; i < pushA.length; i ++) { stack.push(pushA[i]); while(j < popA.length && !stack.empty() && stack.peek() == popA[j]) { stack.pop(); j ++; } } return stack.empty(); } }
我们使用的栈底层是个数组，那么请问能不能用单链表来实现？
1.先进后出
2.入栈和出栈的时间复杂度都是O(1)
因为链表可以头插也可以尾插，那么入栈使用头插法还是尾插法？
假设：入栈是尾插法那么时间复杂度就是O(n）了，因为尾插法每次都要找尾巴
假设：入栈是头插法，时间复杂度就是O(1)，出栈的时候，出栈的时候只需要删除头结点就好了时间复杂度也是O(1)
因为是单链表虽然最后一个节点我知道是那个，但是它的前一个我就不知道了。还要遍历去找这个节点的前驱，时间复杂度又是O(n)了
,使用双链表来实现一个栈，这样完全可以。
还有两个栈的问题：
