【数据结构（五）】栈

❣博主主页: 33的博客❣
▶️文章专栏分类:数据结构◀️
🚚我的代码仓库: 33的代码仓库🚚
🫵🫵🫵关注我带你学更多数据结构知识

在这里插入图片描述

1.前言

最近淄博烧烤的热度很大啊，同学们想去淄博吃吃烤串吗?那想一想，在我们串肉的时候，最先串上的肉，是不是最后在被我们吃到呢？其实这就是日常生活在的一个“栈”，在数据结构中栈又是什么样子的呢？接下来，博主将详细介绍栈的相关知识。

2.概念

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

3.栈的使用

在这里插入图片描述
注意
pop（）与peek（）的区别：pop是将栈顶元素出栈，peek只是瞄一眼并不出栈

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

4.栈的应用场景

例1：
若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（）
A: 1,4,3,2 B: 2,3,4,1 C: 3,1,4,2 D: 3,4,2,1
答案：C，1、2、3入栈以后，3再出栈，此时栈顶为2，只能出2，不能出

4.1有效的括号

给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效:OJ链接

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;
            }
            if(ch=='}'&&stack.peek()=='{'||ch==')'&&stack.peek()=='('||ch==']'&&stack.peek()=='['){
                stack.pop();
            }else{
                return false;
            }
            }        
        }
        if(!stack.isEmpty()){
                return false;
            }
        return true;  
    }

4.2逆波兰表达式

给你一个字符串数组 tokens ，表示一个根据逆波兰表示法表示的算术表达式。
请你计算该表达式：OJ链接

 public int evalRPN(String[] tokens) {
        Stack<Integer> stack=new Stack<>();
        for (String X:tokens){
            if(!isOperation(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.peek();
    }

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

4.3栈的压入弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序：OJ链接
解题思路：

假设入栈顺序是：[1,2,3,4,5],出栈顺序是：[4,3,5,1,2]
每次入栈一个元素后检查栈顶元素，和出栈的元素进行比较，如果相同，那么此元素出栈。
如果结束后，栈内依然有元素，那么第二个序列是否可能为该栈的弹出顺序。

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.isEmpty()&&j<popV.length&&popV[j]==stack.peek()){
                stack.pop();
                j++;
            }
        }
        return stack.isEmpty();
    }

4.4最小栈

设置一个最小栈，并能在常数时间内检索到最小元素的栈：OJ链接
解题思路

创建两个栈，一个用于存放所有元素，一个用于存放最小元素，
入栈时，把入栈元素和最小栈的栈顶元素m进行比较，如小于或等于m，则也存入最小栈
出栈时，把出栈元素与m比较，如果相同则最小栈也出栈。

public class MinStack {
    Stack<Integer> minStack;
    Stack<Integer> stack;
    public MinStack() {
       minStack =new Stack<>();
       stack=new Stack<>();
    }
    void push(int val){
        stack.push(val);
        if(minStack.isEmpty()){
            minStack.push(val);
        }else {
            if (val<=minStack.peek()){
                minStack.push(val);
            }
        }
    }
    void pop(){
        int a=stack.pop();

        if(!minStack.isEmpty()&&a==minStack.peek()){
            minStack.pop();
        }
    }
    int top(){
        return stack.peek();
    }
    int getMin(){
        if(!minStack.isEmpty()){
            return minStack.peek();
        }
        return -1;
    }
}