1. 概念

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据在栈顶。

栈在现实生活中的例子：

2. 栈的使用

方法	功能
Stack()	构造一个空的栈
E push(E e)	将e入栈，并返回e
E pop()	将栈顶元素出栈并返回
E peek()	获取栈顶元素
int size()	获取栈中有效元素个数
boolean empty()	检测栈是否为空

3. 栈的模拟实现

那么，集合类栈的底层是怎么存储的呢？
栈是属于线性结构的，线性结构存储要么是顺序存储要么是链式存储。
查看源码，我们发现Stack类中没有定义成员变量？回忆之前继承的内容，我们不难想到，成员变量一定是从父类继承下来了，呢我们再去查看父类Vector的源码：

由此我们可知，集合类栈的底层是顺序存储的。

从上图中可以看到，Stack继承了Vector，Vector和ArrayList类似，都是动态的顺序表，不同的是Vector是线程安全的。

import java.util.Arrays;

public class MyStack {
    public int[] elem;
    public int usedSize;
    public static final int DEFAULT_SIZE = 10;

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

    /**
     * 压栈
     * @param val
     * @return
     */
    public int push(int val){
        if(isFull()){
            elem = Arrays.copyOf(elem,2*elem.length);
        }
        elem[usedSize] = val;
        usedSize++;
        return val;
    }

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

    public int pop(){
        if(empty()){
            throw new MyEmptyStackException("栈为空！");
        }
        // int ret = elem[usedSize-1];
        // usedSize--;
        // return ret;
        return elem[--usedSize];
    }

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

    public int peek(){
        if (empty()){
            throw new MyEmptyStackException("栈为空！");
        }
        return elem[usedSize-1];    // 区分--usedSize
    }

}

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

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

public class Test {
    public static void main(String[] args) {
        MyStack myStack = new MyStack();
        myStack.push(1);
        myStack.push(2);
        myStack.push(3);
        myStack.push(4);

        int x1 = myStack.pop();
        System.out.println(x1);
        int x2 = myStack.peek();
        System.out.println(x2);
        int x3 = myStack.peek();
        System.out.println(x3);
    }
}

4. 栈的应用场景

1.改变元素的序列

2.将递归转化为循环

递归方式打印链表：

非递归：

3.括号匹配
OJ链接

所以，并不可以通过括号个数来判断是否匹配。
思路：
遍历字符串，如果是左括号就压栈；如果是右括号就从栈里弹出，然后看两括号是否匹配。
最后如果字符串遍历完成，栈也是空的，则匹配。

代码实现：

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.empty()){
                    // 错误1：遇到了右括号，但此时栈为空，不匹配
                    return false;
                }
				char ch2 = stack.peek();
                // 此时，如果满足下面的任何一个匹配逻辑，都是匹配的
                if(ch2 == '(' && ch == ')' || ch2 == '[' && ch == ']' || ch2 == '{' && ch == '}'){
                    stack.pop();
                // 错误2：逻辑不匹配
                }else{
                    return false;
                }
            }
        }
        // 错误3：字符串遍历完成了，但是栈不为空，不匹配
        if(!stack.empty()){
            return false;
        }
        return true;
    }
}

4.后缀表达式（逆波兰表达式）
OJ链接

例如在实现计算器时，我们一定是需要把中缀表达式转换为后缀表达式再进行计算的。
总结中缀转后缀方法：

将所有计算按优先级加括号；
将所有运算符移动到括号后面；
去括号。

那么若给出一个后缀表达式，该怎么计算呢？

遇到数字入栈；
遇到运算符出栈顶2个元素：第一个是右操作数，第二个是左操作数；
计算结果入栈，接着进行表达式入栈。

OJ链接
代码实现：

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack= new Stack<>();

        // 遍历tokens数组，判断当中字符串的类型
        for(String x : tokens){
            if(!isOperations(x)){
                stack.push(Integer.parseInt(x));
            }else{
                int num2 = stack.pop();
                int num1 = stack.pop();
                switch(x){
                    case "+":
                        stack.push(num1+num2);
                        break;
					case "-":
                        stack.push(num1-num2);
                        break;
                    case "*":
                        stack.push(num1*num2);
                        break;
                    case "/":
                        stack.push(num1/num2);
                        break;
				}
            }
        }
        return stack.pop();
    }

    private boolean isOperations(String s){
        if(s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")){
            return true;
        }else{
            return false;
        }
    }

}

5.出栈入栈次序匹配
OJ链接

思路：
1.i下标遍历PushAs数组，直接入栈。
2.入栈之后判断j下标是不是当前栈顶的元素。
3.如果是则弹出栈顶元素，且j++ 。然后循环进行2、3步骤。
4.如果不是则继续i++即可。

当栈中最后还剩下元素的时候就说明这是不匹配的出栈序列。

代码实现：

import java.util.*;

public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        Stack<Integer> stack = new Stack<>();
        int j = 0;   // 遍历popA数组
        for(int i = 0;i < pushA.length;i++){
            stack.push(pushA[i]);
            while(j < popA.length && !stack.empty() && stack.peek().equals(popA[j])){
                stack.pop();
                j++;
            }
        }
        return stack.empty();
    }
}

6.实现最小栈
OJ链接

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
思路：

代码实现：

class MinStack {

    private Stack<Integer> stack1;
    private Stack<Integer> minStack;

    public MinStack() {
        stack1 = new Stack<>();
        minStack = new Stack<>();
    }
    
    public void push(int val) {
        stack1.push(val);
        if(minStack.empty()){
            minStack.push(val);
		}else{
            if(val <= minStack.peek()){
                minStack.push(val);
            }
        }
    }
	public void pop() {
        if(!stack1.empty()){
            int x = stack1.pop();
            if(x == minStack.peek()){
                minStack.pop();
            }
        }
    }
    
    public int top() {
        if(!stack1.empty()){
            return stack1.peek();
        }else{
            return -1;   // 不要抛异常
        }
    }
    
	public int getMin() {
        if(minStack.empty()){
            return -1;
        }
        return minStack.peek();
    }
}

5. 概念区分

栈、虚拟机栈、栈帧有什么区别呢？
栈：是一种先进后出的数据结构。
虚拟机栈： 是JVM的一块内存空间
栈帧： 是在调用函数的过程当中，在Java虚拟机栈上开辟的一块内存。
顺序栈和链式栈？
目前实现的栈，底层是数组实现，所以也可以叫做顺序栈。请问，由单链表来实现栈是否可以？
当然可以：