02.3.2.3 队列、双端队列与循环队列
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.3 链表、栈与队列 / 02.3.2 栈与队列、单调栈
02.3.2.3-001 队列是什么结构?
一句话结论
队列是先进先出(FIFO)线性结构:队尾入队、队头出队;支持 offer/peek/poll/isEmpty;适配顺序处理与 BFS 场景。
概念解释
- FIFO:先到先服务。
- 队头:出队端。
- 队尾:入队端。
原理流程
- 元素队尾入队。
- 队头出队。
- 空队列不可取。
代码 / 图示
队头 → 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:队尾引用。
- 空队列两者为空。
原理流程
- 入队:空则头尾同指新节点,否则 tail.next 后移。
- 出队:head 后移。
- 出空后 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:出队专用。
- 批量倒栈反转顺序。
原理流程
- push:in.push。
- pop/peek:out 空则倒空 in,再 out.pop。
- 非空直接 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、撤销);按“先到先处理”还是“最近先处理”选择。
概念解释
- 队列:顺序展开。
- 栈:逆序回溯。
- 场景映射。
原理流程
- 判断处理顺序。
- 广度用队列,深度用栈。
- 嵌套配对用栈。
代码 / 图示
BFS:队列逐层
DFS:栈回溯
括号:栈配对
常见误区
- 误区:BFS 用栈;正解:广度优先必须队列。
- 误区:层序遍历用栈;正解:同层顺序由队列保证。
追问
- Q:递归 DFS 底层结构? A:调用栈。
- Q:消息排队用什么? A:队列。
02.3.2.3-005 双端队列(Deque)是什么?
一句话结论
双端队列两端都可入队出队;可同时当栈、普通队列使用;Java Deque 接口,ArrayDeque 为数组实现;栈语义 push/pop 走同一端,队列语义 offer/poll 走两端。
概念解释
- 两端:队头队尾均可操作。
- 灵活:栈/队列复用。
- 循环数组实现。
原理流程
- 两端插入删除。
- 按语义选择操作方法。
- 容量动态调整。
代码 / 示例
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 记录元素数,简化判满判空。
原理流程
- 初始化容量、head/tail=0、size=0。
- 入队:写 tail,tail=(tail+1)%cap,size++。
- 出队:读 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 法:元素计数。
- 空位法:牺牲一格。
- 边界区分。
原理流程
- 选定口径。
- 入队前判满。
- 出队后判空。
代码 / 图示
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。
- 环绕:取模。
原理流程
- 检查容量。
- 写入/读取对应位置。
- 指针后移取模。
代码 / 图示
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。
- 旋转把新元素翻到头。
- 反转顺序靠多次出队入队。
原理流程
- 新元素入队尾。
- 前面 n-1 个依次出队再入队尾。
- 队头即最新元素。
代码 / 示例
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:先发现先扩展。
- 队列入队即标记防重。
原理流程
- 起点入队标记。
- 出队扩展邻接。
- 未访问邻接入队标记。
代码 / 示例
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) 空间。
概念解释
- 分层:记录每层节点数。
- 子节点入队。
- 层序广度优先。
原理流程
- 根入队。
- 循环:取当前 size 处理一层。
- 左右子节点入队。
代码 / 示例
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/层序存节点引用;窗口题与距离题存索引,便于判断过期位置与计算步数;与单调栈同理,按需要的量选择存储类型。
概念解释
- 存引用:扩展节点。
- 存索引:位置与过期判断。
- 回查数组取值。
原理流程
- 判断答案是否依赖位置。
- 选节点或索引。
- 出队时按类型计算。
代码 / 图示
BFS:队列存节点
窗口最大:队列存下标
常见误区
- 误区:窗口队列存值丢位置;正解:存索引判断过期。
- 误区:BFS 存索引无法访问邻接;正解:图结构按索引回查。
追问
- Q:索引队列怎么取值? A:arr[q.peek()]。
- Q:可封装成对吗? A:可,索引附带值。
02.3.2.3-013 阻塞队列与并发队列是什么概念?
一句话结论
阻塞队列入队满时阻塞、出队空时阻塞,用于生产者消费者;并发队列内部保证多线程安全;基础手写队列非线程安全,生产场景用并发实现。
概念解释
- 阻塞:条件不满足挂起等待。
- 并发:内部加锁/无锁控制。
- 与基础结构区分。
原理流程
- 多线程访问共享队列。
- 入队满等待空位。
- 出队空等待元素。
代码 / 图示
生产者 → 阻塞队列 → 消费者
常见误区
- 误区:普通 ArrayDeque 可直接多线程用;正解:需同步保护。
- 误区:阻塞队列是算法题结构;正解:并发工程概念,面试区分口径。
追问
- Q:Java 常见并发队列? A:具体实现类以 JDK 版本为准,按阻塞/非阻塞分类。
- Q:算法题需要线程安全吗? A:通常单线程口径,不考虑并发。
02.3.2.3-014 循环队列取模为什么不会越界?
一句话结论
指针移动恒为 (x+1) % cap,结果落在 [0, cap-1];写入前判满、读取前判空,下标始终合法;取模是环绕复用的关键。
概念解释
- 模数:容量。
- 区间:合法下标范围。
- 边界保护。
原理流程
- 指针加一。
- 对 cap 取模。
- 容量检查防覆盖。
代码 / 图示
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
push 4 后旋转:4 1 2 3
常见误区
- 误区:队列能直接逆序;正解:靠旋转搬运。
- 误区:旋转后旧元素丢失;正解:出队再入队保留。
追问
- Q:push 后栈顶是谁? A:刚压入元素。
- Q:连续 push 复杂度? A:每次 O(n) 旋转。
02.3.2.3-016 队列题有哪些边界用例?
一句话结论
空队列出队、单元素、满队列入队、循环环绕后入出、两栈队列倒栈边界、队列实现栈的连续压弹;验证判空判满与指针环绕。
概念解释
- 空与满。
- 最短元素。
- 环绕边界。
原理流程
- 空队列操作保护。
- 容量临界入队。
- 环绕多次入出。
代码 / 图示
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)。
概念解释
- 转入次数:一次。
- 批量倒栈。
- 均摊分摊。
原理流程
- 元素入 in。
- out 空时一次性转入。
- 转入代价由后续出队分摊。
代码 / 图示
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) 含节点指针开销。
概念解释
- 同时在队:最大队列长度。
- 节点开销:指针。
- 固定容量。
原理流程
- 估算最大队长。
- 单元素常数。
- 结构额外开销单列。
代码 / 图示
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。
概念解释
- 优先级:键大小。
- 堆:维护最值。
- 出队:堆顶。
原理流程
- 插入元素调整堆。
- 取堆顶最值。
- 其余元素不出队顺序无关。
代码 / 图示
普通队列:先入先出
优先队列:最小值/最大值先出
常见误区
- 误区:优先队列内部有序;正解:只保证堆顶最值,不全局有序。
- 误区:优先队列 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 按节点与层宽。
原理流程
- 标注入出队代价。
- 模拟结构搬运次数。
- 辅助空间按队长/容量。
代码 / 图示
基础队列: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:先数组循环队列,再讲链表与双栈模拟。