Day21——栈和队列专题

﹏ヽ暗。殇╰゛Y 2024-04-01 11:53 60阅读 0赞

#### 文章目录 ####

*   *   *  3.有效的括号
         *  4.删除字符串中的所有相邻重复项
         *  5. 逆波兰表达式求值

--------------------

#### 3.有效的括号 ####

**思路**：括号匹配有三种失败的情况：

1.  左括号多余
    
    `({[]}()`
2.  括号未多余，但不匹配
    
    `[()[`
3.  右括号多余
    
    `({[]})))`

我们的代码只要覆盖了这三种不匹配的情况，就不会出问题，可以看出 动手之前分析好题目的重要性。

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

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

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

**代码实现：**

class Solution {
        
        public boolean isValid(String s) {
        
            int n = s.length();
            if(n % 2 !=0){
        
                return false;
            }
            Stack<Character> stk = new Stack<>();
            for(int i=0;i<n;i++){
        
                char ch = s.charAt(i);
                if(ch=='(') stk.push(')');
                else if(ch=='[') stk.push(']');
                else if(ch=='{') stk.push('}');
                else if(stk.empty()||ch!=stk.peek()) return false;
                else stk.pop();                                                              
            } 
            return stk.empty();
        }
    }

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

**思路：**

用栈来存放，那么栈的目的，就是存放遍历过的元素，当遍历当前的这个元素的时候，去栈里看一下我们是不是遍历过相同数值的相邻元素。然后再去做对应的消除操作

*  当栈为空或者此时的元素和栈顶元素不匹配, 则将当前元素入栈
 *  匹配, 则弹出栈顶元素
 *  最后通过字符串拼接返回

最后栈内剩余的元素就是答案

**代码实现：**

class Solution {
        
        public String removeDuplicates(String s) {
        
            ArrayDeque<Character> deque = new ArrayDeque<>();
            for(int i=0;i<s.length();i++){
        
                char 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;
        }
    }

#### 5. 逆波兰表达式求值 ####

逆波兰表达式：其实就是二叉树的后续遍历（后缀表达式）

思路：栈模拟

*  遇到数字加入栈
 *  遇到操作字符弹出栈顶两个元素，进行对应操作即可

注意：在做减法以及除法时，要注意pop出来的顺序，**先放进的-后放进的，先放进的/后放进的，后pop出来的-先pop出来的，后pop出来的/先pop出来的**

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