目录
一、栈(Stack)
1、概念
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据在栈顶。
在现实生活中，也有这样的例子，如猎枪的子弹，羽毛球筒里的羽毛球，都和栈一样后进先出。
（同样的，不一定是进一个出一个，顺序可以是随机的，根据需求来）
2、栈的使用
public static void main(String[] args) {
Stack<Integer> s = new Stack();
s.push(1);
s.push(2);
s.push(3);
s.push(4);
System.out.println(s.size()); // 获取栈中有效元素个数---> 4
System.out.println(s.peek()); // 获取栈顶元素---> 4
s.pop(); // 4出栈，栈中剩余1 2 3，栈顶元素为3
System.out.println(s.pop()); // 3出栈，栈中剩余1 2 栈顶元素为3
if(s.empty()){
System.out.println("栈空");
}else{
System.out.println(s.size());
}
}3、栈的模拟实现
从上图中可以看到，Stack继承了Vector，Vector和ArrayList类似，都是动态的顺序表，不同的是Vector是线程安全的。（线程安全会在后面的EE进阶里面讲到）
public class MyStack {
int[] array;
int size;
public MyStack(){
array = new int[3];
}
public int push(int e){
ensureCapacity();
array[size++] = e;
return e;
}
public int pop(){
int e = peek();
size--;
return e;
}
public int peek(){
if(empty()){
throw new RuntimeException("栈为空，无法获取栈顶元素");
}
return array[size-1];
}
public int size(){
return size;
}
public boolean empty(){
return 0 == size;
}
private void ensureCapacity(){
if(size == array.length){
array = Arrays.copyOf(array, size*2);
}
}
}4、栈的应用场景（练习）
（多练！！！多练！！！多练！！！）
4.1将递归转化为循环
如：逆序打印链表
// 递归方式
void printList(Node head){
if(null != head){
printList(head.next);
System.out.print(head.val + " ");
}
}
// 循环方式
void printList(Node head){
if(null == head){
return;
}
Stack<Node> s = new Stack<>();
// 将链表中的结点保存在栈中
Node cur = head;
while(null != cur){
s.push(cur);
cur = cur.next;
}
// 将栈中的元素出栈
while(!s.empty()){
System.out.print(s.pop().val + " ");
}
}4.2括号匹配
这题就可以通过栈的形式解决问题，首先判断字符串的长度，若是奇数则直接返回false。接着创建一个哈希表，用来存储每一种括号。哈希表的键为右括号，值为相同类型的左括号。
创建一个栈，将字符依次放入栈，放入前与栈顶进行比较，若是构成一对则弹出栈顶，这个字符也不用入栈，直接跳过。循环执行，直到遍历完整个字符串。再去判断栈是否为空，若为空则有效。
class Solution {
public boolean isValid(String s) {
int n = s.length();
if (n % 2 == 1) {
return false;
}
Map<Character, Character> pairs = new HashMap<Character, Character>() {{
put(')', '(');
put(']', '[');
put('}', '{');
}};
Deque<Character> stack = new LinkedList<Character>();
for (int i = 0; i < n; i++) {
char ch = s.charAt(i);
if (pairs.containsKey(ch)) {
if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
return false;
}
stack.pop();
} else {
stack.push(ch);
}
}
return stack.isEmpty();
}
}4.3逆波兰表达式求值
（150. 逆波兰表达式求值 - 力扣（LeetCode））
逆波兰表达式也可以称作后缀算术表达式。举个简单的例子：
((2 + 1) * 3) = 9这是我们常见的表达式，其实这就是中缀表达式，我们将运算符移动到向外一层的括号后面，得到"2","1","+","3","*"这和起来就是后缀表达式，用后缀表达式就可以借助栈求解了。
我们直接创建一个栈，将所有的字符循环放进栈中，若是数字就依次堆叠，若是符号就在栈顶弹出两个数进行运算，并将运算结果重新放到栈顶。往复循环，直到遍历完整个数组，这是栈顶就是结果（此时栈内只有一个元素了）
class Solution {
public int evalRPN(String[] tokens) {
Deque<Integer> stack = new LinkedList<Integer>();
int n = tokens.length;
for (int i = 0; i < n; i++) {
String token = tokens[i];
if (isNumber(token)) {
stack.push(Integer.parseInt(token));
} else {
int num2 = stack.pop();
int num1 = stack.pop();
switch (token) {
case "+":
stack.push(num1 + num2);
break;
case "-":
stack.push(num1 - num2);
break;
case "*":
stack.push(num1 * num2);
break;
case "/":
stack.push(num1 / num2);
break;
default:
}
}
}
return stack.pop();
}
public boolean isNumber(String token) {
return !("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token));
}
}4.4出栈入栈次序匹配
这题的思路其实很明确，想要判断出栈入栈匹配，只需要创建一个栈，进行入栈操作，同时和出栈序列进行比较，相同则出栈。最后返回stack.empty()（这个方法，如果栈为空，就返回true，不为空返回false）
public boolean IsPopOrder(int [] pushV,int [] popV) {
Stack<Integer> stack = new Stack<>();
int j = 0;
for(int i = 0; i< pushV.length;i++) {
stack.push(pushV[i]);
while(!stack.empty() && j < popV.length &&
stack.peek() == popV[j]) {
stack.pop();
j++;
}
}
return stack.empty();
}4.5最小栈
对于栈来说，如果一个元素 a 在入栈时，栈里有其它的元素 b, c, d，那么无论这个栈在之后经历了什么操作，只要 a 在栈中，b, c, d 就一定在栈中，因为在 a 被弹出之前，b, c, d 不会被弹出。
因此，在操作过程中的任意一个时刻，只要栈顶的元素是a，那么我们就可以确定栈里面现在的元素一定是 a, b, c, d。
那么，我们可以在每个元素 a 入栈时把当前栈的最小值 m 存储起来。在这之后无论何时，如果栈顶元素是 a，我们就可以直接返回存储的最小值 m.
按照上面的思路，我们可以使用一个辅助栈，与元素栈同步插入与删除，用于存储与每个元素对应的最小值。
当一个元素要入栈时，我们取当前辅助栈的栈顶存储的最小值，与当前元素比较得出最小值，将这个最小值插入辅助栈中；
当一个元素要出栈时，我们把辅助栈的栈顶元素也一并弹出；
在任意一个时刻，栈内元素的最小值就存储在辅助栈的栈顶元素中。
class MinStack {
Deque<Integer> xStack;
Deque<Integer> minStack;
public MinStack() {
xStack = new LinkedList<Integer>();
minStack = new LinkedList<Integer>();
minStack.push(Integer.MAX_VALUE);
}
public void push(int x) {
xStack.push(x);
minStack.push(Math.min(minStack.peek(), x));
}
public void pop() {
xStack.pop();
minStack.pop();
}
public int top() {
return xStack.peek();
}
public int getMin() {
return minStack.peek();
}
}5、概念区分
栈、虚拟机栈、栈帧有什么区别呢？
