20. 有效的括号
class Solution {public boolean isValid(String s) {// 边界处理：如果字符串长度是奇数，则不可能配对成功if (s.length() % 2 != 0) {return false;}// 创建一个映射，存储闭合括号对应的开括号Map<Character,Character> map = new HashMap<>();map.put(')', '(');map.put('}', '{');map.put(']', '[');// 创建一个栈，用于存储开括号Deque<Character> stack = new ArrayDeque<>();// 遍历字符串中的每一个字符for (int i = 0; i < s.length(); i++) {char c = s.charAt(i);// 如果是闭合括号if (map.containsKey(c)) {// 检查栈顶是否与当前闭合括号对应的开括号匹配if (stack.isEmpty() || stack.peek() != map.get(c)) {// 不匹配，返回falsereturn false;}// 匹配成功，弹出栈顶的开括号stack.pop();} else {// 如果是开括号，压入栈中stack.push(c);}}// 检查栈是否为空，栈空表示所有开括号都有对应的闭合括号return stack.isEmpty();}}
71. 简化路径
class Solution {// 方法 simplifyPath 接收一个字符串 path，返回简化后的路径public String simplifyPath(String path) {// 根据 "/" 分割路径字符串，得到各级目录名称String[] names = path.split("/");// 创建一个双端队列用于存储有效的路径部分Deque<String> stack = new ArrayDeque<String>();// 遍历每个目录名for (String name : names) {// 如果目录名是 ".."，从栈中弹出上一级目录（如果栈不为空）if ("..".equals(name)) {if (!stack.isEmpty()) {stack.pollLast(); // 弹出栈顶元素，表示回到上一级}// 如果目录名有效（非空且不是 "."）} else if (name.length() > 0 && !".".equals(name)) {stack.offerLast(name); // 将有效的目录名加入栈中}}// 用 StringBuffer 构建简化后的路径StringBuffer ans = new StringBuffer();// 如果栈为空，说明路径为根目录，结果设为 "/"if (stack.isEmpty()) {ans.append('/');} else {// 遍历栈中的内容，构建最终简化路径while (!stack.isEmpty()) {ans.append('/'); // 在每个目录前加上 "/"ans.append(stack.pollFirst()); // 取出并添加目录名}}// 将构建好的路径转换为字符串并返回return ans.toString();}
}
155. 最小栈
class MinStack {// 主栈，存储正常的整数值Deque<Integer> stack;// 辅助栈，存储当前的最小值Deque<Integer> minStack;// 构造函数，初始化主栈和最小值栈public MinStack() {stack = new ArrayDeque<>(); // 初始化主栈minStack = new ArrayDeque<>(); // 初始化最小值栈minStack.push(Integer.MAX_VALUE); // 推入一个最大值作为初始最小值}// 推入新元素到主栈public void push(int val) {stack.push(val); // 将值推入主栈// 将当前值与 minStack 顶部元素比较，推入较小的值到 minStackminStack.push(Math.min(val, minStack.peek()));}// 弹出主栈的顶部元素public void pop() {stack.pop(); // 从主栈弹出顶部元素minStack.pop(); // 从最小值栈弹出对应元素}// 获取主栈的顶部元素public int top() {return stack.peek(); // 返回主栈的顶部元素}// 获取当前栈的最小值public int getMin() {return minStack.peek(); // 返回最小值栈的顶部元素（即当前最小值）}
}
150. 逆波兰表达式求值
class Solution {public int evalRPN(String[] tokens) {Deque<Integer> stack = new LinkedList<>();for (int i = 0; i < tokens.length; i++) {if (isNumber(tokens[i])) {stack.push(Integer.parseInt(tokens[i]));} else {Integer a = stack.pop();Integer b = stack.pop();switch(tokens[i]) {case "+":stack.push(b + a);break;case "-":stack.push(b - a);break;case "*":stack.push(b * a);break;case "/":stack.push(b / a);break;}}}return stack.pop();}public boolean isNumber(String token) {return !("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token));}}
