1. 栈（Stack）的概念

栈是一种线性表，它的结构可以类比于无盖容器，元素遵循“先进后出”的原则

例如：将12，23，34，45，56依次放入栈中，如图：

当需要取出栈中的元素中，需要依次取出最上面的元素，不能直接取出下面的元素。所以，该栈取出元素的顺序只能为：56，45，34，23，12

压栈： 栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈： 栈的删除操作叫做出栈。出数据在栈顶。

值得注意的是：压栈的过程中也可以进行出栈，即压栈和出栈可以交替进行

2. 栈（Stack）的实现

栈（Stack）既可以使用数组来实现，也可以使用链表来实现

2.1 用数组实现

用数组来实现栈需要创建三个文件：MyStack.java、EmptyStackException.java、Test.java。下面仅展示MyStack.java和EmptyStackException.java文件，Test.java测试文件不做展示

MyStack.java：

public class MyStack {
    public int[] elem;
    public int usedSize;

    public MyStack() {
        this.elem = new int[10];
    }

    //入栈
    public void push(int val) {
        if(isFull()) {
            //扩容
            elem = Arrays.copyOf(elem, 2*elem.length);
        }
        elem[usedSize++] = val;
    }

    public boolean isFull() {
        return usedSize == elem.length;
    }

    //出栈，会删除栈顶元素
    public int pop() {
        if(isEmpty()) {
            throw new EmptyStackException();
        }
        int val = elem[usedSize-1];
        usedSize--;
        return val;
    }
    //获取栈顶元素 但是不删除
    public int peek() {
        if(isEmpty()) {
            throw new EmptyStackException();
        }
        return elem[usedSize-1];
    }

    public boolean isEmpty() {
        return usedSize == 0;
    }
}

EmptyStackException.java：

public class EmptyStackException extends RuntimeException{
    public EmptyStackException() {
    }

    public EmptyStackException(String message) {
        super(message);
    }
}

其中，EmptyStackException.java是自定义异常，用于抛出空栈异常。

2.2 用链表实现

链表分为单链表和双链表，用哪个来实现好呢？其实两个都是可以的！

2.2.1 用单链表实现

假如用单链表实现时，当压栈（或者出栈）时，用采用头插（头删）还是尾插（尾删）呢？

• 若采用尾插和尾删，则每次都需要找到尾节点，就算用一个引用last标志尾节点，当尾删尾节点后，需要重新遍历链表找到尾节点，进而重新用last引用标记尾节点，这时的时间复杂度就是O(N)。
• 若采用头插和头删，每次只需将头节点head向前或向后移动就可以了，时间复杂度为O(1)。

综上可知，当采用单链表实现栈时，采用头插和头删更好！

3. leetcode刷题

3.1 括号匹配问题

题目链接：有效的括号

解题思路：

1. 遍历字符串，如果是左括号，放入栈中；如果是右括号，就与栈顶的元素比较看是否相同
2. 如果相同，则将栈顶元素弹出；不同则返回false
3. 再考虑左右括号数不相等的情况

代码如下：

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for(int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if(ch =='(' || ch == '[' || ch == '{') {
                stack.push(ch);
            }else {
                if(stack.isEmpty()) {
                    //左括号数少于右括号数的情况
                    return false;
                }
                char ch2 = stack.peek();
                if((ch2 == '(' && ch == ')') 
                || (ch2 == '[' && ch == ']') 
                || (ch2 == '{' && ch == '}')) {
                    stack.pop();
                } else {
                    return false;
                }
            }
        }
        if(!stack.isEmpty()){
            //左括号数多于右括号数的情况
            return false;
        }
        return true;
    }
}

3.2 栈的弹出压入序列

题目链接：JZ31 栈的压入、弹出序列

解题思路：

1. 分别遍历pushV数组和popV数组，依次将pushV数组中元素放入栈中，每次放入一个元素到栈中的同时，比较栈顶元素是否与数组popV当前元素是否相等，相等则弹出栈顶元素
2. 由于栈顶元素弹出后，新的栈顶元素可能与数组popV的下一个相等，因此需要循环比较
3. 当栈为空，且popV数组遍历完时，popV数组为pushV数组的一个弹出顺序

代码如下：

public boolean IsPopOrder (int[] pushV, int[] popV) {
        // write code here
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for(int i = 0; i < pushV.length; i++) {
            stack.push(pushV[i]);
            //注意循环的条件
            while(!stack.isEmpty() && j < popV.length && stack.peek() == popV[j]) {
                stack.pop();
                j++;
            }
        }
        if(stack.isEmpty() && j == popV.length) {
            return true;
        }
        return false;
    }

3.3 逆波兰表达式求值

中缀表达式和后缀表达式

在做这道题之前，我们需要了解什么是逆波兰表达式。逆波兰表达式又叫做后缀表达式，而我们平常所见到的表达式是一般都是中缀表达式，下面通过一个例子来讲解如何由中缀表达式得到后缀表达式

例： 中缀表达式a + bc+(de+f)g，其转换成后缀表达式则为abc+def+g+，演算过程如下图：

假如例子中a,b,c,d,e,f,g分别取1，2，3，4，5，6，7。由中缀表达式可以很容易求得该表达式的结果为189，那么怎么由后缀表达式求值呢？运用后缀表达式求值需要用到栈

后缀表达式求值规则： 从左往后，如果是数字，就将其放去栈中；如果是加减乘除符号，取出一个栈顶元素作为该符号的右操作数，再取出一个栈顶元素做为左操作数，计算得到的结果放入栈中，如此下去，最后栈中只会剩一个元素，这就是最终的结果

题目链接：150. 逆波兰表达式求值

解题思路：

1. 遍历字符串数组，判断是数字还是符号
2. 如果是数字，则将该数字转化为整型后，放入栈中
3. 如果是符号，取出栈顶元素作为右操作数，再取出一个栈顶元素作为左操作数，进行运算，得到的运算结果放入栈中
4. 最终栈中的元素即为后缀表达式的运算结果

代码如下：

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i < tokens.length; i++) {
            //判断是否为符号
            if(tokens[i].equals("+") 
            || tokens[i].equals("-") 
            || tokens[i].equals("*") 
            || tokens[i].equals("/")) {
                int val2 = stack.pop();
                int val1 = stack.pop();
                int result = 0;
                //进行运算操作
                switch(tokens[i]) {
                    case "+":
                        result = val1+val2;
                        break;
                    case "-":
                        result = val1-val2;
                        break;
                    case "*":
                        result = val1*val2;
                        break;
                    case "/":
                        result = val1/val2;
                        break;
                }
                //将运算结果放入栈中
                stack.push(result);
                continue;
            }
            int val = Integer.parseInt(tokens[i]);
            stack.push(val);
        }
        return stack.pop();
    }
}

计算机的工作原理也是这样的，将你输入的中缀表达式转化为后缀表达式，再按照后缀表达式的运算规则进行运算，得到结果！

3.4 最小栈

题目链接：155. 最小栈

解题思路：

1. 这道题想表达的意思是得到当前栈中的最小元素，而这个栈是可以压栈或出栈的，因此这个最小元素也是变化的
2. 想解决这道题，仅仅靠一个栈是不够的。需要创建两个栈，一个普通栈stack，一个最小栈minStack

入栈：

1. 普通栈是一定要放的，最小栈放的原则：1. 如果普通栈为空，则最小栈也要放；2.如果入栈元素小于最小栈的栈顶元素，则需要放
2. 这时就有一个问题了：如果入栈元素等于最小栈的栈顶元素，那么需要放吗？答案是需要的！因为当出栈时，普通栈的这个元素（即最小元素）出去时，最小栈的栈顶元素也同样需要出去。如果入栈的时候不放，那么在出栈后，得到的最小元素就可能不对了!举个例子：假设普通栈里有0，1，-1，-2，2，-2，那么对应最小栈里有0，-1，-2，-2，假如普通栈最后一个元素入栈时没有放入最小栈，那么最小栈里就只有0，-1，-2，而当后面出栈时，普通栈出去了-2，最小栈的栈顶元素也是-2，同样也需要出栈。出栈后最小栈里就只有0，-1了，就说明此时普通栈的最小元素为-1，而事实上普通栈的最小元素为-2，这互相矛盾了。因此当入栈元素等于最小栈的栈顶元素，需要放入最小栈

出栈：

1. 需要判断普通栈的出栈元素是否与最小栈的栈顶元素相等，相等则最小栈也需要出栈

代码如下：

class MinStack {
    public Stack<Integer> stack;
    public  Stack<Integer> minStack;
    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }
    
    public void push(int val) {
        stack.push(val);
        if(minStack.empty()) {
            minStack.push(val);
        }else {
            int peekVal = minStack.peek();
            if(val <= peekVal) {
                minStack.push(val);
            }
        }
    }
    public void pop() {
        if(stack.empty()) {
            return;
        }
        int popVal = stack.pop();
        if(popVal == minStack.peek()) {
            minStack.pop();
        }
    }
    
    public int top() {
        if(stack.empty()) {
            return -1;
        }
        return stack.peek();
    }
    
    public int getMin() {
        if(minStack.empty()) {
            return -1;
        }
        return minStack.peek();
    }
}

4. 栈、虚拟机栈、栈帧有什么区别？

栈是一种数据结构；虚拟机栈是JVM中的一块内存；当你运行一个方法，给这个方法开辟的内存叫做栈帧