栈与队列代码题分析指南

---

一、明确数据结构特性

角度	栈	队列
操作原则	后进先出（LIFO）	先进先出（FIFO）
核心操作	push()/pop()/peek()	offer()/poll()/peek()
JDK 实现	Stack（不推荐） 推荐：ArrayDeque	LinkedList ArrayDeque PriorityQueue
应用场景	函数调用栈、括号匹配、DFS	任务调度、BFS、缓存系统

---

二、问题拆解步骤

1. 识别数据结构需求

   • 若需要反向处理数据（如反转顺序、回溯），优先考虑栈
     示例： 检查括号有效性 ([{}])
   • 若需保持原始顺序（如按序处理任务），选择队列
     示例： 打印二叉树的层级遍历（BFS）

2. 设计操作流程

   • 栈典型模式：

     Stack<Integer> stack = new Stack<>();
     for (元素 : 集合) {
         while (!stack.isEmpty() && 条件) stack.pop(); // 弹栈直到满足条件
         stack.push(元素); // 压栈
     }

   • 队列典型模式：

     Queue<Integer> queue = new LinkedList<>();
     queue.offer(起始点); // 入队
     while (!queue.isEmpty()) {
         int size = queue.size(); // 关键：分层处理
         for (int i = 0; i < size; i++) {
             T node = queue.poll(); // 出队
             if (条件) queue.offer(新元素); // 子节点入队
         }
     }

3. 处理边界与异常

   • 栈：空栈时调用 pop() 会抛出 EmptyStackException → 用 isEmpty() 防御
   • 队列：poll() 返回 null，remove() 抛异常 → 按需选择

---

三、混合结构进阶场景

1. 双栈模拟队列

   • 输入栈 + 输出栈：push 时进输入栈，pop 时若输出栈空则转移数据

   Deque<Integer> inStack = new ArrayDeque<>();
   Deque<Integer> outStack = new ArrayDeque<>();
   
   void push(int x) { inStack.push(x); }
   
   int pop() {
       if (outStack.isEmpty()) 
           while (!inStack.isEmpty()) 
               outStack.push(inStack.pop());
       return outStack.pop();
   }

2. 队列实现栈

   • 单队列循环：push 后立即将前 n-1 个元素重新入队

   Queue<Integer> queue = new LinkedList<>();
   
   void push(int x) {
       queue.offer(x);
       for (int i = 0; i < queue.size() - 1; i++) 
           queue.offer(queue.poll()); // 旋转队列
   }

---

四、复杂度与优化

操作	栈时间复杂度	队列时间复杂度
插入/删除	O(1)	O(1)
空间占用	O(n)	O(n)

• 优化点：
  • 栈：用 Deque 替代 Stack（JDK 官方推荐，性能更优）
  • 队列：需分层处理时（如 BFS），记录 queue.size() 避免冗余操作

---

五、经典题型示例

1. 栈的应用：每日温度（单调栈）

   int[] dailyTemperatures(int[] temps) {
       int[] ans = new int[temps.length];
       Deque<Integer> stack = new ArrayDeque<>(); // 存储下标
       for (int i = 0; i < temps.length; i++) {
           while (!stack.isEmpty() && temps[i] > temps[stack.peek()]) {
               int idx = stack.pop();
               ans[idx] = i - idx; // 计算间隔
           }
           stack.push(i);
       }
       return ans;
   }

2. 队列的应用：二叉树的右视图（BFS+分层）

   List<Integer> rightSideView(TreeNode root) {
       List<Integer> res = new ArrayList<>();
       if (root == null) return res;
       Queue<TreeNode> queue = new LinkedList<>();
       queue.offer(root);
       while (!queue.isEmpty()) {
           int size = queue.size();
           for (int i = 0; i < size; i++) {
               TreeNode node = queue.poll();
               if (i == size - 1) res.add(node.val); // 每层最后一个元素
               if (node.left != null) queue.offer(node.left);
               if (node.right != null) queue.offer(node.right);
           }
       }
       return res;
   }

---

总结分析策略

1. 先判特性：根据 LIFO/FIFO 需求选择数据结构
2. 再定操作：设计压栈/弹栈或入队/出队逻辑流
3. 考虑混合：复杂场景用双栈/双队列组合
4. 优化细节：利用 JDK 新特性（如 ArrayDeque）、防御空值异常
5. 验证场景：栈→递归/回溯；队列→顺序任务/BFS

关键提示：JDK8+ 中优先使用 Deque 实现栈（ArrayDeque）和队列（LinkedList/ArrayDeque），避免线程不安全的 Stack 类。