Stack集合

定义

Stack是Java中表示栈的类，它继承自Vector类，用于实现后进先出(LIFO)的数据结构，主要用于存储和访问遵循特定顺序的元素。

作用

Stack集合在实际开发中具有以下重要价值： 1. 函数调用：管理程序执行栈和递归调用 2. 表达式求值：实现后缀表达式计算 3. 括号匹配：检查括号的合法性 4. 撤销操作：支持操作的撤销和重做 5. 深度优先搜索：实现DFS算法

图表说明

重要

• eMac在20年职业生涯中只使用了大约3次，一般很少用到
• 面试时候用到很多，考的是对数据结构的理解
• eMac觉得记住这张图就好了
• 现实项目中比队列场景少很多

例子

import java.util.Stack;

public class StackDemo {
    public static void main(String[] args) {
        // 基本操作示例
        Stack<String> stack = new Stack<>();
        stack.push("第一层");
        stack.push("第二层");
        stack.push("第三层");

        System.out.println("栈大小: " + stack.size());
        System.out.println("栈顶元素: " + stack.peek());

        // 出栈操作
        System.out.println("出栈顺序:");
        while (!stack.isEmpty()) {
            System.out.println(stack.pop());
        }

        // 括号匹配示例
        String expression = "((a+b)*(c-d))";
        System.out.println("括号匹配检查: " + isBalanced(expression));

        // 后缀表达式计算
        String postfix = "3 4 + 5 *";
        System.out.println("后缀表达式计算: " + evaluatePostfix(postfix));
    }

    // 检查括号是否匹配
    public static boolean isBalanced(String expression) {
        Stack<Character> stack = new Stack<>();
        for (char c : expression.toCharArray()) {
            if (c == '(') {
                stack.push(c);
            } else if (c == ')') {
                if (stack.isEmpty()) return false;
                stack.pop();
            }
        }
        return stack.isEmpty();
    }

    // 计算后缀表达式
    public static int evaluatePostfix(String expression) {
        Stack<Integer> stack = new Stack<>();
        String[] tokens = expression.split(" ");

        for (String token : tokens) {
            if (token.matches("\\d+")) {
                stack.push(Integer.parseInt(token));
            } else {
                int b = stack.pop();
                int a = stack.pop();
                switch (token) {
                    case "+": stack.push(a + b); break;
                    case "-": stack.push(a - b); break;
                    case "*": stack.push(a * b); break;
                    case "/": stack.push(a / b); break;
                }
            }
        }
        return stack.pop();
    }
}

执行结果

栈大小: 3
栈顶元素: 第三层
出栈顺序:
第三层
第二层
第一层
括号匹配检查: true
后缀表达式计算: 35