20.有效的括号

一言以概之，由于栈结构的特殊性，非常适合用来做匹配、对称类问题。

public boolean isValid(String s) {

    Deque<Character> deque=new LinkedList<>();

    for(int i=0;i<s.length();i++) {

        char 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();

}

public boolean isValid2(String s) {        
    Stack<Character> stack=new Stack<>();    
    Map<Character,Character> map=new HashMap<Character,Character>(){
        {
            put('}','{');
            put(']','[');
            put(')','(');
        }
    };

    for(char ch : s.toCharArray()) {
        if(!stack.isEmpty()&&map.containsKey(ch)) {
            if(map.get(ch)==stack.peek()) {
                stack.pop();
            }
            else {
                return false;
            }
        }
        else {
            stack.push(ch);
        }            
    }
    return stack.isEmpty();        
}

思路简述

这道题比较简单，就是利用了栈先进后出的特性，然后对括号进行匹配。
因为括号的特性，一对的左括号肯定比和它匹配的右括号先进栈。所以比较便捷的方法就是对右括号进行判断，看看栈里有没有和它匹配的左括号。如果先判断左括号的话，此时要找在左括号后面的右括号就会很麻烦。

具体来说，就是对输入的字符串进行判断，如果是左括号，那么就压入栈中。如果是右括号，那么就看此时栈顶元素是不是和它可以匹配的左括号（是栈顶元素的原因是按照判断顺序，可以匹配的左右括号之间一定没有其他元素）。如果是，就把那个左括号抛出栈，然后继续判断。如果不是，就说明这个右括号没有匹配的元素，就判断出错。
然后最后判断一下栈是否为空，如果不为空，说明有左括号剩余在栈中，那么就返回false。
然后下面两个方法本质上是一样的，就是第二种方法提前将左右括号存储到了hashmap中。

1047. 删除字符串中的所有相邻重复项

public static String removeDuplicates(String s) {        
    Stack<Character> stack=new Stack<>();        
    for(char ch: s.toCharArray()) {            
        if(!stack.isEmpty()&&ch==stack.peek()) {                
            stack.pop();
        }
        else {
            stack.push(ch);
        }            
    }
    String str2=stack.toString();
    String str="";
    while(!stack.isEmpty()) {
        str=stack.pop()+str;//注意这个相加的顺序问题
    }
    return str;    
}

思路简述

这个题比较简单，一开始在想abaaab里的aaa怎么同时消除，后来发现他并不会有这种情况。所以难点就大大降低了。
简单来说，在判断每一个新的字符时，看看它是不是和栈顶元素相同就可以了。如果相同，就删除栈顶元素，如果不相同，就将这个字符push进栈。

可能麻烦一点的是最后要再建立一个string字符串，来记录下栈内的元素，虽然栈是有tostring函数的，但是看看效果图，如果直接用这个函数，不会通过。

正常输出应该如下图所示：