【数据结构与算法】6、栈（Stack）的实现、LeetCode：有效的括号-Toy模板网

这篇具有很好参考价值的文章主要介绍了【数据结构与算法】6、栈（Stack）的实现、LeetCode：有效的括号。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、栈（Stack）

🌱 栈是一种特殊的线性表，只能在一端进行操作
🌱 往栈中添加元素的操作，一般叫做 push（入栈）

🌱 从栈中移除元素的操作，一般叫做 pop，出栈（只能移除栈顶元素），也叫做：弹出栈顶元素

🌱 后进先出的原则，Last In First Out，LIFO

【数据结构与算法】6、栈（Stack）的实现、LeetCode：有效的括号,数据结构与算法,leetcode,算法,职场和发展

注意：这里的栈与内存中的栈空间是两个不同的概念

二、利用 ArrayList 实现栈

🌾栈的内部实现可使用动态数组、链表等进行实现
🌾jdk 官方的栈是继承了 Vector 进行实现

【数据结构与算法】6、栈（Stack）的实现、LeetCode：有效的括号,数据结构与算法,leetcode,算法,职场和发展
🌾Vector 可以理解为是线程安全的动态数组

/**
 * 利用动态数组实现栈
 */
public class Stack<E> {
    // 通过【组合】的方式使用 ArrayList
    private final List<E> list = new ArrayList<>();

    /**
     * 获取栈中元素个数
     */
    public int size() {
        return list.size();
    }

    /**
     * 判断栈中是否一个元素都没有（判断是否是一个空栈）
     */
    public boolean isEmpty() {
        return list.isEmpty();
    }

    /**
     * 往栈中添加元素（入栈）
     */
    public void push(E element) {
        list.add(element);
    }

    /**
     * 取出栈顶元素, 并把栈顶元素删除（出栈）
     *
     * @return 栈顶元素
     */
    public E pop() {
        return list.remove(size() - 1);
    }

    /**
     * 获取栈顶元素内容
     */
    public E top() {
        return list.get(size() - 1);
    }

    /**
     * 清空栈
     */
    public void clear() {
        list.clear();
    }
}

测试代码：

public class QQMain {
    public static void main(String[] args) {
        Stack<String> stack = new Stack<>();

        stack.push("心");
        stack.push("顺");
        stack.push("事");
        stack.push("万");
        stack.push("愿");

        while (!stack.isEmpty()) {
            System.out.print(stack.pop());
        }
    }

}

三、LeetCode: 有效的括号

题目地址：https://leetcode.cn/problems/valid-parentheses/

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

有效字符串需满足：

① 左括号必须用相同类型的右括号闭合
② 左括号必须以正确的顺序闭合
③ 每个右括号都有一个对应的相同类型的左括号

【数据结构与算法】6、栈（Stack）的实现、LeetCode：有效的括号,数据结构与算法,leetcode,算法,职场和发展

☘️ {[]}: true
☘️ ([)]: false

【数据结构与算法】6、栈（Stack）的实现、LeetCode：有效的括号,数据结构与算法,leetcode,算法,职场和发展

(1) 思路

🍃① 遇见左字符，将左字符入栈
🍃② 遇见右字符
🌻如果栈是空的，说明不是有效的括号【)()】
🌻如果栈不为空，将栈顶字符出栈，与右字符进行比较
❄️如果左右字符不匹配，说明括号无效
❄️如果左右字符匹配，继续扫描下一个字符
🍃③ 所有字符扫描完毕后
🌻栈为空，说明是有效的括号
🌻栈不为空，说明不是有效的括号

(2) 代码

① 看完思路后自己实现的代码

代码是正确的，通过了 LeetCode 的检测

【数据结构与算法】6、栈（Stack）的实现、LeetCode：有效的括号,数据结构与算法,leetcode,算法,职场和发展

class Solution {
    /**
     * 判断是否是有效的括号
     *
     * @param s 待判断的字符串
     * @return true: 是有效的括号; false: 不是有效的括号
     */
    public boolean isValid(String s) {
        if (s == null || s.length() < 2) return false;

        String[] ss = s.split("");

        Stack<String> stack = new Stack<>();

        for (String item : ss) {
            if (isLeft(item)) { // 是左括号：入栈
                stack.push(item);
            } else if (isRight(item)) { // 是右括号：拿出栈顶元素进行比较
                // 拿出了右括号, 但栈为空
                if (stack.isEmpty()) return false;

                String left = stack.pop();

                if (!match(left, item)) return false;
            }
        }

        return stack.isEmpty();
    }

    private boolean match(String left, String right) {
        if ("(".equals(left)) {
            return ")".equals(right);
        } else if ("{".equals(left)) {
            return "}".equals(right);
        } else if ("[".equals(left)) {
            return "]".equals(right);
        }

        return false;
    }

    /**
     * 判断是否是【左】括号
     */
    private boolean isLeft(String s) {
        return "(".equals(s) || "{".equals(s) || "[".equals(s);
    }

    /**
     * 判断是否是【右】括号
     */
    private boolean isRight(String s) {
        return ")".equals(s) || "}".equals(s) || "]".equals(s);
    }

}

② 老师的代码

☘️ 字符串的长度要调用 length() 方法
☘️ 数组的长度是直接访问 length 成员变量
☘️ 取出字符串的每个字符：charAt(int index)，返回值是 char 类型
【 我是先把字符串转换为字符数组 】

class Solution {
    public boolean isValid(String s) {
        if (s == null) return false;
        int length = s.length();
        // 如果只有一个字符（一个括号）或括号是单数, 肯定不是有效的括号
        if (length < 2 || ((length % 2) != 0)) return false;

        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < length; i++) {
            char c = s.charAt(i);

            if (c == '(' || c == '[' || c == '{') { // 是左括号
                stack.push(c);
            } else if (c == ')' || c == ']' || c == '}') { // 是右括号
                // 检查栈是否为空
                if (stack.isEmpty()) return false;

                // 取出栈顶元素进行比较
                Character topElem = stack.pop();
                if (c == ')' && topElem != '(') return false;
                if (c == ']' && topElem != '[') return false;
                if (c == '}' && topElem != '{') return false;
            }
        }

        return stack.isEmpty(); // 如果栈中还有元素，则不是有效的括号
    }
}

③ 利用 HashMap 简化代码

public class Solution {

    private static final Map<Character, Character> MAP = new HashMap<>();

    static { // 初始化 MAP 的值
        MAP.put('(', ')');
        MAP.put('[', ']');
        MAP.put('{', '}');
    }

    /**
     * 判断是否是有效的括号
     *
     * @param s 待判断的字符串
     * @return true: 是有效的括号; false: 不是有效的括号
     */
    public boolean isValid(String s) {
        if (s == null) return false;
        int length = s.length();
        // 如果只有一个字符（一个括号）或括号是单数, 肯定不是有效的括号
        if (length < 2 || ((length % 2) != 0)) return false;

        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < length; i++) {
            char c = s.charAt(i);

            if (MAP.containsKey(c)) { // 是左括号
                stack.push(c);
            } else if (MAP.containsValue(c)) { // 是右括号
                // 检查栈是否为空
                if (stack.isEmpty()) return false;

                // 取出栈顶元素进行比较
                Character topElem = stack.pop();
                if (MAP.get(topElem) != c) return false;
            }
        }

        return stack.isEmpty(); // 如果栈中还有元素，则不是有效的括号
    }

}