具体案例

利用栈后进先出的特点，可以解决一些特定的算法问题

有效括号问题（LeetCode第20题）

问题描述

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

示例

示例1：

1 2	输入: "()" 输出: true

示例2：

1 2	输入: "()[]{}" 输出: true

示例3：

1 2	输入: "([)]" 输出: false

示例4：

1 2	输入: "{[]}" 输出: true

算法思路

总体思路：将开括号入栈，对于闭括号，检测栈顶元素是否与之匹配，匹配则栈顶元素出栈，否则说明该字符串无效。
注意：

在处理闭括号时，要留意是否有栈顶元素，如果没有栈顶，说明前面没有与之匹配的开括号，该字符串无效。
处理完所有字符后，如果栈中还有元素，说明开括号没有匹配完，该字符串无效。

在这个算法中，由于闭括号要与其最接近的开括号匹配，所以正好可以利用栈后进先出的特点。

代码实现

private static boolean isValid(String s) {
    if (s.equals("") || s.equals("()") || s.equals("[]") || s.equals("{}")) {
        return true;
    }

    ArrayDeque<Character> stack = new ArrayDeque<>();
    HashMap<Character, Character> hashMap = new HashMap<>();    //存储括号对
    hashMap.put('(', ')');
    hashMap.put('[', ']');
    hashMap.put('{', '}');

    for (int i = 0; i < s.length(); i++) {
        char curr = s.charAt(i);
        if (curr == '(' || curr == '[' || curr == '{') {
            stack.push(curr);
        } else {
            try {
                if (hashMap.get(stack.pop()) != curr) {
                    return false;
                }
            } catch (Exception e) {
                return false;
            }
        }
    }

    return stack.size() == 0;
}