栈与队列 20. 有效的括号（简单）

需求：

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = "()"
输出：true
示例 2：

输入：s = "()[]{}"
输出：true
示例 3：

输入：s = "(]"
输出：false

提示：

1 <= s.length <= 104
s 仅由括号 '()[]{}' 组成

leetcode题目链接

思路：

看到字符串的这一个起始脑袋已经开始懵了，太多可能性和边界条件了。
这个题的实际含义是判断是否每一个括号都是成对出现的。
但是终结起来是三种情况

1. 左括号多了

   
   image.png

2.中间某对括号不匹配

image.png

3. 右括号多了

   
   image.png

循环这个括号字符串，循环为左括号的时候，将对应的右括号存入栈中。当循环到有括号的时候，与获取栈顶的括号对比，如果匹配进行出栈消除，如果不匹配直接返回false。还有两种特殊的情况，
一种是：循环到有括号的时候栈内已空，说明左括号少了。
另一种是：字符串已循环完成但是栈内还有元素寿命左括号多了。

有效括号.gif

栈

public boolean isValid(String s) {
        if (s == null || s.length() == 0
                || s.length() % 2 == 1) return false;
        Stack<Character> st = new Stack<Character>();
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            // 遍历左括号，存入右括号，方便右括号的匹配
            if ('(' == chars[i]) {
                st.push(')');
            } else if ('[' == chars[i]) {
                st.push(']');
            } else if ('{' == chars[i]) {
                st.push('}');
                // 字符串循环右侧括号过程中栈内左括号已空 ，说明右边括号多了
                // 左右括号不相等
            } else if (st.isEmpty() || chars[i] != st.peek()) {
                return false;
            }else {
                st.pop();
            }
        }
        // 字符串循环完毕 栈内剩余了元素说明左括号多了
        if(!st.isEmpty()) return false;

        return true;
    }

队列

        Deque<Character> deque = new LinkedList<>();
        char ch;
        for (int i = 0; i < s.length(); i++) {
            ch = s.charAt(i);
            //碰到左括号，就把相应的右括号入栈
            if (ch == '(') {
                deque.push(')');
            }else if (ch == '{') {
                deque.push('}');
            }else if (ch == '[') {
                deque.push(']');
            } else if (deque.isEmpty() || deque.peek() != ch) {
                return false;
            }else {//如果是右括号判断是否和栈顶元素匹配
                deque.pop();
            }
        }
        //最后判断栈中元素是否匹配
        return deque.isEmpty();
    }\

验证结果 验证结果 验证结果