算法选择题：栈、队列与单调结构（5 题）
021 需要实现“撤销最近一次操作”与“按到达顺序处理任务”，应分别使用哪种结构？
难度： 基础
- A. 最近未完成状态适合栈（LIFO），按到达顺序或分层处理适合队列（FIFO）；数据结构顺序必须与问题要求一致
- B. 栈适合按到达顺序处理，队列适合最近撤销
- C. 栈和队列只是方法名不同，行为完全一样
- D. 两种场景都应该用 List 随机访问，效率最高
查看答案与解析
正确答案A
正确原因： 最近未完成状态适合栈，按到达顺序或分层处理适合队列；数据结构顺序必须与问题要求一致。
错误选项辨析： B 项：把两种结构的语义用反了；C 项：栈后进先出、队列先进先出，访问顺序完全不同；D 项：随机访问与题目要求的顺序语义不匹配，且不一定高效。
022 需要频繁从队首移除元素，用 .NET 集合实现，哪种做法最合理？
难度： 进阶
- A. 频繁出队的场景用数组从头弹出即可，无需搬移
- B. Queue<T> 与 List<T> 的出队成本完全相同
- C. List<T>.RemoveAt(0) 需要搬移后续元素，单次 O(n)；需要高效出队应使用 Queue<T> 或环形缓冲区
- D. List<T>.RemoveAt(0) 是 O(1)，可以直接模拟队列
查看答案与解析
正确答案C
正确原因： List<T> 删除下标零通常需要搬移后续元素；需要高效出队应使用 Queue<T> 或环形缓冲区。
错误选项辨析： A 项：固定数组从头部弹出仍需移动元素，除非使用环形索引；B 项：Queue 使用环形缓冲，出队通常 O(1)，与 List 的搬移不同；D 项：删除下标零会触发后续元素整体前移，成本为 O(n)。
023 用栈计算逆波兰表达式（后缀表达式），弹出两个操作数时应如何确定顺序？
难度： 进阶
- A. 逆波兰表达式不需要栈，直接从左到右计算即可
- B. 先弹出的是左操作数，后弹出的是右操作数
- C. 弹栈顺序不影响任何二元运算结果
- D. 先弹出的是右操作数，后弹出的是左操作数；减法、除法等不可交换运算必须保持此顺序
查看答案与解析
正确答案D
正确原因： 先弹出的是右操作数，后弹出的是左操作数；减法和除法不可交换两者。
错误选项辨析： A 项：遇到运算符时需要取回最近的两个操作数，正是栈的用途；B 项：栈顶是最后压入的元素，先弹出的是右操作数；C 项：减法与除法的操作数顺序决定结果，交换会出错。
024 单调栈代码中 while 循环内会不断弹栈，为什么总复杂度仍是 O(n)？
难度： 进阶
- A. 单调栈的复杂度与元素个数无关，恒为 O(1)
- B. 每个元素最多入栈一次、出栈一次，弹栈总次数为 O(n)；循环内出现 while 不代表一定是 O(n²)
- C. 每个元素可能被弹出多次，因此最坏是 O(n²)
- D. 循环内出现 while 就一定是 O(n²)
查看答案与解析
正确答案B
正确原因： 每个元素最多入栈一次并出栈一次；while 弹栈不会让总复杂度变为 O(n²)。
错误选项辨析： A 项：至少需要遍历所有元素，复杂度与 n 相关；C 项：元素出栈后就离开栈，最多出栈一次；D 项：复杂度取决于 while 的总执行次数，元素各出栈一次时总量仍是 O(n)。
025 实现 O(1) 取最小值的 MinStack 时，辅助栈应如何处理重复的最小值？
难度： 综合
- A. 辅助栈只需保存所有不同的最小值
- B. 弹出时重新扫描主栈求最小值，同样能保证单次 O(1)
- C. 辅助栈必须为每次压入保留对应的最小值；重复最小值弹出一次后，另一个仍可能是当前最小值
- D. 最小栈只能处理不含重复值的输入
查看答案与解析
正确答案C
正确原因： 辅助状态必须保留每次压入时对应的最小值；重复最小值弹出一次后仍可能是当前最小值。
错误选项辨析： A 项：去重后弹出一次重复最小值，后续取最小就会缺少正确候选；B 项：重新扫描是 O(n)，违背 O(1) 要求；D 项：正确的实现正是要覆盖重复最小值，否则是缺陷而非限制。