数据结构：栈

特点

先进后出（FILO）后进先出（LIFO）

现在我有一个栈，栈顶不封顶，可以将元素加进来，但是栈底是封闭的，元素没办法溜走栈底 

把元素加进去，想要把12拿出来的时候，必须让23和34分别出来，12才能从栈底脱身

手搓一个栈

我们先用数组来实现一个栈，它的时间复杂度是O(1)

🆗了解了这些方法之后，我们把这些方法写到接口里面

//IStack 接口
package stack;
 
public interface IStack {
    void push(int x);
 
    int pop();
 
    int peek();
 
    int size();
 
    boolean empty();
 
    boolean full();
}

在具体实现的文件里面实现方法

package stack;
 
public class MyStack implements IStack{
    //初始化
    private int[] elem;
    private int usedSize;
    private static final int DEFAULT_CAPACITY = 10;
    public MyStack(){
        elem = new int[DEFAULT_CAPACITY];
    }
    @Override
    public void push(int x) {
 
 
    }
 
    @Override
    public int pop() {
        return 0;
    }
 
    @Override
    public int peek() {
        return 0;
    }
 
    @Override
    public int size() {
        return 0;
    }
 
    @Override
    public boolean empty() {
        return false;
    }
 
    @Override
    public boolean full() {
        return false;
    }
}

push 压栈

压栈之前首先要判断栈是不是满的

    @Override
    public boolean full() {
        if(usedSize == elem.length){
            return true;
        }
        return false;
    }

满了的话就需要扩容，然后把数组对应位置放入值x就行

    @Override
    public void push(int x) {
        if (full()){
            elem = Arrays.copyOf(elem, 2* elem.length);
        }
        elem[usedSize] = x;
        usedSize++;
    }

pop出栈

弹出元素需要先判断栈内为不为空

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

如果为空了，可以抛一个异常

        if(empty()){
            throw new EmptyException("栈空了！")
        }
//重新写一个文件反馈异常
public class EmptyException extends RuntimeException{
    public EmptyException(String msg){
        super(msg);
    }
}

删除元素 --》usedSize--  就行了

    @Override
    public int pop() {
        if(empty()){
            throw new EmptyException("栈空了！")
        }
        int old = elem[usedSize-1];
        usedSize--;//相当于删除元素
        return old;
    }

peek和size

    @Override
    public int peek() {
        return elem[usedSize-1];
    }
 
    @Override
    public int size() {
        return usedSize;
    }

用链表实现一个栈

如果是单链表，我们没有last这个引用

假设从头入栈-》O(1)，从头出：删除头节点 -》O(1)

假设从尾巴入栈 --》 O(n)   从尾巴出--》O(n)

如果是双向链表，可以直接当成一个栈，叫做链式栈

有关栈的题目和应用

开胃小菜

answer：C

要先弹出3，栈里面必然有1和2，然而当3弹出来后，1被2挡着，不可能比2更快弹出

所以C就是不对的

看看B

1和2先入栈，2先出栈，再入栈3，3出栈，再入栈4，4出栈，最后1出栈

顺序就是2，3，4，1

3.应用栈来逆序打印链表

循环方法

用一个cur遍历链表，每次遍历一个元素就加入栈中，把元素一一出栈，出栈的过程中顺便打印

递归方法

比循环多这么一步：每次入栈就调用一次自己的方法

    // 递归方式
    void printList(Node head){
        if(null != head){
            printList(head.next);
            System.out.print(head.val + " ");
        }
    }
    // 循环方式
    void printList(Node head){
        if(null == head){
            return;
        }
        Stack s = new Stack<>();
// 将链表中的结点保存在栈中
        Node cur = head;
        while(null != cur){
            s.push(cur);
            cur = cur.next;
        }
        // 将栈中的元素出栈
        while(!s.empty()){
            System.out.print(s.pop().val + " ");
        }
    }

输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
输出：22
解释：该算式转化为常见的中缀算术表达式为：
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

什么叫做逆波兰表达式

逆波兰表达式是一种后缀表达式

我们平常写的算式是中缀表达式 比如：9+(3-1)*3+8/2

改成后缀表达式就是 9 3 1 - 3 * + 8 2 / +

中缀怎么变后缀的呢？

我们的中缀表达式遵循先乘除后加减的原则

我们就先给乘除操作加上一个括号

9先加上乘法的结果，再给他们俩一个括号

最后整个加在一起，再给整体一个括号

现在把每个运算符移到对应括号的外边，注意只用移动一层就行

然后把所有的括号删掉就是后缀表达式了

9 3 1 - 3 * + 8 2 / +

那后缀表达式怎么运行/计算的呢？

1.把符号前面数字扔到栈里面，符号不要扔进去！

2.现在栈里面有9，3和1，把先弹出来的1放到减号的右边，紧接着弹出来的3放到减号左边

3.3-1 = 2 把这个计算得出的2再压回栈中

现在栈里面长这样

4.再把3扔进去

5.弹出3放*右边，弹出2放*左边，计算得到的6再压入栈里面

6.加号放栈外边，依次弹出6和9，计算得到15再压入栈

7.把8和2依次压入栈，然后2和8依次弹出分别放除号右边和左边 

8.计算得到4再压回栈里

现在栈的情况

最后把这俩依次弹出放到+右边和左边再进行计算得到19，这个19就是最终的答案啦

🆗了解了后缀表达式怎么计算，那我们回到题目

这道题就是要我们用代码实现上面的过程

第一步：我们把数字(Integer)压入栈中，同时要设计一个方法判断是不是Integer

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

        Stack stack = new Stack<>();
        for(String x:tokens){
            if(!isOperation(x)){
                stack.push(Integer.parseInt(x));//字符串转整型

第二步：处理四个字符串

            else{
                int num2 = stack.pop();
                int num1 = stack.pop();//注意先弹出num2,方便后面把num2放到右边
                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;
                }
            }

第三步：把最终的计算结果pop出来就行

整个的代码

class Solution {
    public int evalRPN(String[] tokens) {
        Stack stack = new Stack<>();
        for(String x:tokens){
            if(!isOperation(x)){
                stack.push(Integer.parseInt(x));//字符串转整型
            }else{
                int num2 = stack.pop();
                int num1 = stack.pop();//注意先弹出num2,方便后面把num2放到右边
                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 isOperation(String s){
        if(s.equals("+") || s.equals("-")||s.equals("*")||s.equals("/")){
            return true;
        }
        return false;
    }
}

20. 有效的括号 - 力扣（LeetCode） 

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = "()"
输出：true

示例 2：

输入：s = "()[]{}"
输出：true

示例 3：

输入：s = "(]"
输出：false

提示：

• 1 <= s.length <= 104
• s 仅由括号 '()[]{}' 组成

 括号不匹配的情况（我们只需要解决的情况）

遇到的第一个右括号应该和最后一个左括号进行匹配，所以我们要用到栈

先把左括号入栈，遇到右括号的时候和栈顶元素的左括号比较是不是匹配的，每匹配一个就pop一个

当栈里面的元素为空且字符串也遍历完成时，匹配完成

情况1：

情况2：

情况3：

完整的代码

栈的压入、弹出序列_牛客题霸_牛客网 (nowcoder.com) 

描述

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。

1. 0<=pushV.length == popV.length <=1000

2. -1000<=pushV[i]<=1000

3. pushV 的所有数字均不相同

示例1

输入：

[1,2,3,4,5],[4,5,3,2,1]

返回值：

true

说明：

可以通过push(1)=>push(2)=>push(3)=>push(4)=>pop()=>push(5)=>pop()=>pop()=>pop()=>pop()
这样的顺序得到[4,5,3,2,1]这个序列，返回true      

示例2

输入：

[1,2,3,4,5],[4,3,5,1,2]

返回值：

false

说明：

由于是[1,2,3,4,5]的压入顺序，[4,3,5,1,2]的弹出顺序，要求4，3，5必须在1，2前压入，且1，2不能弹出，但是这样压入的顺序，1又不能在2之前弹出，所以无法形成的，返回false      

我们设置两个数组，一个是压栈的数组，一个是用来判断的数组

设置i遍历push里面的元素，每次遍历一个元素看超不超过pop里面的j位置的元素的大小

设置j遍历pop里面的元素，遍历一个就看看与栈里面元素是不是一样的，一样的就把栈里面对应元素pop出来

 如图，pop第一个元素是4，那么push里面1 2 3 4可以直接push到栈里面，4一样，弹出，再把5push进去，j往后走。5一样，弹出。再依次比较3 2 1

push和栈都是空的，说明匹配完成

归纳步骤:

1.遍历push数组，把元素放入栈中

        Stack stack = new Stack<>();
        int j = 0;
        for(int i = 0; i < pushV.length; i++){
            stack.push(pushV[i]);

2.每push一个元素，就和pop数组的元素比较

3.如果相等，j++且出栈（注意：这么做的前提是栈不为空且数组不越界）

4.如果不相等，就想办法入栈

            while(!stack.empty() && j < popV.length && stack.peek() == popV[j]){
                stack.pop();
                j++;
            }

完整代码

155. 最小栈 - 力扣（LeetCode）

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

实现 MinStack 类:

• MinStack() 初始化堆栈对象。
• void push(int val) 将元素val推入堆栈。
• void pop() 删除堆栈顶部的元素。
• int top() 获取堆栈顶部的元素。
• int getMin() 获取堆栈中的最小元素。

示例 1:

输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

 这道题只用一个栈是明显行不通的

假设有这么一组数，-1，2，6，3，依次入栈，想要最快拿到最小值-1就得经过O(n)时间，不合题意

所以我们可以申请两个栈，一个栈就是普通的栈，用来放列表的元素的

另一个栈就是最小栈，每次放入普通栈的元素都要和原来栈里面的元素进行比较，如果是最小的话就放入最小栈，放到最后你会发现，最小栈的栈顶就是那个最小值

初始化

    private Stack stack;
    private Stack minStack;
    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }

push

普通的栈一定得放元素

最小栈如果是空的，也要放；如果不为空且要存放的元素小于最小栈的栈顶，也要放到最小栈

    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);
            }
        }
    }

pop

1.要pop的元素和栈顶元素比较

2.如果pop的元素和栈顶元素是一样的，那么两个栈都要出

3.不一样只出普通栈

    public void pop() {
        int val = stack.pop();
        if(!minStack.empty()){
            if(val == minStack.peek()){
                minStack.pop();
            }
        }
    }

top和getMin

    //peek获取当前普通栈的栈顶元素
    public int top() {
        return stack.peek();
    }
    //最小栈的peek，通过这个方法获取最小值
    public int getMin() {
        if(!minStack.empty()){
            return minStack.peek();
        }
        return -1;
    }

概念区分

栈、虚拟机栈、栈帧的区别

栈：一种数据结构

虚拟机栈：JVM划分的一块内存

栈帧：调用方法的时候会在虚拟机当中给这块方法开辟一块内存