Stack<Character> st = new Stack<>(); 如何判断栈是否为空？

Question

在Java中，使用`Stack st = new Stack<>();`定义一个栈后，如何判断栈是否为空是一个常见的技术问题。解决方法是调用`st.isEmpty()`方法。该方法返回布尔值：如果栈为空，则返回`true`；否则返回`false`。 例如，在字符匹配场景中（如括号匹配），我们常利用栈的特性来存储和比较字符。当所有字符处理完毕后，若栈仍不为空，则说明存在未匹配的字符。此时，通过`st.isEmpty()`可以准确判断是否存在错误或冗余字符。 需要注意的是，除了`isEmpty()`，还可以通过检查栈大小`st.size() == 0`来间接判断，但推荐使用`isEmpty()`，因为它语义清晰且效率更高。此外，在多线程环境中，若使用非线程安全的`Stack`类，需自行同步访问以确保判断结果的准确性。

Answer 1

1. 基础概念：栈的基本操作

在Java中，栈（Stack）是一种后进先出（LIFO, Last In First Out）的数据结构。我们可以通过`Stack st = new Stack<>();`来定义一个存储字符的栈。

栈提供了多种常用方法，例如：

• `push(E item)`：将元素压入栈顶。
• `pop()`：移除并返回栈顶元素。
• `peek()`：返回栈顶元素但不移除。
• `isEmpty()`：判断栈是否为空。

其中，`isEmpty()`是判断栈是否为空的核心方法，返回布尔值。如果栈为空，则返回`true`；否则返回`false`。

2. 应用场景分析：括号匹配问题

在实际开发中，栈常用于解决括号匹配问题。例如，给定一个字符串包含各种括号，如`{[(())]}`，我们需要验证括号是否正确配对。

具体步骤如下：

1. 遍历字符串中的每个字符。
2. 如果遇到左括号（如`(`、`[`、`{`），将其压入栈。
3. 如果遇到右括号（如`)`、`]`、`}`），检查栈顶元素是否为对应的左括号。如果是，则弹出栈顶元素；如果不是，则说明括号不匹配。
4. 当所有字符处理完毕后，使用`st.isEmpty()`判断栈是否为空。若栈非空，则说明存在未匹配的左括号。

public boolean isValid(String s) {
    Stack st = new Stack<>();
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else {
            if (st.isEmpty()) return false;
            char top = st.pop();
            if ((c == ')' && top != '(') ||
                (c == ']' && top != '[') ||
                (c == '}' && top != '{')) {
                return false;
            }
        }
    }
    return st.isEmpty(); // 栈为空表示所有括号匹配
}
    

3. 替代方案与性能比较

除了使用`isEmpty()`方法外，还可以通过检查栈大小来判断栈是否为空：

if (st.size() == 0) {
    System.out.println("栈为空");
}
    

然而，推荐使用`isEmpty()`方法，原因如下：

方法	语义清晰度	效率
`isEmpty()`	高	通常为O(1)
`size() == 0`	较低	可能涉及额外计算，效率略低

4. 多线程环境下的注意事项

在多线程环境中，`Stack`类是非线程安全的。这意味着多个线程同时访问同一个栈时，可能会导致数据不一致或错误的判断结果。

解决方案包括：

• 使用同步块手动同步访问。
• 改用线程安全的替代类，如`java.util.concurrent.ConcurrentLinkedDeque`。

以下是一个简单的同步示例：

synchronized (st) {
    if (st.isEmpty()) {
        System.out.println("栈为空");
    }
}
    

对于更复杂的并发场景，建议设计专门的线程安全机制。

5. 流程图：括号匹配逻辑

graph TD;
            A[开始] --> B{是否为空？};
            B -- 是 --> C[返回 true];
            B -- 否 --> D{是否为左括号？};
            D -- 是 --> E[压入栈];
            D -- 否 --> F{是否匹配栈顶？};
            F -- 是 --> G[弹出栈顶];
            F -- 否 --> H[返回 false];
            E --> I{继续遍历？};
            G --> I;
            I -- 是 --> J[下一个字符];
            I -- 否 --> K{栈是否为空？};
            K -- 是 --> L[返回 true];
            K -- 否 --> M[返回 false];