队列

本章题海战术

典型例题	leetcode题目	leetcode链接
用栈实现队列	leetcode 232	https://leetcode.cn/problems/implement-queue-using-stacks/description/
滑动窗口最大值	leetcode 239	https://leetcode.cn/problems/sliding-window-maximum/description/
二叉树层序遍历	leetcode 102	https://leetcode.cn/problems/binary-tree-level-order-traversal/description/
二叉树的锯齿形层序遍历	leetcode 103	https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/description/
二叉树的最大深度	leetcode 104	https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/
二叉树右视图	leetcode 199	https://leetcode.cn/problems/binary-tree-right-side-view/description/
循环队列设计	leetcode 622	https://leetcode.cn/problems/design-circular-queue/description/

队列

面试官您好，队列是算法面试的高频考点，核心是 先进先出 (FIFO) 的操作特性，我从基础特性、高频考题、避坑要点三个维度来回答～

核心基础：队列的分类与 Java 实现 📚

队列本质是操作受限的线性表，算法面试里最常用 3 种形态，Java 中统一优先用ArrayDeque实现（基于动态数组，性能优于LinkedList）：

队列类型	操作特性	典型应用场景
普通队列	仅队尾入、队首出	BFS 层序遍历、广度优先搜索
双端队列 (Deque)	头尾两端均可入队、出队	单调队列、滑动窗口类题目
单调队列	手动维护队内元素单调递增 / 递减	区间最值、滑动窗口最大值

队列基础结构示意图

💡 面试加分细节：非并发场景下，ArrayDeque的入队出队均摊 O (1)，缓存命中率比链表实现更高，是算法题的首选。

高频必考题 & 解题模板 🚀

1. 用栈实现队列（LeetCode 232・简单高频）

题目：仅用两个栈实现队列的入队、出队、取队首、判空操作。

核心思路：双栈分工，inStack只管入队，outStack只管出队；出队时若outStack为空，一次性把inStack所有元素倒入outStack，保证 FIFO 顺序。

核心代码

class MyQueue {
    Deque<Integer> inStack = new ArrayDeque<>();
    Deque<Integer> outStack = new ArrayDeque<>();

    // 入队：直接压入输入栈
    public void push(int x) {
        inStack.push(x);
    }
    
    // 出队：输出栈空了就倒数据
    public int pop() {
        if (outStack.isEmpty()) {
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop());
            }
        }
        return outStack.pop();
    }
    
    public boolean empty() {
        return inStack.isEmpty() && outStack.isEmpty();
    }
}

✅ 考点点睛：每个元素最多入栈、出栈各 2 次，摊还时间复杂度 O (1)—— 这是区分候选人水平的关键，不要笼统说 O (n)。

2. 滑动窗口最大值（LeetCode 239・困难标杆题）

题目：给定数组nums和窗口大小k，返回每个滑动窗口内的最大值。

核心思路：维护单调递减的双端队列，队列存储数组下标：

1. 新元素入队前，不断弹出队尾所有 ≤ 当前值的元素，保证队列单调递减
2. 检查队首下标是否超出窗口左边界，超出则弹出队首
3. 窗口形成后（索引≥k-1），队首对应的值就是当前窗口最大值

单调队列执行流程示意图

核心代码

public int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    int[] res = new int[n - k + 1];
    Deque<Integer> deque = new ArrayDeque<>();
    
    for (int i = 0; i < n; i++) {
        // 1. 维护单调递减：队尾值<=当前值，持续弹出
        while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
            deque.pollLast();
        }
        deque.offerLast(i);
        
        // 2. 队首超出窗口左边界，弹出
        if (deque.peekFirst() <= i - k) {
            deque.pollFirst();
        }
        
        // 3. 窗口形成，记录结果
        if (i >= k - 1) {
            res[i - k + 1] = nums[deque.peekFirst()];
        }
    }
    return res;
}

✅ 考点点睛：整体时间复杂度 O (n)，每个元素最多入队、出队各 1 次；队列存下标而非值，是为了方便判断元素是否超出窗口边界。

3. 二叉树层序遍历（LeetCode 102・BFS 模板题）

题目：按层遍历二叉树，逐层返回节点值。

核心思路：队列存储当前层所有节点，每次遍历前先记录队列大小（即当前层节点数），批量处理完一层再处理下一层。

核心代码

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) return res;
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);
    
    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        List<Integer> levelVals = new ArrayList<>();
        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();
            levelVals.add(node.val);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        res.add(levelVals);
    }
    return res;
}

✅ 考点点睛：这是 BFS 的通用模板，锯齿形层序(leetcode 103)、树的最大深度(leetcode 104)、二叉树右视图(leetcode 199)等题目都基于此模板改造。

考点 & 复杂度汇总表 📊

题目	时间复杂度	空间复杂度	考察频率	核心考察点
用栈实现队列(leetcode 232)	均摊 O (1)	O(n)	⭐⭐⭐⭐⭐	摊还复杂度分析、栈队列特性转换
滑动窗口最大值(leetcode 239)	O(n)	O(k)	⭐⭐⭐⭐⭐	单调队列思想、边界处理细节
循环队列设计(leetcode 622)	O(1)	O(n)	⭐⭐⭐	数组模拟、空满状态判断
二叉树层序遍历(leetcode 102)	O(n)	O(n)	⭐⭐⭐⭐	BFS 思想、队列经典落地场景

面试避坑提醒 ⚠️

1. 实现选择坑：不要默认用LinkedList实现队列，主动提及ArrayDeque在非并发场景的性能优势，体现细节积累。
2. 单调队列坑：队列必须存数组下标，存值无法判断元素是否滑出窗口边界，这是高频写错的点。
3. 复杂度坑：用栈实现队列不要说时间复杂度 O (n)，一定要强调均摊 O (1)，这是拉开差距的得分点。
4. 循环队列坑：主动讲清两种空满判断方案 —— 牺牲一个数组位置 / 用 count 变量计数，体现思考全面性。

接下来我补充一下队列核心算法题的代码设计亮点，以及对应场景下的技术难点和标准解决方案。

核心代码 & 技术亮点拆解 ✨

针对三道最高频的队列考题，我标注了代码里的设计考量和面试加分点：

1. 用栈实现队列（LeetCode 232）

class MyQueue {
    // 亮点1：摒弃Java不推荐的Stack类，选用轻量的ArrayDeque，规避同步开销与老旧设计缺陷
    Deque<Integer> inStack = new ArrayDeque<>();
    Deque<Integer> outStack = new ArrayDeque<>();

    // 入队直接压入输入栈，O(1)
    public void push(int x) {
        inStack.push(x);
    }
    
    public int pop() {
        // 亮点2：懒加载式倒栈——仅输出栈为空时批量倒数据
        // 把单次O(n)的倒栈成本平摊到所有操作上，实现均摊时间复杂度O(1)
        if (outStack.isEmpty()) {
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop());
            }
        }
        return outStack.pop();
    }

    public int peek() {
        // 亮点3：复用倒栈逻辑，统一维护双栈状态，避免代码冗余
        if (outStack.isEmpty()) {
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop());
            }
        }
        return outStack.peek();
    }
    
    public boolean empty() {
        return inStack.isEmpty() && outStack.isEmpty();
    }
}

亮点总结：核心拉分点是「均摊复杂度」的设计思想，而非简单实现功能；主动提及ArrayDeque与Stack的选型差异，能体现 Java 编码规范积累。

2. 滑动窗口最大值（LeetCode 239）

public int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    int[] res = new int[n - k + 1];
    // 亮点1：队列存数组下标而非元素值，同时解决「窗口边界判断」和「取值」两个问题
    Deque<Integer> deque = new ArrayDeque<>();
    
    for (int i = 0; i < n; i++) {
        // 亮点2：严格维护单调递减：队尾元素<=当前值则持续弹出
        // 保证队列头部永远是当前窗口最大值的下标
        while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
            deque.pollLast();
        }
        deque.offerLast(i);
        
        // 亮点3：入队后再校验队首越界，执行顺序不可颠倒
        // 新元素必然在窗口内，只需淘汰滑出左边界的队首元素
        if (deque.peekFirst() <= i - k) {
            deque.pollFirst();
        }
        
        // 亮点4：窗口成型后再记录结果，避免输出无效值
        if (i >= k - 1) {
            res[i - k + 1] = nums[deque.peekFirst()];
        }
    }
    return res;
}

亮点总结：整体时间复杂度 O (n)，每个元素仅入队、出队各一次，性能优于暴力法 O (nk) 和堆解法 O (nlogk)；「存下标」是单调队列的通用设计技巧，可迁移到所有区间最值类题目。

3. 二叉树层序遍历（LeetCode 102）

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    // 亮点1：空值前置判断，提前拦截空指针，提升代码鲁棒性
    if (root == null) return res;
    
    // 亮点2：面向Queue接口编程，用ArrayDeque作为实现，符合Java最佳实践
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);
    
    while (!queue.isEmpty()) {
        // 亮点3：遍历前先锁定当前层节点数，划清层级边界
        // 避免遍历过程中子节点入队，导致队列长度变化打乱层级划分
        int levelSize = queue.size();
        List<Integer> levelVals = new ArrayList<>(levelSize);
        
        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();
            levelVals.add(node.val);
            // 亮点4：先左后右顺序入队，严格保证层序遍历顺序
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        res.add(levelVals);
    }
    return res;
}

亮点总结：「先记 size 再遍历」是所有 BFS 分层题的通用模板，可无缝扩展到锯齿形遍历、二叉树右视图、层序遍历 II 等变种题；提前初始化 ArrayList 容量，体现性能优化细节意识。

队列算法场景 技术难点与解决方案汇总 🛠️

我整理了队列类题目最容易踩坑的 5 个核心难点，以及对应的标准解法：

技术难点	问题本质	标准解决方案	代码落地要点
栈模拟队列出队效率低	每次出队都倒栈，单次操作 O (n)	双栈分工 + 懒加载倒栈：输入栈只管入，输出栈空了再批量倒数据	倒栈逻辑仅在outStack.isEmpty()时触发，保证每个元素最多倒一次
单调队列无法兼顾最值与窗口边界	只存元素值，无法判断是否滑出窗口	队列存储数组下标，而非元素值	通过i - k计算窗口左边界，直接比对队首下标即可判断越界
循环队列空 / 满状态歧义	队首、队尾指针重合时，无法区分是空还是满	方案 1：牺牲一个数组位置，(rear+1)%capacity == front 判定为满 方案 2：维护size计数变量，直接通过计数判断	算法题优先用 size 计数，逻辑更直观，代码不易错
BFS 遍历无法区分节点所属层级	队列动态增减，无法感知层与层的边界	分层处理：每层遍历前先记录队列当前 size，按 size 批量处理本层	int levelSize = queue.size(); 必须写在 for 循环外层，写在内层必错
双端队列 API 混用导致逻辑错误	分不清队首 / 队尾的入队出队方法	统一使用First/Last后缀 API： 队首：offerFirst / pollFirst / peekFirst 队尾：offerLast / pollLast / peekLast	禁止用push/pop操作双端队列，避免和栈的语义混淆

面试加分延伸 💡

如果面试官追问工程落地，可以补充一句：

算法题中非并发场景优先选ArrayDeque，追求极致性能；实际工程的并发场景下，会选用 JUC 包下的ArrayBlockingQueue、LinkedBlockingQueue等并发队列，基于锁和 CAS 保证线程安全。

真实面试模拟

真实面试模拟

面试官 😊：

「看你简历写了对数据结构比较熟，那咱们先来道热身题：用两个栈实现一个队列(leetcode 232)，支持 push、pop、peek、empty 操作。你先说说思路，然后白板上写下代码，最后分析下复杂度。」

候选人 💪：

「好嘞。这道题关键是要用栈（LIFO）模拟队列（FIFO）。我准备用两个栈，一个叫 stackIn 负责入队，一个叫 stackOut 负责出队。大概思想就是“倒腾”——出队时，如果 stackOut 是空的，就把 stackIn 的所有元素都倒进 stackOut，这样栈顶就变成队头了。」

面试官 🤔：

「能画个图解释下“倒腾”的过程吗？」

候选人 ✍️：

「没问题，我随手画一下。」

假设依次 push 1、2、3，此刻：

📦 stackIn 里放着 [1,2,3， 1在底，3在顶]

现在第一次 pop()：把 stackIn 逐个弹出并压入 stackOut：

🔁 倒完后 stackOut 栈顶是 1，正好是队列的队头，弹出 1 即可。

之后如果再 push(4)：

🧘 stackIn 继续收新元素，互不干扰；stackOut 不为空时直接出栈。只有 stackOut 空了，才再次倒腾。

面试官 👍：

「图很清晰。那你按这个思路把代码写出来吧。」

候选人 💻（边写边说）：

「好的，Java 实现，我用标准库的 Stack，封装成一个 MyQueue 类。」

class MyQueue {
    private Stack<Integer> stackIn;
    private Stack<Integer> stackOut;

    public MyQueue() {
        stackIn = new Stack<>();
        stackOut = new Stack<>();
    }

    // 入队：O(1)
    public void push(int x) {
        stackIn.push(x);
    }

    // 出队：均摊 O(1)
    public int pop() {
        transferIfNeeded();
        return stackOut.pop();
    }

    // 看队头
    public int peek() {
        transferIfNeeded();
        return stackOut.peek();
    }

    // 两个栈都空才算空
    public boolean empty() {
        return stackIn.isEmpty() && stackOut.isEmpty();
    }

    // 核心：stackOut 空时，把 stackIn 全部倒入
    private void transferIfNeeded() {
        if (stackOut.isEmpty()) {
            while (!stackIn.isEmpty()) {
                stackOut.push(stackIn.pop());
            }
        }
    }
}

面试官 🧐：

「代码干净，transferIfNeeded 封装得不错。那你说说 pop 的时间复杂度是多少？好多人会直接说 O(n)，你怎么看？」

候选人 🎯：

「单个 pop 的最坏情况确实是 O(n)，因为可能触发 while 循环把整个 stackIn 倒空。但从整体来看，每个元素只会从 stackIn 移到 stackOut 一次，再从 stackOut 弹出一次，总共常数次操作。所以用均摊分析，pop 是 均摊 O(1)，push 是 O(1)，peek 和 empty 也都是 O(1)。」

我还画了张每个元素的生命周期图，方便理解：

🕊 每个元素经历：1次入栈→ 至多1次倒手→ 1次出栈，总代价是常数。

面试官 😊：

「嗯，提到均摊分析是加分项。这道题主要看你能否讲清 LIFO ↔ FIFO 的转化、代码的边界，以及复杂度意识。到这里你回答得挺完整了。」

候选人 🙏：

「谢谢面试官，如果还有时间，我还可以展开讲讲循环队列(leetcode 622)或者滑动窗口最大值(leetcode 239)，都跟队列有关。」

面试官 😊：

「那你再总结一下这道题的核心代码块和技术难点吧，以及你是怎么解决的。」

候选人 🧑‍💻：

「好的，这道题的核心，其实就是惰性转移思想，我用一段关键方法体现。」

🔑 核心代码 & 技术亮点

// 核心：惰性转移 —— 只在必要时才倒腾
private void transferIfNeeded() {
    if (stackOut.isEmpty()) {          // 出队栈为空才触发
        while (!stackIn.isEmpty()) {
            stackOut.push(stackIn.pop());
        }
    }
}

✨ 技术亮点：

1. 惰性求值 – 不提前搬运，只有 stackOut 空了才倒，避免了每次 pop 都 O(n)
2. 每个元素只倒一次 – 入 stackIn → 出 stackIn 进 stackOut → 出 stackOut，总操作次数固定，均摊 O(1)
3. 职责分离 – stackIn 只管进，stackOut 只管出，逻辑清晰，可读性强
4. 线程不安全下的纯粹 – 代码极简，没有额外锁或同步，完全用栈的原语表达队列语义

⚙️ 技术难点 & 解决方案

难点	为什么难	解决方案
🎯 FIFO 语义实现	栈天然 LIFO，和队列冲突	双栈倒置：入队栈顺序为逆序，出队栈再倒一次恢复先进先出
🔁 连续混合操作的边界	如果在 stackOut 不为空时继续 push，新元素不能破坏原有顺序	规定 transferIfNeeded 仅在 stackOut 为空时触发，新元素暂存 stackIn，等下一轮倒腾
⏱ 性能陷阱	每次 pop 都倒会导致 O(n²)	采用均摊分析，证明每个元素最多参与一次倒腾，总复杂度 O(n) over n 次操作 = O(1) 均摊
🧠 理解成本	新手容易困惑“为什么 pop 有时慢有时快”	画出元素生命周期（push→in→out→pop），强调每个元素只动常数次
🔍 peek 与 pop 的复用	需要保证 peek 不删除元素且遵循同样逻辑	复用 transferIfNeeded 后再调用 stackOut.peek()，避免重复代码
📉 空判断	两个栈的状态共同决定队列是否为空	必须 stackIn.isEmpty() && stackOut.isEmpty()，否则可能出现 stackIn 有元素但 stackOut 空时误判为空

🌟 生命周期可视化

🧸 每个元素旅程：进 stackIn（一次 push）→ 必要时倒进 stackOut（一次 pop + 一次 push）→ 离开（一次 pop），全程 O(3) = O(1)。

这样，无论压测还是面试，都能把「为什么用两个栈」「为什么快」说得明明白白 👍

面试官 😄：

「总结得很到位，惰性转移和均摊分析都抓住了。那这道题就到这里，准备进入下一题。」

候选人 🙏：

「谢谢面试官，我准备好了。」