目标

辨析队列的先进先出语义、front 与 dequeue 的行为差异，推导循环队列的下标与长度，并检查链队列边界、复杂度和工程选型中的常见误区。

前置知识

建议先阅读第 2.2 节队列，并确认采用正文的统一约定：front 指向队头元素，rear 指向下一次入队写入位置，循环队列使用空一格方案。题目中的物理槽位数均以 m 表示。

正文循环队列部分已有 3 道随堂复习题，分别检查有效容量、判满条件和满队列入队失败后的状态。本 Lab 不重复这些题目，而是进一步检查操作序列、公式应用、链式边界与实现取舍。

环境、输入与预期输出

• 环境：任意现代浏览器；建议准备纸笔画出队头、队尾和逻辑顺序。
• 输入：本页按源文件顺序加载的 10 道单项选择题。
• 预期输出：一份独立作答记录，以及每道错题的错误原因和正确推导。

作答方法

1. 先写出当前逻辑队列，不要只观察数组中的物理位置；
2. 涉及循环下标时，明确 m、front、rear 的含义后再代入公式；
3. 选择答案并提交，再核对反馈、提示和题解；
4. 做错后点击“重新作答”，在不看解析的情况下重新推导。

选择题

答题进度已答 0/10正确 0

第 1 题

难度★考点队列、FIFO、操作序列标识queue-drill-001

初始队列为空，依次执行 enqueue(A)、enqueue(B)、enqueue(C)、dequeue()、enqueue(D)。此时调用 front() 应得到哪个元素？

查看提示

先逐步写出每次操作后的逻辑队列，不要按最近一次入队判断。

请选择一个答案

AA

BB

CC

DD

第 2 题

难度★考点Queue ADT、front、后置条件标识queue-drill-002

队列依次入队 10、20 后，成功调用一次 front(out)。按照 Queue ADT 契约，下列哪项描述正确？

查看提示

区分“查看队头”和“移除队头”两种操作。

请选择一个答案

Aout == 20，队列长度仍为 2

Bout == 10，队列长度变为 1

Cout == 10，队列长度仍为 2

Dout == 20，队列长度变为 1

第 3 题

难度★考点顺序队列、假溢出、循环复用标识queue-drill-003

普通顺序队列的 rear 只向数组右侧推进。若多次出队后数组前部已有空位，但 rear 已到达数组末端，继续入队仍被拒绝。这种现象的根本原因是什么？

查看提示

判断是“空间真的不足”，还是“当前下标规则到不了空位置”。

请选择一个答案

A队列的 FIFO 语义禁止复用旧位置

B数组前部的空位已被操作系统回收

C每次出队都会自动缩小数组容量

D线性推进的下标无法回到数组开头复用空位

第 4 题

难度★考点循环队列、取模、rear标识queue-drill-004

循环队列物理槽位数 m = 6，rear = 5 且本次入队可以成功。元素写入 data[rear] 后执行 rear = (rear + 1) % m，新的 rear 是多少？

查看提示

直接计算 (5 + 1) % 6，并注意合法下标范围是 0～5。

请选择一个答案

A0

B4

C5

D6

第 5 题

难度★★考点循环队列、长度公式、环绕标识queue-drill-005

采用正文统一约定的循环队列中，物理槽位数 m = 7，当前 front = 5、rear = 2。队列的逻辑元素个数是多少？

查看提示

当 front > rear 时，逻辑区间会跨过数组末端。

请选择一个答案

A2

B3

C4

D6

第 6 题

难度★★考点动态扩容、摊还复杂度、固定容量标识queue-drill-006

一个动态循环队列在空间不足时按固定倍数扩容，并按逻辑顺序搬移现有 n 个元素。下列复杂度描述哪项正确？

查看提示

分别判断“发生扩容的那一次”和“一长串操作的平均成本”。

请选择一个答案

A每次入队的最坏时间都是 O(1)

B单次扩容是 O(n)，一长串入队可达到摊还 O(1)

C单次扩容是 O(log n)，入队摊还为 O(n)

D动态队列与固定容量队列在满时都必须立即返回失败

第 7 题

难度★★考点链队列、单元素边界、首尾指针标识queue-drill-007

无哨兵节点的链队列当前只有一个元素，且 head、tail 都指向该节点。成功出队并释放该节点后，正确状态应是什么？

查看提示

检查 size == 0、head == nullptr、tail == nullptr 是否仍然等价。

请选择一个答案

Ahead == nullptr，tail 仍指向已释放节点，size == 0

Bhead 仍指向已释放节点，tail == nullptr，size == 0

Chead == tail，但二者必须指向一个新建的空节点

Dhead == tail == nullptr，size == 0

第 8 题

难度★★考点循环队列、链队列、复杂度、工程取舍标识queue-drill-008

比较固定容量循环队列与维护尾指针的链队列，下列哪项说法最准确？

查看提示

复杂度相同不代表容量模型、内存局部性和失败契约相同。

请选择一个答案

A两者主要操作通常都是 O(1)，但容量、内存布局和失败方式不同

B循环队列的出队是 O(n)，链队列的出队是 O(1)

C链队列不需要内存分配，因此入队永远不会失败

D两者的存储空间都必须在构造时一次性确定

第 9 题

难度★★考点工程选型、环形缓冲区、可预测延迟标识queue-drill-009

某设备的数据缓冲区容量固定，初始化后禁止再次分配内存，要求入队和出队具有可预测的最坏延迟，并规定缓冲区满时拒绝新数据。最合适的核心结构是哪个？

查看提示

优先匹配“不再分配”“固定容量”“最坏延迟可预测”三个条件。

请选择一个答案

A自动扩容的 std::queue

B每次入队都分配节点的链队列

C固定容量环形缓冲区

D按数值大小出队的优先队列

第 10 题

难度★★★考点双栈队列、摊还分析、结构组合标识queue-drill-010

用输入栈 in 和输出栈 out 实现队列：入队压入 in；出队时若 out 为空，就把 in 中所有元素转移到 out。下列复杂度结论哪项正确？

查看提示

追踪单个元素一生中进入和离开两个栈的总次数。

请选择一个答案

A每次出队最坏和摊还都只能是 O(n)

B某次出队可能是 O(n)，但一串操作中每次操作可摊还为 O(1)

C入队必须是 O(n)，因为需要立即保持两个栈大小相等

D每个元素会在 in 与 out 之间来回移动 O(n) 次

答案总览（建议完成全部题目后查看）

1. 第 1 题：B
2. 第 2 题：C
3. 第 3 题：D
4. 第 4 题：A
5. 第 5 题：C
6. 第 6 题：B
7. 第 7 题：D
8. 第 8 题：A
9. 第 9 题：C
10. 第 10 题：B

完成清单

• 10 道题均在提交答案前独立作答；
• 能从操作序列写出最终队头、长度和出队顺序；
• 能解释循环下标和长度公式，而不是只背诵结果；
• 能说清链队列第一次入队、最后一次出队需要维护的状态；
• 能根据容量、分配和延迟约束选择合适的队列实现。

思考题

1. 为什么逻辑队列顺序不能直接由数组下标从小到大判断？
2. 动态扩容队列的“摊还 O(1)”为什么不等于每次入队最坏 O(1)？
3. 链队列若只维护 head 而不维护 tail，哪项基本操作可能退化为 O(n)？
4. 双栈队列中，一个元素为什么不会在两个栈之间反复来回移动？

复盘

• 我最容易混淆的是 FIFO 语义、循环下标，还是物理容量与逻辑长度？
• 代入公式前，我是否先确认了 front 和 rear 的具体约定？
• 面对实现选型题时，我是否先看容量、分配和延迟约束，而不是只看容器名称？