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 中，并执行以下操作：

• 从 Stack 中取出栈顶元素。
• 如果当前元素为终点，则返回 true。
• 否则，对当前元素的四个方向进行遍历，判断是否可以走（即是否越界或者已经走过），如果可以，则将该位置的坐标压入 Stack 中，并记录该位置已经走过。

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

Path found!

这表示我们从起点（1, 1）出发可以找到终点（5, 5）。