Java栈的知识点有哪些

栈（Stack）是计算机科学中一种常见的数据结构，它遵循后进先出（LIFO, Last In First Out）的原则。在Java中，栈可以通过多种方式实现，包括使用Java集合框架中的Stack类或Deque接口。本文将详细介绍Java栈的相关知识点。

1. 栈的基本概念

栈是一种线性数据结构，具有以下特点：

• 后进先出（LIFO）：最后入栈的元素最先出栈。
• 操作受限：栈只允许在一端（称为栈顶）进行插入和删除操作。
• 基本操作：
  • push：将元素压入栈顶。
  • pop：移除并返回栈顶元素。
  • peek：返回栈顶元素但不移除。
  • isEmpty：判断栈是否为空。
  • size：返回栈中元素的数量。

2. Java中的栈实现

在Java中，栈可以通过以下几种方式实现：

2.1 Stack类

Stack类是Java集合框架中的一个类，继承自Vector类。它提供了栈的基本操作。

import java.util.Stack;

public class StackExample {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();

        // 压栈
        stack.push(1);
        stack.push(2);
        stack.push(3);

        // 弹栈
        System.out.println(stack.pop()); // 输出 3

        // 查看栈顶元素
        System.out.println(stack.peek()); // 输出 2

        // 判断栈是否为空
        System.out.println(stack.isEmpty()); // 输出 false

        // 获取栈的大小
        System.out.println(stack.size()); // 输出 2
    }
}

2.2 Deque接口

Deque（双端队列）接口也可以用来实现栈。ArrayDeque是Deque接口的一个常用实现类，它比Stack类更高效。

import java.util.ArrayDeque;
import java.util.Deque;

public class DequeStackExample {
    public static void main(String[] args) {
        Deque<Integer> stack = new ArrayDeque<>();

        // 压栈
        stack.push(1);
        stack.push(2);
        stack.push(3);

        // 弹栈
        System.out.println(stack.pop()); // 输出 3

        // 查看栈顶元素
        System.out.println(stack.peek()); // 输出 2

        // 判断栈是否为空
        System.out.println(stack.isEmpty()); // 输出 false

        // 获取栈的大小
        System.out.println(stack.size()); // 输出 2
    }
}

3. 栈的应用场景

栈在计算机科学中有广泛的应用，以下是一些常见的应用场景：

3.1 函数调用栈

在程序执行过程中，函数调用的顺序是通过栈来管理的。每次调用一个函数时，系统会将函数的返回地址、局部变量等信息压入栈中，函数执行完毕后，再从栈中弹出这些信息，返回到调用点。

3.2 表达式求值

栈可以用于解析和计算表达式，如中缀表达式转后缀表达式、后缀表达式求值等。

import java.util.Stack;

public class ExpressionEvaluation {
    public static int evaluatePostfix(String expression) {
        Stack<Integer> stack = new Stack<>();

        for (char c : expression.toCharArray()) {
            if (Character.isDigit(c)) {
                stack.push(c - '0');
            } else {
                int operand2 = stack.pop();
                int operand1 = stack.pop();
                switch (c) {
                    case '+':
                        stack.push(operand1 + operand2);
                        break;
                    case '-':
                        stack.push(operand1 - operand2);
                        break;
                    case '*':
                        stack.push(operand1 * operand2);
                        break;
                    case '/':
                        stack.push(operand1 / operand2);
                        break;
                }
            }
        }

        return stack.pop();
    }

    public static void main(String[] args) {
        String expression = "231*+9-";
        System.out.println("Postfix Evaluation: " + evaluatePostfix(expression)); // 输出 -4
    }
}

3.3 括号匹配

栈可以用于检查表达式中的括号是否匹配。

import java.util.Stack;

public class BracketMatching {
    public static boolean isBalanced(String expression) {
        Stack<Character> stack = new Stack<>();

        for (char c : expression.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else if (c == ')' || c == ']' || c == '}') {
                if (stack.isEmpty()) {
                    return false;
                }
                char top = stack.pop();
                if (!isMatchingPair(top, c)) {
                    return false;
                }
            }
        }

        return stack.isEmpty();
    }

    private static boolean isMatchingPair(char opening, char closing) {
        return (opening == '(' && closing == ')') ||
               (opening == '[' && closing == ']') ||
               (opening == '{' && closing == '}');
    }

    public static void main(String[] args) {
        String expression = "{[()()]}";
        System.out.println("Is Balanced: " + isBalanced(expression)); // 输出 true
    }
}

3.4 浏览器的前进后退功能

浏览器的前进和后退功能可以通过两个栈来实现。一个栈用于存储访问过的页面，另一个栈用于存储后退时弹出的页面。

4. 栈的复杂度分析

• 时间复杂度：
  • push、pop、peek、isEmpty、size操作的时间复杂度均为O(1)。
• 空间复杂度：
  • 栈的空间复杂度为O(n)，其中n是栈中元素的数量。

5. 栈的优缺点

5.1 优点

• 简单易用：栈的操作非常简单，容易理解和实现。
• 高效：栈的基本操作时间复杂度均为O(1)，非常高效。

5.2 缺点

• 功能受限：栈只允许在一端进行操作，功能相对受限。
• 内存限制：栈的大小通常受限于内存，可能会发生栈溢出。

6. 总结

栈是一种非常重要的数据结构，广泛应用于各种场景中。在Java中，可以通过Stack类或Deque接口来实现栈。理解栈的基本概念、操作和应用场景，对于编写高效、可靠的程序至关重要。