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();*/
)
)
