罗罗编程学习记录
本页内容 展开查看

02.3.2.3 队列、双端队列与循环队列

所属:全栈开发面试题库 / 02 数据结构与算法 / 02.3 链表、栈与队列 / 02.3.2 栈与队列、单调栈

02.3.2.3-001 队列是什么结构?

一句话结论

队列是先进先出(FIFO)线性结构:队尾入队、队头出队;支持 offer/peek/poll/isEmpty;适配顺序处理与 BFS 场景。

概念解释

  • FIFO:先到先服务。
  • 队头:出队端。
  • 队尾:入队端。

原理流程

  1. 元素队尾入队。
  2. 队头出队。
  3. 空队列不可取。

代码 / 图示

队头 → a b c ← 队尾
出队:a
入队:d → b c d

常见误区

  • 误区:队列可从中间取;正解:只暴露队头队尾。
  • 误区:队列是栈反过来;正解:FIFO 与 LIFO 用途不同。

追问

  • Q:队列用链表还是数组? A:都可;循环数组避免头部搬迁。
  • Q:队列满怎么办? A:固定容量拒绝或动态扩容。

02.3.2.3-002 队列的链表实现怎么做?

一句话结论

链表维护队头队尾两个引用;入队挂到队尾,出队摘除队头;首尾都有引用,增删均 O(1);空间 O(n)。

概念解释

  • head:队头引用。
  • tail:队尾引用。
  • 空队列两者为空。

原理流程

  1. 入队:空则头尾同指新节点,否则 tail.next 后移。
  2. 出队:head 后移。
  3. 出空后 tail 置空。

代码 / 示例

class LinkedQueue {
    private Node head, tail;
    private static class Node {
        int val; Node next;
        Node(int v) { val = v; }
    }
    public void offer(int v) {
        Node n = new Node(v);
        if (tail == null) head = tail = n;
        else { tail.next = n; tail = n; }
    }
    public int poll() {
        int v = head.val;
        head = head.next;
        if (head == null) tail = null;
        return v;
    }
}

常见误区

  • 误区:只维护 head 找尾;正解:双引用 O(1) 入队。
  • 误区:出空后 tail 残留;正解:最后一节点出队时 tail 置 null。

追问

  • Q:链表队列节点开销? A:每节点额外指针空间。
  • Q:并发队列? A:需加锁或无锁结构,基础版非线程安全。

02.3.2.3-003 用两个栈实现队列(LC 232)怎么做?

一句话结论

入队栈压入;出队时若出队栈为空,把入队栈全部弹转入出队栈,再弹出;两次栈反转得到 FIFO;均摊 O(1),空间 O(n)。

概念解释

  • in:入队专用。
  • out:出队专用。
  • 批量倒栈反转顺序。

原理流程

  1. push:in.push。
  2. pop/peek:out 空则倒空 in,再 out.pop。
  3. 非空直接 out.pop。

代码 / 示例

class MyQueue {
    private final Deque<Integer> in = new ArrayDeque<>();
    private final Deque<Integer> out = new ArrayDeque<>();
    public void push(int x) { in.push(x); }
    public int pop() {
        if (out.isEmpty()) while (!in.isEmpty()) out.push(in.pop());
        return out.pop();
    }
    public int peek() {
        if (out.isEmpty()) while (!in.isEmpty()) out.push(in.pop());
        return out.peek();
    }
    public boolean empty() { return in.isEmpty() && out.isEmpty(); }
}

常见误区

  • 误区:每次出队都倒栈;正解:out 非空直接弹,避免重复反转。
  • 误区:倒栈顺序反了;正解:in 弹出入 out,栈顶变队头。

追问

  • Q:均摊为什么 O(1)? A:每个元素至多倒栈一次。
  • Q:两栈都空判空? A:两栈同时为空才是空队列。

02.3.2.3-004 队列和栈分别适合什么场景?

一句话结论

队列适配顺序、层级、广度优先(BFS、层序、排队);栈适配嵌套、回溯、最近关系(括号、DFS、撤销);按“先到先处理”还是“最近先处理”选择。

概念解释

  • 队列:顺序展开。
  • 栈:逆序回溯。
  • 场景映射。

原理流程

  1. 判断处理顺序。
  2. 广度用队列,深度用栈。
  3. 嵌套配对用栈。

代码 / 图示

BFS:队列逐层
DFS:栈回溯
括号:栈配对

常见误区

  • 误区:BFS 用栈;正解:广度优先必须队列。
  • 误区:层序遍历用栈;正解:同层顺序由队列保证。

追问

  • Q:递归 DFS 底层结构? A:调用栈。
  • Q:消息排队用什么? A:队列。

02.3.2.3-005 双端队列(Deque)是什么?

一句话结论

双端队列两端都可入队出队;可同时当栈、普通队列使用;Java Deque 接口,ArrayDeque 为数组实现;栈语义 push/pop 走同一端,队列语义 offer/poll 走两端。

概念解释

  • 两端:队头队尾均可操作。
  • 灵活:栈/队列复用。
  • 循环数组实现。

原理流程

  1. 两端插入删除。
  2. 按语义选择操作方法。
  3. 容量动态调整。

代码 / 示例

Deque<Integer> dq = new ArrayDeque<>();
dq.offerLast(1);
dq.offerFirst(0);
dq.pollFirst();
dq.pollLast();

常见误区

  • 误区:Deque 只能双端;正解:也可限制只用一端作栈。
  • 误区:Deque 允许 null;正解:ArrayDeque 不存 null。

追问

  • Q:Deque 与 Queue 关系? A:Deque 继承 Queue,扩展双端能力。
  • Q:单调队列用什么? A:Deque,队尾维护单调,队首删过期。

02.3.2.3-006 循环队列(LC 622)怎么设计?

一句话结论

固定长度数组 + 队头 head、队尾 tail(指向下一个可写位置)与当前 size;入队写 tail 后移取模,出队 head 后移取模;首尾指针环绕,避免头部搬迁。

概念解释

  • 数组环形复用。
  • 取模环绕。
  • size 记录元素数,简化判满判空。

原理流程

  1. 初始化容量、head/tail=0、size=0。
  2. 入队:写 tail,tail=(tail+1)%cap,size++。
  3. 出队:读 head,head=(head+1)%cap,size--。

代码 / 示例

class MyCircularQueue {
    private final int[] data;
    private int head = 0, tail = 0, size = 0;
    MyCircularQueue(int k) { data = new int[k]; }
    public boolean enQueue(int v) {
        if (isFull()) return false;
        data[tail] = v;
        tail = (tail + 1) % data.length;
        size++;
        return true;
    }
    public boolean deQueue() {
        if (isEmpty()) return false;
        head = (head + 1) % data.length;
        size--;
        return true;
    }
    public int front() { return isEmpty() ? -1 : data[head]; }
    public boolean isEmpty() { return size == 0; }
    public boolean isFull() { return size == data.length; }
}

常见误区

  • 误区:tail 指尾节点还是下一空位混淆;正解:口径统一,配合 size。
  • 误区:移动指针不取模;正解:环绕必须 % cap。

追问

  • Q:不用 size 怎么判满? A:空一格区分空满,(tail+1)%cap==head 为满。
  • Q:固定队列能扩容吗? A:循环队列常固定容量,扩容需搬移。

02.3.2.3-007 循环队列怎么判空与判满?

一句话结论

用 size 最直观:size==0 空、size==cap 满;不用 size 时保留一个空位:head==tail 为空,(tail+1)%cap==head 为满;两种口径不要混用。

概念解释

  • size 法:元素计数。
  • 空位法:牺牲一格。
  • 边界区分。

原理流程

  1. 选定口径。
  2. 入队前判满。
  3. 出队后判空。

代码 / 图示

size 法:空 0,满 cap
空位法:head==tail 空;tail 下一为 head 满

常见误区

  • 误区:head==tail 既可能空也可能满;正解:需 size 或空位区分。
  • 误区:满时仍入队覆盖;正解:先判满返回 false。

追问

  • Q:哪种实现推荐? A:面试 size 法清晰;空位法省一个计数变量。
  • Q:容量 1? A:size 法正常;空位法容量按 cap-1 使用。

02.3.2.3-008 循环队列入队出队指针怎么移动?

一句话结论

入队写 tail 位置后 tail=(tail+1)%cap;出队读 head 后 head=(head+1)%cap;取模保证环绕;读写位置由 head/tail 与 size 共同确定。

概念解释

  • 写入位:tail。
  • 读取位:head。
  • 环绕:取模。

原理流程

  1. 检查容量。
  2. 写入/读取对应位置。
  3. 指针后移取模。

代码 / 图示

tail → 空位;head → 队头
后移:(x+1) % cap

常见误区

  • 误区:先移指针再读写;正解:先读写当前位再移动。
  • 误区:tail 追上 head 覆盖;正解:判满保护。

追问

  • Q:head 与 tail 谁大? A:环绕后大小不定,靠取模与 size。
  • Q:遍历队列? A:从 head 按步长取模访问 size 次。

02.3.2.3-009 用队列实现栈(LC 225)怎么做?

一句话结论

单队列法:入队后把前面元素依次转到队尾,使新元素位于队头;出队直接 poll;或双队列辅助;每次 push 后旋转,pop O(1),push O(n)。

概念解释

  • 队列 FIFO,栈 LIFO。
  • 旋转把新元素翻到头。
  • 反转顺序靠多次出队入队。

原理流程

  1. 新元素入队尾。
  2. 前面 n-1 个依次出队再入队尾。
  3. 队头即最新元素。

代码 / 示例

class MyStack {
    private final Deque<Integer> q = new ArrayDeque<>();
    public void push(int x) {
        q.offer(x);
        for (int i = 0; i < q.size() - 1; i++) q.offer(q.poll());
    }
    public int pop() { return q.poll(); }
    public int top() { return q.peek(); }
    public boolean empty() { return q.isEmpty(); }
}

常见误区

  • 误区:旋转次数漏一个;正解:转 size-1 次保留新元素在头。
  • 误区:队列实现栈空间 O(1);正解:队列仍存全部元素 O(n)。

追问

  • Q:能否 pop O(1)、push O(n) 对调? A:也可在 pop 时旋转,按操作频率选型。
  • Q:两队列法? A:辅助队列转存,留最后元素。

02.3.2.3-010 BFS 为什么用队列?

一句话结论

BFS 按距离逐层扩展:先入队的节点先出队,保证同层节点先处理、下一层后处理;队列 FIFO 与层级顺序一致;O(n) 时间 O(n) 队列空间。

概念解释

  • 层级:距离起点步数。
  • FIFO:先发现先扩展。
  • 队列入队即标记防重。

原理流程

  1. 起点入队标记。
  2. 出队扩展邻接。
  3. 未访问邻接入队标记。

代码 / 示例

Queue<Node> q = new ArrayDeque<>();
q.offer(start);
visited.add(start);
while (!q.isEmpty()) {
    Node cur = q.poll();
    for (Node next : cur.neighbors()) {
        if (visited.add(next)) q.offer(next);
    }
}

常见误区

  • 误区:BFS 用栈;正解:栈是 DFS 顺序。
  • 误区:出队才标记;正解:入队即标记避免重复入队。

追问

  • Q:BFS 求最短路径? A:无权图首次到达即最短。
  • Q:队列空间最坏? A:层宽最大时 O(n)。

02.3.2.3-011 二叉树层序遍历怎么做?

一句话结论

根节点入队;每轮按当前队列长度分层,逐层出队并把子节点入队;队列保存同层待处理节点;O(n) 时间 O(n) 空间。

概念解释

  • 分层:记录每层节点数。
  • 子节点入队。
  • 层序广度优先。

原理流程

  1. 根入队。
  2. 循环:取当前 size 处理一层。
  3. 左右子节点入队。

代码 / 示例

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

常见误区

  • 误区:不记录 size 导致层交错;正解:每轮固定当前队列长度。
  • 误区:子节点入队前判空遗漏;正解:空节点不入队。

追问

  • Q:锯齿层序? A:按层奇偶反转顺序。
  • Q:最右视图? A:每层最后一个节点。

02.3.2.3-012 队列存值与存索引分别用于什么?

一句话结论

普通 BFS/层序存节点引用;窗口题与距离题存索引,便于判断过期位置与计算步数;与单调栈同理,按需要的量选择存储类型。

概念解释

  • 存引用:扩展节点。
  • 存索引:位置与过期判断。
  • 回查数组取值。

原理流程

  1. 判断答案是否依赖位置。
  2. 选节点或索引。
  3. 出队时按类型计算。

代码 / 图示

BFS:队列存节点
窗口最大:队列存下标

常见误区

  • 误区:窗口队列存值丢位置;正解:存索引判断过期。
  • 误区:BFS 存索引无法访问邻接;正解:图结构按索引回查。

追问

  • Q:索引队列怎么取值? A:arr[q.peek()]。
  • Q:可封装成对吗? A:可,索引附带值。

02.3.2.3-013 阻塞队列与并发队列是什么概念?

一句话结论

阻塞队列入队满时阻塞、出队空时阻塞,用于生产者消费者;并发队列内部保证多线程安全;基础手写队列非线程安全,生产场景用并发实现。

概念解释

  • 阻塞:条件不满足挂起等待。
  • 并发:内部加锁/无锁控制。
  • 与基础结构区分。

原理流程

  1. 多线程访问共享队列。
  2. 入队满等待空位。
  3. 出队空等待元素。

代码 / 图示

生产者 → 阻塞队列 → 消费者

常见误区

  • 误区:普通 ArrayDeque 可直接多线程用;正解:需同步保护。
  • 误区:阻塞队列是算法题结构;正解:并发工程概念,面试区分口径。

追问

  • Q:Java 常见并发队列? A:具体实现类以 JDK 版本为准,按阻塞/非阻塞分类。
  • Q:算法题需要线程安全吗? A:通常单线程口径,不考虑并发。

02.3.2.3-014 循环队列取模为什么不会越界?

一句话结论

指针移动恒为 (x+1) % cap,结果落在 [0, cap-1];写入前判满、读取前判空,下标始终合法;取模是环绕复用的关键。

概念解释

  • 模数:容量。
  • 区间:合法下标范围。
  • 边界保护。

原理流程

  1. 指针加一。
  2. 对 cap 取模。
  3. 容量检查防覆盖。

代码 / 图示

tail = (tail + 1) % cap

常见误区

  • 误区:指针可超过 cap 不回绕;正解:必须取模。
  • 误区:容量为 0 取模;正解:初始化保证 cap>0。

追问

  • Q:cap 不是 2 的幂取模慢吗? A:可接受,固定容量下常数。
  • Q:下标出界怎么排查? A:检查判满判空与取模位置。

02.3.2.3-015 队列实现栈时元素顺序怎么被反转?

一句话结论

队列把队头元素反复出队再入队尾,新元素经过 n-1 次旋转后位于队头;两次反转由多次 FIFO 搬运完成;栈顶对应队头。

概念解释

  • 搬运:出队再入队。
  • 新元素翻头。
  • 顺序逆置。

原理流程

  1. 新元素入队尾。
  2. 其余元素依次转尾。
  3. 队头为最新。

代码 / 图示

入队 1,2,3:队列 1 2 3
push 4 后旋转:4 1 2 3

常见误区

  • 误区:队列能直接逆序;正解:靠旋转搬运。
  • 误区:旋转后旧元素丢失;正解:出队再入队保留。

追问

  • Q:push 后栈顶是谁? A:刚压入元素。
  • Q:连续 push 复杂度? A:每次 O(n) 旋转。

02.3.2.3-016 队列题有哪些边界用例?

一句话结论

空队列出队、单元素、满队列入队、循环环绕后入出、两栈队列倒栈边界、队列实现栈的连续压弹;验证判空判满与指针环绕。

概念解释

  • 空与满。
  • 最短元素。
  • 环绕边界。

原理流程

  1. 空队列操作保护。
  2. 容量临界入队。
  3. 环绕多次入出。

代码 / 图示

poll 空
enQueue 满
环绕:head 追上 tail

常见误区

  • 误区:满队列入队返回 true;正解:应返回 false。
  • 误区:环绕后 size 计算错误;正解:入出队同步维护 size。

追问

  • Q:容量 1 入两次? A:第二次判满失败。
  • Q:两栈队列连续倒栈? A:out 非空不倒。

02.3.2.3-017 两栈实现队列的均摊 O(1) 怎么推?

一句话结论

每个元素从 in 转入 out 至多一次;倒栈批量发生,单次倒栈 O(k) 被 k 次出队分摊;均摊每次操作 O(1),总操作 O(n)。

概念解释

  • 转入次数:一次。
  • 批量倒栈。
  • 均摊分摊。

原理流程

  1. 元素入 in。
  2. out 空时一次性转入。
  3. 转入代价由后续出队分摊。

代码 / 图示

n 个元素:转入合计 n 次弹栈
摊到每次操作 O(1)

常见误区

  • 误区:两栈队列每次 O(n);正解:均摊 O(1)。
  • 误区:out 非空也倒栈;正解:重复倒栈破坏均摊。

追问

  • Q:最坏单次出队? A:out 空时倒栈 O(k)。
  • Q:peek 触发倒栈吗? A:空则同样倒栈。

02.3.2.3-018 队列空间复杂度怎么算?

一句话结论

队列空间为同时等待处理的元素数 × 单元素;BFS 最坏 O(n)(层宽最大);循环队列固定容量 O(cap);链表队列 O(n) 含节点指针开销。

概念解释

  • 同时在队:最大队列长度。
  • 节点开销:指针。
  • 固定容量。

原理流程

  1. 估算最大队长。
  2. 单元素常数。
  3. 结构额外开销单列。

代码 / 图示

BFS:O(层宽),最坏 O(n)
循环队列:O(cap)
链表:O(n) 含指针

常见误区

  • 误区:队列空间按总访问节点;正解:按同时在队。
  • 误区:循环队列空间 O(n) 动态;正解:固定 cap。

追问

  • Q:链状图 BFS 队长? A:每层 1,O(1) 队长。
  • Q:宽层图队长? A:O(n)。

02.3.2.3-019 优先队列和普通队列什么区别?

一句话结论

普通队列 FIFO 按入队顺序出队;优先队列按优先级(最值)出队,底层堆实现,取最值 O(log n);窗口 Top-K、任务调度使用;见 02.3.2.4。

概念解释

  • 优先级:键大小。
  • 堆:维护最值。
  • 出队:堆顶。

原理流程

  1. 插入元素调整堆。
  2. 取堆顶最值。
  3. 其余元素不出队顺序无关。

代码 / 图示

普通队列:先入先出
优先队列:最小值/最大值先出

常见误区

  • 误区:优先队列内部有序;正解:只保证堆顶最值,不全局有序。
  • 误区:优先队列 O(1) 出队;正解:堆调整 O(log n)。

追问

  • Q:优先队列底层? A:通常二叉堆。
  • Q:Top-K 用什么? A:大小 K 的堆。

02.3.2.3-020 队列类题复杂度怎么汇报?

一句话结论

普通队列入出队 O(1);两栈队列均摊 O(1),空间 O(n);队列实现栈 push O(n)/pop O(1)(或对调);BFS/层序 O(n)/O(n);循环队列 O(1) 操作,O(cap) 空间。

概念解释

  • 基础操作常数。
  • 双结构模拟有搬运代价。
  • BFS 按节点与层宽。

原理流程

  1. 标注入出队代价。
  2. 模拟结构搬运次数。
  3. 辅助空间按队长/容量。

代码 / 图示

基础队列:O(1) / O(n)
两栈队列:均摊 O(1) / O(n)
BFS:O(n) / O(n)
循环队列:O(1) / O(cap)

常见误区

  • 误区:两栈队列最坏 O(n) 报 O(n) 均摊;正解:说明均摊 O(1)、单次最坏 O(k)。
  • 误区:BFS 空间 O(1);正解:队列存层宽节点。

追问

  • Q:什么操作可 O(1) 空间? A:原地环形缓冲、固定两指针场景。
  • Q:面试先讲哪种实现? A:先数组循环队列,再讲链表与双栈模拟。