第3天：栈与队列算法 - 问题分析与Java实现
1. 问题分析
问题1：有效的括号
问题描述
给定一个只包含 '('、)、'{'、'}'、'['、']' 的字符串，判断输入字符串是否有效。
示例
输入: s = "()"
输出: true输入: s = "()[]{}"
输出: true输入: s = "(]"
输出: false
2. 解决方案（多种方法）
方法1：使用栈（O(n))
思路：
- 遍历字符串，使用栈来跟踪左括号。
- 对于每个右括号，检查它是否匹配栈顶的左括号。
- 如果匹配，弹出栈顶元素；否则，返回false。
- 如果栈为空，返回true，否则返回false。
public boolean isValid(String s) {Stack<Character> stack = new Stack<>();for (char c : s.toCharArray()) {if (c == '(' || c == '[' || c == '{') {stack.push(c);} else {if (stack.isEmpty()) return false;char top = stack.pop();if (c == ')' && top != '(') return false;if (c == ']' && top != '[') return false;if (c == '}' && top != '{') return false;}}return stack.isEmpty();
}
优点：
- 时间复杂度：O(n)，遍历字符串一次。
- 空间复杂度：O(n)，使用栈来存储字符。
问题2：用栈实现队列
问题描述
用两个栈实现一个队列，队列应该实现以下操作：
push(x)：将元素x推到队列的末尾。pop()：从队列的前端移除元素。peek()：获取队列前端的元素。empty()：返回队列是否为空。
示例
MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // 返回 1
queue.pop(); // 返回 1
queue.empty(); // 返回 false
2. 解决方案（多种方法）
方法1：使用两个栈（O(1)的push，O(n)的pop和peek）
思路：
- 使用两个栈：一个用于入队，一个用于
出队。
- 出队或查看队列前端时，如果出队栈为空，则从入队栈中转移元素到出队栈。
- 这样可以保证元素按照FIFO顺序被处理。
class MyQueue {private Stack<Integer> stack1;private Stack<Integer> stack2;public MyQueue() {stack1 = new Stack<>();stack2 = new Stack<>();}public void push(int x) {stack1.push(x);}public int pop() {if (stack2.isEmpty()) {while (!stack1.isEmpty()) {stack2.push(stack1.pop());}}return stack2.pop();}public int peek() {if (stack2.isEmpty()) {while (!stack1.isEmpty()) {stack2.push(stack1.pop());}}return stack2.peek();}public boolean empty() {return stack1.isEmpty() && stack2.isEmpty();}
}
优点：
- 时间复杂度：**O(1)**的push，**O(n)**的pop和peek。
- 空间复杂度：O(n)，使用了两个栈。
问题3：用队列实现栈
问题描述
用两个队列实现一个栈，栈应该实现以下操作：
push(x)：将元素x推到栈顶。pop()：移除栈顶的元素。top()：获取栈顶元素。empty()：返回栈是否为空。
示例
MyStack stack = new MyStack();
stack.push(1);
stack.push(2);
stack.top(); // 返回 2
stack.pop(); // 返回 2
stack.empty(); // 返回 false
2. 解决方案（多种方法）
方法1：使用两个队列（O(n)的pop，O(1)的push）
思路：
- 使用两个队列，一个存储元素，另一个临时保存元素进行pop操作。
- 在模拟栈操作时，将除最后一个元素外的所有元素转移到第二个队列。
class MyStack {private Queue<Integer> queue1;private Queue<Integer> queue2;public MyStack() {queue1 = new LinkedList<>();queue2 = new LinkedList<>();}public void push(int x) {queue1.offer(x);}public int pop() {while (queue1.size() > 1) {queue2.offer(queue1.poll());}int top = queue1.poll();Queue<Integer> temp = queue1;queue1 = queue2;queue2 = temp;return top;}public int top() {while (queue1.size() > 1) {queue2.offer(queue1.poll());}int top = queue1.peek();queue2.offer(queue1.poll());Queue<Integer> temp = queue1;queue1 = queue2;queue2 = temp;return top;}public boolean empty() {return queue1.isEmpty();}
}
优点：
- 时间复杂度：**O(n)**的pop和top，**O(1)**的push。
- 空间复杂度：O(n)，使用了两个队列。
总结
| 问题 | 最优解法 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 有效括号 | 使用栈 | O(n) | O(n) |
| 用栈实现队列 | 使用两个栈 | **O(1)**的push，**O(n)**的pop和peek | O(n) |
| 用队列实现栈 | 使用两个队列 | **O(n)**的pop和top，**O(1)**的push | O(n) |
🔥 掌握这些栈和队列算法，强化大厂面试题的解决能力！ 🚀
