LeetCode Hot100 20.有效的括号

题目：

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

有效字符串需满足：

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

方法：

由于栈结构的特殊性，非常适合做对称匹配类的题目。

首先要弄清楚，字符串里的括号不匹配有三种情况：

第一种情况：已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false， 缺少右括号

第二种情况：遍历字符串匹配的过程中，发现栈里没有要匹配的字符。所以return false， 栈顶不匹配

第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号return false， 缺少左括号

那么什么时候说明左括号和右括号全都匹配了呢，就是字符串遍历完之后，栈是空的，就说明全都匹配了。

但还有一些技巧，在匹配左括号的时候，右括号先入栈，就只需要比较当前元素和栈顶相不相等就可以了，比左括号先入栈代码实现要简单的多了！

代码：

class Solution {
    public boolean isValid(String s) {
        // Deque双端队列,头部、尾部都可以插入、删除元素
        // push插入头部、peek从头部取出返回但不删除、pop删除头部并且不返回
        // addFirst()、getFirst()、removeFirst()  头部操作
        // addLast() 、getLast() 、removeLast()   尾部操作
        // 可以实现 栈、队列、双向队列
        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();
    }
}

重点：通过Deque掌握队列、栈、双端队列