Stack（堆栈）是一种存储数据的结构，其遵循后进先出（LIFO）的原则。在 Stack 中，只有在栈顶的元素才能被访问、删除或更新，而其他的元素则需要等待栈顶元素先被操作。

Java 实现 Stack 详解及实例代码

什么是 Stack

Stack（堆栈）是一种存储数据的结构，其遵循后进先出（LIFO）的原则。在 Stack 中，只有在栈顶的元素才能被访问、删除或更新，而其他的元素则需要等待栈顶元素先被操作。

Stack 的基本操作

Stack 可以执行以下操作：

push：将数据项压入 stack 的顶部。
pop：弹出 stack 的顶部数据项，并将其返回。
peek：返回 stack 的顶部数据项。
isEmpty：判断 stack 是否为空。
size：返回 stack 内元素的数量。

Stack 的实现

在 Java 中，我们可以使用 java.util.Stack 类来实现 Stack。

下面是一个示例代码，演示了如何创建一个 Stack 对象、将数据项压入 Stack、从 Stack 取出数据项等基本操作：

import java.util.Stack;

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

        stack.push(10);
        stack.push(20);
        stack.push(30);

        int popped = stack.pop();
        System.out.println("Popped item: " + popped);

        int peeked = stack.peek();
        System.out.println("Peeked item: " + peeked);

        System.out.println("Is the stack empty? " + stack.isEmpty());
        System.out.println("The size of the stack is: " + stack.size());
    }
}

在上面的代码中，我们首先创建了一个 Stack 对象 stack，并依次将数字 10、20、30 压入 Stack 中。然后我们取出栈顶元素（30），将其弹出并打印。接着我们获取栈顶元素（20），不弹出并打印。最后我们通过 isEmpty() 和 size() 方法检查 Stack 是否为空，以及 Stack 中元素的数量。

Stack 的示例应用

示例1：检查字符串中的括号是否匹配

假设有一个包含括号（(、)、[、]、{、}）的字符串，现在需要检查其中的括号是否匹配。我们可以使用 Stack 来实现括号匹配的功能。

下面是一个示例代码：

import java.util.Stack;

public class CheckBrackets {
    public static boolean check(String str) {
        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            if (ch == '(' || ch == '[' || ch == '{') {
                stack.push(ch);
            } else if (ch == ')' || ch == ']' || ch == '}') {
                if (stack.isEmpty()) {
                    return false;
                }
                char top = stack.peek();
                if ((ch == ')' && top == '(') || (ch == ']' && top == '[') || (ch == '}' && top == '{')) {
                    stack.pop();
                } else {
                    return false;
                }
            }
        }

        return stack.isEmpty();
    }

    public static void main(String[] args) {
        String str1 = "{({[]})}";
        String str2 = "{([)]}";
        String str3 = "([]})";

        System.out.println(str1 + " is " + (check(str1) ? "" : "NOT ") + "valid");
        System.out.println(str2 + " is " + (check(str2) ? "" : "NOT ") + "valid");
        System.out.println(str3 + " is " + (check(str3) ? "" : "NOT ") + "valid");
    }
}

在上面的代码中，我们定义了一个 check() 方法，用于检查输入的字符串中的括号是否匹配。首先我们创建一个 Stack 对象 stack，并扫描字符串中的每个字符，如果字符是左括号，则将其压入 Stack 中。如果字符是右括号，则我们从 Stack 中获取栈顶元素（即与该右括号对应的左括号），如果不匹配则返回 false，否则弹出左括号并继续扫描。最后，如果 Stack 是空的，则表示括号匹配成功，返回 true，否则返回 false。

我们可以运行上面的代码，得到如下输出：

{({[]})} is valid
{([)]} is NOT valid
([]}) is NOT valid

示例 2：使用 Stack 模拟迷宫寻路

在这个示例中，我们将使用 Stack 来解决经典游戏“迷宫寻路”。假设有一个迷宫地图，其中包含了若干个小区域，并且相邻的小区域之间可能有通路。现在我们需要从地图的起点开始寻找终点。我们可以将地图抽象为一个二维数组，并使用 Stack 中存储当前所在的坐标及路径信息。

下面是一个示例代码：

import java.util.Stack;

public class Maze {
    private static int[][] map = { 
            { 1, 1, 1, 1, 1, 1, 1 },
            { 1, 0, 0, 0, 0, 0, 1 },
            { 1, 0, 1, 1, 0, 0, 1 },
            { 1, 0, 0, 1, 0, 0, 1 },
            { 1, 0, 0, 1, 1, 0, 1 },
            { 1, 0, 0, 0, 0, 0, 1 },
            { 1, 0, 1, 1, 1, 1, 1 } 
    };
    private static int[][] directions = {
            {-1, 0}, // 上
            {0, 1},  // 右
            {1, 0},  // 下
            {0, -1}  // 左
    };
    private static Stack<int[]> stack = new Stack<>();

    public static boolean search(int startRow, int startCol, int endRow, int endCol) {
        stack.push(new int[] { startRow, startCol });

        while (!stack.isEmpty()) {
            int[] current = stack.pop();
            if (current[0] == endRow && current[1] == endCol) {
                return true;
            }

            for (int[] direction : directions) {
                int newRow = current[0] + direction[0];
                int newCol = current[1] + direction[1];
                if (newRow >= 0 && newRow < map.length && newCol >= 0 && newCol < map[0].length
                        && map[newRow][newCol] == 0) {
                    stack.push(new int[] { newRow, newCol });
                    map[newRow][newCol] = 2;
                }
            }
        }

        return false;
    }

    public static void main(String[] args) {
        boolean success = search(1, 1, 5, 5);

        if (success) {
            System.out.println("Path found!");
        } else {
            System.out.println("Path not found.");
        }
    }
}

在上面的代码中，我们首先定义了一个地图数组 map 和一个方向数组 directions，用于表示可以走的方向。我们使用 Stack 对象 stack 存储当前所在的坐标及路径信息。

在 search() 方法中，我们将起点的坐标压入 Stack 中，并执行以下操作：