力扣20-有效的括号——栈实现

题目描述

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

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。

解题思路

写代码时一般也要遵从代码的语法规范，括号不符合规范也会报语法错误，一般会出现以下几种情况：

• 左括号多了  ( ( )
• 右括号多了 [ ] ]
• 左右括号不匹配 ( [ ) ]

而且发现如果有括号嵌套时，最内侧的括号是距离最近的（后进先出），最外侧的括号距离是最远的（先进后出），可以联想到这道题目可以用栈来求解。

关于java中的栈Deque是一个双端队列的接口，它的实现类有LinkedList、ArrayDeque、LinkedBlockingDeque，其中比较常用的是LinkedList，这也就是AyyarList会报错的原因。

这是一篇介绍Deque的博客【Java】Java双端队列Deque使用详解_devnn的博客-CSDN博客_deque javaDeque是一个双端队列接口，继承自Queue接口，它们共同的实现类是LinkedList。Deque的功能很强大：代替普通队列Queue：先进先出、队尾进队头出可以作为双端队列：队尾和队头都可以进出还可以作为堆栈使用：先进后出、只能从一端进出 注意：Java堆栈Stack类已经过时，Java官方推荐使用Deque替代Stack使用。jdk文档中关于Deque的使用介...https://blog.csdn.net/devnn/article/details/82716447

 当Deque作为堆栈时，一般使用push、pop、peek三种方法。

• 新建一个栈arr  Deque<Character> arr = new LinkedList<>();
• 遍历字符串s
• 如果遇到左括号一律转变为相应的右括号，这样做的目的是为了将遍历到的右括号与栈内元素做匹配
• 如果在遍历过程中发现栈已经为空，说明右括号数量多了，返回false
• 如果遍历完了发现栈不为空，说明左括号数量多了，也会返回false
• 如果遍历到的字符ch 与当前栈顶元素不匹配，也会返回false，否则就可以pop弹出栈顶元素。

输入输出示例

代码

class Solution {
    public boolean isValid(String s) {
        int len = s.length();
        char ch;
        //Deque<Character> arr = new ArrayList<>();
        Deque<Character> arr = new LinkedList<>();
        for(int i = 0; i < len; i++){
            ch = s.charAt(i);
            if(ch =='('){
                arr.push(')');
            }else if(ch =='['){
                arr.push(']');
            }else if(ch == '{'){
                arr.push('}');
            }else if(arr.isEmpty()){ //在遍历过程中栈为空说明右括号个数多了
                return false;
            }else if(ch == arr.peek()){//栈顶元素与当前元素匹配才可以弹出，也就是说左右元素必须匹配
                arr.pop();
            }else return false;
        }
        return arr.isEmpty();//如果遍历完发现不为空则说明左括号个数多了
    }
}