LeetCode刷题笔记：栈与有效括号问题解析

"这篇刷题笔记主要探讨了LeetCode中关于栈的应用，特别是针对有效括号问题（题号20）的解决方案。笔记涵盖了有效括号的定义、解题思路和示例，以及作者实现的栈类代码。" 在LeetCode的这道题目中，我们需要判断一个由六种括号组成的字符串是否有效。有效字符串的要求是： 1. 左括号必须用相同类型的右括号闭合。 2. 左括号必须按照正确的顺序闭合。 3. 空字符串也被认为是有效字符串。 常规解法是通过栈数据结构来实现。具体步骤如下： 1. 初始化一个空栈S。 2. 遍历输入字符串中的每一个字符。 3. 如果遇到一个开括号，将其压入栈中。 4. 当遇到一个闭括号时，检查栈顶的元素是否为对应的开括号。如果是，就将栈顶元素弹出；如果不是，说明字符串无效。 5. 最后，如果栈为空，说明所有括号已经匹配完成，字符串有效；反之，栈非空，则无效。 作者实现了一个简单的栈类`Stack`，包含以下方法： - `__init__(self, limit=10)`: 初始化栈，设定栈的默认容量为10。 - `push(self, data)`: 向栈中添加元素，如果栈已满则抛出异常。 - `pop(self)`: 弹出栈顶元素，栈为空时返回False。 - `peek(self)`: 查看栈顶元素，栈为空时不进行操作。 - `is_empty(self)`: 判断栈是否为空。 - `size(self)`: 返回栈中元素的数量。 在解决有效括号问题的`Solution`类中，定义了一个`isValid(self, s)`方法，这个方法将使用上述栈类来实现有效括号的检查。 这个问题的关键在于理解栈的特性——后进先出（LIFO），它使得我们可以用栈来追踪当前未闭合的左括号，当遇到右括号时，检查栈顶的左括号，如果匹配则消除，否则标记为无效。 通过这种方法，我们可以有效地解决括号匹配问题，并且这个思路同样适用于其他需要检查配对关系的问题，如XML标签的闭合等。在编程面试中，此类问题经常出现，掌握好这种解题策略对于提升算法能力非常有帮助。