Day11:栈与队列part02：20. 有效的括号、1047.删除字符串中所有相邻重复项、150. 逆波兰表达式求值

https://blog.csdn.net/weixin_43303286/article/details/131869968?spm=1001.2014.3001.5501

20. 有效的括号

遇见左括号对应的右括号进栈，遇到右括号看栈顶，不相同就返回false

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for(char ch : s.toCharArray()){
            if(ch == '{') {
                stack.push('}');
            }else if(ch == '('){
                stack.push(')');
            }else if(ch == '['){
                stack.push(']');
            }else{
                if(!stack.empty()){
                    if(stack.peek() != ch){
                        return false;
                    }else{
                        stack.pop();
                    }
                }else{
                    return false;
                }

            }
        }
        return stack.empty();
    }

}

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

就是消消乐思想，栈的拿手好戏，可以直接声明stack，也可以用字符串当作栈：

在Java中，Deque（双端队列）通常被用作栈的实现，而不是Stack类，主要有以下几个原因：

Stack类是Java早期版本中的遗留类，它继承自Vector类，而Vector类的所有方法都是同步的，这意味着它在多线程环境下的性能较差。

Deque接口提供了更丰富和一致的接口。例如，Deque提供了addFirst、addLast、removeFirst、removeLast等方法，这使得它既可以作为栈（先进后出）使用，也可以作为队列（先进先出）使用。

Deque接口的实现类，如ArrayDeque，通常比Stack类具有更好的性能。

class Solution {
    public String removeDuplicates(String s) {
        Stack<Character> sb = new Stack<>();
        StringBuilder sb1 = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if(sb.isEmpty() || sb.peek()!= s.charAt(i)){
                sb.push(s.charAt(i));
            }else{
                sb.pop();
            }
        }
        while(!sb.empty()){
            sb1.append(sb.pop());
        }
        return sb1.reverse().toString();
    }
}

• 翻转字符串：StringBuilder的reverse()
• 使用Deque的代码：

class Solution {
    public String removeDuplicates(String S) {
        //ArrayDeque会比LinkedList在除了删除元素这一点外会快一点
        //参考：https://stackoverflow.com/questions/6163166/why-is-arraydeque-better-than-linkedlist
        ArrayDeque<Character> deque = new ArrayDeque<>();
        char ch;
        for (int i = 0; i < S.length(); i++) {
            ch = S.charAt(i);
            if (deque.isEmpty() || deque.peek() != ch) {
                deque.push(ch);
            } else {
                deque.pop();
            }
        }
        String str = "";
        //剩余的元素即为不重复的元素
        while (!deque.isEmpty()) {
            str = deque.pop() + str;
        }
        return str;
    }
}

• 直接用字符串当栈：

class Solution {
    public String removeDuplicates(String s) {
        // 将 res 当做栈
        // 也可以用 StringBuilder 来修改字符串，速度更快
        // StringBuilder res = new StringBuilder();
        StringBuffer res = new StringBuffer();
        // top为 res 的长度
        int top = -1;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // 当 top > 0,即栈中有字符时，当前字符如果和栈中字符相等，弹出栈顶字符，同时 top--
            if (top >= 0 && res.charAt(top) == c) {
                res.deleteCharAt(top);
                top--;
            // 否则，将该字符 入栈，同时top++
            } else {
                res.append(c);
                top++;
            }
        }
        return res.toString();
    }
}

150. 逆波兰表达式求值

注意-和/有顺序要求。

class Solution {
    public int evalRPN(String[] tokens) {
        Deque<Integer> nums = new ArrayDeque<>();//用来存数字
        for(String s: tokens){
            if(Objects.equals(s, "+")){
                nums.push(nums.pop() + nums.pop());
            }else if(Objects.equals(s, "-")){
                int a = nums.pop();
                int b = nums.pop();
                nums.push(b - a);
            }else if(Objects.equals(s, "*")){
                nums.push(nums.pop() * nums.pop());
            }else if(Objects.equals(s, "/")){
                int a = nums.pop();
                int b = nums.pop();
                nums.push(b / a);
            }else{
                nums.push(Integer.parseInt(s));
            }
        }
        return nums.peek();
    }

• Integer.parseInt(s)字符串转数字