当前位置：首页 > news >正文

【力扣】stack容器的探索之有效的括号

news 2025/8/9 18:56:28

作者：狮子也疯狂
专栏：《算法详解》
愿你生如夏花之绚烂，幸运永远与你相伴，疯狂常在。

一. 🦁 Stack容器的来历

Stack 栈容器是 Vector 的一个子类，它实现了一个标准的后进先出(LIFO：Last In Frist Out)的栈。它通过 5 个操作方法对 Vector 进行扩展，允许将向量视为堆栈。

1.1 操作栈的方法

Modifier and Type	Method and Description
boolean	enpty() :判断该栈是否为空
E	peek(): 查看栈顶元素
E	pop(): 删除栈顶元素，并返回该值
E	push(E item):将元素推入栈顶
int	search(object o) : 返回该元素的位置

二. 🦁 Stack的使用

这里以力扣第20题为实战案例：查看

2.1 题目

给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号

2.2 分析

这一道题明显是可以使用栈的结构来做，实例化一个栈（Stack< String >）,对字符串做一次循环遍历，在遍历过程中，遇到左括号（无论是什么左括号（{ （ [），都将其对应的右括号放进stack容器中；如果遇到右括号c，则会从stack顶中弹出一个栈顶元素x，将x与c比较，使用flag这一布尔值（默认为true，即匹配）来判断是否匹配，如果不匹配则修改flag为false。到最后遍历结束，如果stack ——>!empty(),则也修改flag为false，最后返回flag。
注意到有效字符串的长度一定为偶数，因此如果字符串的长度为奇数，我们可以直接返回 False，省去后续的遍历判断过程。

2.3 详细算法实现

class Solution {public boolean isValid(String s) {Stack<String> stack = new Stack<>();boolean flag = true;for(int i = 0;i<s.length();i++){char str = s.charAt(i);if(str == '('){stack.push(")");}if(str == '['){stack.push("]");}if(str == '{'){stack.push("}");}if(str == ')'||str == ']'||str == '}'){if(stack.empty()){return false;}String c = stack.pop();if(c.charAt(0) != str){flag = false;break;}}}if(!stack.empty()){flag = false;}return flag;}
}