1. 常用表格总结
| 数据结构 | 常见应用场景 | 时间复杂度（入/出/查） | LeetCode 高频题 |
|---|---|---|---|
| 栈（Stack） | 括号匹配、单调栈、DFS | 入栈 O(1) / 出栈 O(1) / 查顶 O(1) | 20 有效的括号, 155 最小栈, 739 每日温度 |
| 队列（Queue） | 层序遍历、BFS、滑动窗口 | 入队 O(1) / 出队 O(1) / 查头 O(1) | 225 用队列实现栈, 102 二叉树层序遍历, 239 滑动窗口最大值 |
| 双端队列（Deque） | 单调队列、滑动窗口 | 前后插入 O(1) / 前后删除 O(1) | 641 设计双端队列, 239 滑动窗口最大值 |
| 优先队列（Heap） | 最大/最小值快速获取 | 插入 O(log n) / 删除 O(log n) / 取堆顶 O(1) | 23 合并K个有序链表, 347 前 K 个高频元素 |
2. 常用解题思路
栈（Stack）
括号匹配类：遇到左括号入栈，遇到右括号检查栈顶
单调栈：维护单调递增/递减栈，用于“下一个更大/更小元素”
模拟函数调用：递归展开或表达式求值
// 栈常见写法 Stack<Integer> stack = new Stack<>();// 入栈 stack.push(x);// 出栈 int val = stack.pop();// 查看栈顶 int top = stack.peek();// 判空 if(stack.isEmpty()) { ... }队列（Queue）
BFS：树/图最短路径，逐层扩展
层序遍历：树按层输出
循环队列：利用数组实现环形结构
// 普通队列 Queue<Integer> queue = new LinkedList<>();// 入队 queue.offer(x);// 出队 int val = queue.poll();// 查看队头 int head = queue.peek();// 判空 if(queue.isEmpty()) { ... }双端队列（Deque）
单调队列：保证队首是最大/最小值，常用于滑动窗口问题
双向扩展搜索（BFS 优化）
优先队列（Heap）
维护动态区间的最大/最小值
经典应用：前 K 个最大值，合并 K 个有序列表
3. 常见注意点
栈模拟递归时要注意 栈溢出 问题
队列的 BFS 中要注意 访问过的节点要标记（避免死循环）
单调栈/队列需要 合理出栈/出队 保证单调性
循环队列数组实现时下标要用 取模运算
4. 高频模板
栈：括号匹配（LC 20）
public boolean isValid(String s) {Stack<Character> stack = new Stack<>();for (char c : s.toCharArray()) {if (c == '(') stack.push(')');else if (c == '[') stack.push(']');else if (c == '{') stack.push('}');else if (stack.isEmpty() || stack.pop() != c) return false;}return stack.isEmpty();
}
单调栈：下一个更大元素（LC 496/739）
Stack<Integer> st = new Stack<>();
for (int i = n - 1; i >= 0; i--) {while (!st.isEmpty() && st.peek() <= nums[i]) st.pop();ans[i] = st.isEmpty() ? -1 : st.peek();st.push(nums[i]);
}
队列：BFS 层序遍历（LC 102）
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {int size = q.size();List<Integer> level = new ArrayList<>();for (int i = 0; i < size; i++) {TreeNode node = q.poll();level.add(node.val);if (node.left != null) q.offer(node.left);if (node.right != null) q.offer(node.right);}ans.add(level);
}
单调队列：滑动窗口最大值（LC 239）
Deque<Integer> dq = new ArrayDeque<>();
for (int i = 0; i < n; i++) {if (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst();while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) dq.pollLast();dq.offerLast(i);if (i >= k - 1) ans[i - k + 1] = nums[dq.peekFirst()];
}
5 leetcode题目
232用栈实现队列
class MyQueue {private Stack<Integer> inStack;private Stack<Integer> outStack;public MyQueue() {inStack = new Stack<>();outStack = new Stack<>();} public void push(int x) {inStack.push(x);}public int pop() {shiftStack();return outStack.pop();}public int peek() {shiftStack();return outStack.peek();}public boolean empty() {return inStack.isEmpty() && outStack.isEmpty();}private void shiftStack(){if(outStack.isEmpty()){while(!inStack.isEmpty()){outStack.push(inStack.pop());}}}
}/*** Your MyQueue object will be instantiated and called as such:* MyQueue obj = new MyQueue();* obj.push(x);* int param_2 = obj.pop();* int param_3 = obj.peek();* boolean param_4 = obj.empty();*/225用队列实现栈
class MyStack {private Queue<Integer> queue1;private Queue<Integer> queue2;public MyStack() {queue1 = new LinkedList<>();queue2 = new LinkedList<>();}public void push(int x) {queue2.offer(x); //暂时while(!queue1.isEmpty()){queue2.offer(queue1.poll());}Queue<Integer> temp = queue1;queue1 = queue2;queue2 = temp;}public int pop() {return queue1.poll();}public int top() {return queue1.peek();}public boolean empty() {return queue1.isEmpty();}
}/*** Your MyStack object will be instantiated and called as such:* MyStack obj = new MyStack();* obj.push(x);* int param_2 = obj.pop();* int param_3 = obj.top();* boolean param_4 = obj.empty();*/
)
)
