目录

1，栈的相关理解

2，栈的应用

一，栈的相关理解

概念：

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

栈的相关方法：

方法名	功能作用	备注
push()	入栈，将元素添加到栈顶	栈结构新增元素
pop()	出栈，删除并返回栈顶元素	栈空会报错 / 返回 null
peek() / top()	取栈顶，只查看不删除元素	不改变栈结构
isEmpty()	判断栈是否为空	空返回 true，非空 false
size()	获取栈中元素总个数	返回整数
clear()	清空栈中所有元素	重置为空栈
search()	查找元素，返回距栈顶位置	找不到返回 - 1
contains()	判断栈是否包含指定元素	存在返回 true

栈的应用及相关题目

1，顺序问题

答：问题一选C，因为当你要3在开头的话，就先放123，然后拿出3，不过3的后一个就得是栈顶端的2或者还没放进去的4了，不可能为1；问题二选B，B就是简单的从顶部往外拿

2，逆序打印

因为栈是先进后出，所以可以运用栈来实现逆序打印

import java.util.LinkedList;
import java.util.Stack;
public class Test {
    public static void main(String[] args) {
        LinkedList<Integer> linkedList1=new LinkedList<>();
        linkedList1.add(1);
        linkedList1.add(2);
        linkedList1.add(3);
        System.out.println(linkedList1);
        change(linkedList1);
    }
    public static void change(LinkedList<Integer> linkedList){
        Stack<Integer> stack=new Stack();
        for (int i = 0; i < linkedList.size(); i++) {
            stack.push(linkedList.get(i));
        }
        while (!stack.empty()){
            int a = stack.pop();
            System.out.print(a+" ");
        }

    }
}

打印结果就是[1, 2, 3]和3 2 1

3，有效的括号

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

我们判断是否有效的话就可以通过比较最后一个左括号和第一个右括号是不是相等，那怎么拿到最后一个左括号呢，我们就可以通过栈，因为栈先进后出，就可以拿到最后一个，具体做法就是将字符串一个一个拿出来放在字符ch里面，然后遍历一遍所有括号，将左边的括号放进栈里面，有右括号的时候将栈里面的左括号拿出来比较，如果一样的话就从栈里面拿走，然后继续遍历，当然全是右括号直接就可以判断为假，只要判断栈是不是空就行，其他的具体看看代码来理解

class Solution {
    public boolean isValid(String s) {
           Stack<Character> stack=new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char ch1 = s.charAt(i);
            if (ch1=='(' ||ch1=='[' ||ch1=='{'){
                stack.push(ch1);
            }
            //这是右边的括号
            else {
                if (stack.empty()){
                    return false;
                }
                char ch2=stack.peek();
                if ((ch2=='('&&ch1==')')||(ch2=='['&&ch1==']')||(ch2=='{'&&ch1=='}')){
                    stack.pop();
                }else {
                    return false;
                }
            }
        }
        if (stack.empty()){
            return true;
        }
        return false;
    }
}

4,判断出栈顺序

栈的压入、弹出序列_牛客题霸_牛客网

这题的意思就是跟顺序问题一样，但是需要你代码来实现，我们可以这样来理解，我们将pushV数组的数据通过和popV的比较，不一样的就先放在栈里面，一样的再拿出来，如果最终pushV放完了，并且栈里面也空了，说明都匹配上了，就返回true，具体看代码来理解

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pushV int整型一维数组
     * @param popV int整型一维数组
     * @return bool布尔型
     */
    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.empty() && j < popV.length && popV[j] == stack.peek()) {
                j++;
                stack.pop();
            }
        }
        if (stack.empty()) {
            return true;
        }
        return false;
    }
}

5，逆波兰表达式

150. 逆波兰表达式求值 - 力扣（LeetCode）

前缀知识：我们有三种表达式，分别为前缀，中缀，以及后缀，中缀就是我们平时写的表达式，比如1+1,2*3，前缀又称波兰表达式，后缀为逆波兰，通过名字就知道前和后是有点相反的，前缀是将符号写在数字前面，后缀是写在后面，这种写法不是机器语言，但专门给计算机、给计算器、给编译器设计的 “友好表达式写法”。具体的写法如下：

这是我们平时自己做题的时候的写法，这种的做法就是运用栈来实现

具体来看看题目：

在遇到运算符前，我们先将数字放入栈里面，然后遇到运算符，我们将栈顶的元素和栈顶下面一个元素分别拿出，栈顶的在运算符右边，另外一个在左边，这不能搞反，可以自己验证一下，具体实现看代码

  public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (String s : tokens) {
            if (!(s.equals("+") || s.equals("*") || s.equals("/") || s.equals("-"))) {
                stack.push(Integer.parseInt(s));

            } else {
                Integer val2 = stack.pop();
                Integer val1 = stack.pop();
                switch (s) {
                    case "+":
                        stack.push(val1 + val2);
                        break;
                    case "-":
                        stack.push(val1 - val2);
                        break;
                    case "*":
                        stack.push(val1 * val2);
                        break;
                    case "/":
                        stack.push(val1 / val2);
                        break;
                }

            }
        }
        return stack.pop();

    }