代码随想录算法训练营第11天 | 20.有效的括号 ， 1047. 删除字符串中的所有相邻重复项 ，150. 逆波兰表达式求值

栈与队列理论基础

文章链接：https://programmercarl.com/%E6%A0%88%E4%B8%8E%E9%98%9F%E5%88%97%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html

20.有效的括号

题目链接：https://leetcode.cn/problems/valid-parentheses/description/

思路：使用栈进行模拟

我们的思路就是通过栈，进行模拟操作。但是要注意一些特殊情况。当我们输入的是左半边符号的时候，我们就把右符号给入栈。（先进后出，后进先出）。
然后，当右符号入栈的时候，检查栈顶的元素是不是一致的（这里要先判空，或者取栈顶元素的时候会报异常）。如果一致的话，就把栈顶元素给出栈了。
最后的话，再判断一下栈是否为空，如果为空的话，才是true。

解法：

class Solution {
    public boolean isValid(String s) {
        Deque<Character> deque = new LinkedList<>();
        int len = s.length();
        for(int i=0;i<len;i++){
            char c = s.charAt(i);
            if(c == '(')
                deque.push(')');
            else if(c == '{')
                deque.push('}');
            else if(c=='[')
                deque.push(']');
            else
            {
                if(deque.isEmpty() || deque.peek()!= c)
                    return false;
                deque.poll();
            }
        }

        return deque.isEmpty();
    }
}

时间复杂度：O(n)
空间复杂度：O(n)

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

题目连接：https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/description/

思路：使用栈的思想

我们定义一个栈，当字符入栈的时候，判断是否为空，如果不为空的话，就判断栈顶元素和我们入栈的元素是否一致，不一致的话就入栈，否则就把栈顶元素给出栈。
最后，得到字符串的时候，因为是栈，要reverse一下。
这里的话，我们是用了一个deque来模拟堆栈，最后生成字符串的时候，直接先进先出，不用再reverse了。

解法：

class Solution {
    public String removeDuplicates(String s) {
    	// ArrayDeque会比LinkedList在除了插入、删除元素这一点外会快一点
       Deque<Character> deque = new ArrayDeque<>();
        int len = s.length();
        for(int i=0;i<len;i++){
            char c = s.charAt(i);
            if(deque.isEmpty() || deque.peek() != c)
                // push等同于offerFirst
                deque.push(c);
            else
                deque.pop();
        }

        String str = "";
        while(!deque.isEmpty()){
            str = deque.pop() + str;
        }
        return str;
    }
}

时间复杂度：O(n)
空间复杂度：O(n)

150. 逆波兰表达式求值

题目连接：https://leetcode.cn/problems/evaluate-reverse-polish-notation/

思路：后缀表达式转成中缀表达式

这道题就是要把后缀表达式，转换成我们常见的后缀表达式。比如2,1,+。也就是我们的2+1。
这里的话，就是把每一个子表达式得到的结果，进行运算，一直迭代的过程。然后判断的话，也就是当出现的是运算符的时候，进行判断。
这里的话，也是用栈去进行解决。
然后，加减乘除的时候，减法和除法，需要注意一个先后顺序的问题。栈中的最后一个元素，就是我们的result了。

解法：

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer>stack = new Stack<>();
        for(String s:tokens){
           if(s.equals("+"))   stack.push(stack.pop() + stack.pop());
           else if(s.equals("-"))   stack.push(-stack.pop() + stack.pop());
           else if(s.equals("*"))   stack.push(stack.pop() * stack.pop());
           else if(s.equals("/"))   {
               int a = stack.pop();
               int b = stack.pop();
               stack.push(b/a);
           }
           else{
               stack.push(Integer.valueOf(s));
           }
        }
        return stack.pop();
    }
}

时间复杂度：O(n)
空间复杂度：O(n)