“关于堆栈”
题干
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
示例
示例 1：
输入：s = "()" 输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]" 输出：false
示例 4：
输入：s = "([)]" 输出：false
示例 5：
输入：s = "{[]}"
输出：true
提示：
1 <= s.length <= 104s仅由括号'()[]{}'组成
Java堆栈
如果单纯的想实现后进先出堆栈，可以用java.util.Stack，注意取元素时，pop()为出栈并接收返回值，而peek()只是获得栈顶的值（不出栈）具体查看下面的代码：
peek意为窥视，java中很多数据结构都有peek()方法，作用都是窥视一眼首个元素的值
import java.util.Stack;
/**
* @author stitch
* @version Main.java, v 0.1 2021年10月29日 4:22 下午 stitch
*/
public class Main {
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
stack.push(0);
stack.push(1);
stack.push(2);
stack.push(3);
// 3
System.out.println(stack.peek());
// 3
System.out.println(stack.pop());
// 2
System.out.println(stack.pop());
// 1
System.out.println(stack.pop());
}
}
Java还有一种更通用的数据结构，双向队列deque，支持双向插入、双向删除，具体如下：
import java.util.Deque;
import java.util.LinkedList;
/**
* @author stitch
* @version Main.java, v 0.1 2021年10月29日 4:22 下午 stitch
*/
public class Main {
public static void main(String[] args) {
// deque implemented by linked list
Deque<Integer> queue = new LinkedList<>();
queue.addFirst(1);
queue.addFirst(2);
queue.addLast(3);
queue.addLast(4);
// [2, 1, 3, 4]
System.out.println(queue);
// 2
System.out.println(queue.removeFirst());
// 4
System.out.println(queue.removeLast());
}
}
题解
由于一个右括号必定匹配离它最近的一个左括号，因此括号的合法性判断是一个典型的堆栈问题
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;
/**
* @author stitch
* @version Main.java, v 0.1 2021年10月29日 4:22 下午 stitch
*/
public class Main {
public boolean isValid(String s) {
Map<Character, Character> dict = new HashMap<>();
dict.put(')', '(');
dict.put(']', '[');
dict.put('}', '{');
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); ++i) {
char c = s.charAt(i);
if (dict.containsKey(c)) {
if (stack.isEmpty() || dict.get(c) != stack.peek()) {
return false;
}
stack.pop();
} else {
stack.push(c);
}
}
return stack.isEmpty();
}
public static void main(String[] args) {
System.out.println(new Main().isValid("()[]{}"));
System.out.println(new Main().isValid("([)]"));
}
}
