利用Stack函数实现先进后出数据结构

Stack(栈)是一种常用的数据结构，它可以用于实现许多算法和函数。在Java中，可以通过java.util.Stack类来实现栈。当需要LIFO（Last-In-First-Out）数据结构时，可以使用Stack。

一、Stack的基本操作

在Java中，Stack类是Vector的一个子类。除了由Vector提供的全部操作之外，Stack还提供了自己的push、pop、empty等方法。其中，push方法用于入栈，pop方法用于出栈，empty方法用于判断栈是否为空。下面是Stack的基本操作的代码示例。

    Stack stack = new Stack<>();
    stack.push(1); //入栈
    stack.push(2);
    stack.push(3);
    
    while (!stack.empty()) { //判断栈是否为空
        System.out.println(stack.pop()); //出栈
    }

  

在以上示例代码中，声明了一个Stack对象并将元素1、2、3入栈，然后通过while循环不断将栈顶元素出栈并打印，直到栈为空。

二、Stack的应用1：括号匹配

括号匹配是栈最常见的应用之一。对于一个字符串，如果其中的括号全部是匹配的，那么就可以认为它是一个合法的表达式。可以使用Stack来检查一个字符串中的括号是否匹配。

    public static boolean isMatch(String s) {
        Stack stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else if (c == ')' && !stack.isEmpty() && stack.peek() == '(') {
                stack.pop();
            } else if (c == ']' && !stack.isEmpty() && stack.peek() == '[') {
                stack.pop();
            } else if (c == '}' && !stack.isEmpty() && stack.peek() == '{') {
                stack.pop();
            } else {
                return false;
            }
        }
        return stack.isEmpty();
    }

  

在以上示例代码中，isMatch方法使用Stack来判断字符串s中的括号是否匹配。遇到左括号就入栈，遇到右括号就判断它和栈顶元素是否匹配。如果匹配，则将栈顶元素出栈；如果不匹配，则说明括号不匹配，返回false。最后，如果栈为空，则说明括号全部匹配，返回true。

三、Stack的应用2：逆波兰表达式求解

逆波兰表达式（Reverse Polish Notation，简称RPN）也称后缀表达式。它将运算符写在操作数（即数字）的后面，使得整个表达式没有括号，从而避免了表达式的歧义。可以用Stack来求解逆波兰表达式。

    public static int evalRPN(String[] tokens) {
        Stack stack = new Stack<>();
        for (String token : tokens) {
            if (token.equals("+")) {
                int b = stack.pop();
                int a = stack.pop();
                stack.push(a + b);
            } else if (token.equals("-")) {
                int b = stack.pop();
                int a = stack.pop();
                stack.push(a - b);
            } else if (token.equals("*")) {
                int b = stack.pop();
                int a = stack.pop();
                stack.push(a * b);
            } else if (token.equals("/")) {
                int b = stack.pop();
                int a = stack.pop();
                stack.push(a / b);
            } else {
                stack.push(Integer.parseInt(token));
            }
        }
        return stack.pop();
    }

  

在以上示例代码中，evalRPN方法使用Stack来求解逆波兰表达式。对于一个操作符，从栈顶依次弹出两个操作数进行计算，并将计算结果压入栈中。对于一个操作数，直接将它压入栈中。最后，栈中只剩下一个元素，即为表达式的值。

四、总结

Stack是Java中常用的数据结构之一，它可以用于实现许多算法和函数。本文介绍了Stack的基本操作，以及两个应用：括号匹配和逆波兰表达式求解。希望读者通过本文的学习，可以更深入地理解Stack的使用。