栈和队列通过限制访问顺序建立清晰不变量；单调结构进一步移除不可能成为答案的候选。

🧭 什么时候考虑这个专题

嵌套匹配和最近候选使用栈；公平顺序和分层使用队列；最近更大或更小元素考虑单调栈。

开始编码前先明确输入、输出、数据规模和允许修改的数据，再用一句话写出循环、窗口、堆或递归函数保持的不变量。

核心结构与复杂度

知识点核心规则常见复杂度
LIFO 与 FIFO 选型最近未完成状态适合栈，按到达顺序或分层处理适合队列入栈出栈或入队出队通常 O(1)
List 头部删除List<T> 删除下标零通常需要搬移后续元素头部删除 O(n)
逆波兰操作数顺序先弹出的是右操作数，后弹出的是左操作数求值 O(n)
单调栈摊还成本每个元素最多入栈一次并出栈一次总时间 O(n)
最小栈重复值辅助状态必须保留每次压入时对应的最小值各操作 O(1)

复杂度必须对应真实代码路径。哈希结构要区分平均与最坏情况，递归要计算调用栈，返回结果是否计入空间也应按题目口径说明。

适用边界

  • LIFO 与 FIFO 选型： 数据结构顺序必须与问题要求一致
  • List 头部删除： 需要高效出队应使用 Queue<T> 或环形缓冲区
  • 逆波兰操作数顺序： 减法和除法不可交换两者
  • 单调栈摊还成本： while 弹栈不会让总复杂度变为 O(n²)
  • 最小栈重复值： 重复最小值弹出一次后仍可能是当前最小值

C# 实现检查

  1. 方法签名与题目契约一致，不依赖控制台输入输出。
  2. 数值计算检查 int 溢出，必要时先提升为 long。
  3. 集合选择说明平均复杂度、顺序语义和重复值处理。
  4. 字符串题明确使用 char、Rune、序号比较还是文化比较。
  5. 递归题说明终止条件、最大深度和退化输入。

⚠️ 常见误区

  • LIFO 与 FIFO 选型： 不要把“栈和队列只是在方法名称上不同”当成规则。
  • List 头部删除： 不要把“任何 List 都能以 O(1) 模拟队列”当成规则。
  • 逆波兰操作数顺序： 不要把“弹栈顺序不会影响二元运算结果”当成规则。
  • 单调栈摊还成本： 不要把“循环内出现 while 就一定是平方复杂度”当成规则。
  • 最小栈重复值： 不要把“辅助栈只需保存不同的最小值”当成规则。

练习顺序

先完成本组 5 道选择题，口述每个选项的边界；再独立实现编程题，最后对照参考答案检查不变量、复杂度和面试追问。