3.3 应用选择题：识别“最近未完成”还是“最早待处理”

应用题先判断状态管理规律。括号、函数返回、表达式运算符需要最近未完成者先处理，用栈；任务调度、BFS、层序遍历需要最早发现者先处理，用队列。

多选：必须借助栈思想的有 A 括号嵌套匹配；B 无权图最短路；C 后缀表达式求值；D 递归调用返回。答案 A、C、D；B 使用队列。

后缀题 6 2 / 3 -：先算 6/2=3，再算 3-3=0。弹栈时第一个是右操作数。若候选答案出现符号相反，优先检查左右次序。

括号题 ([{}]) 合法，([)] 非法。数量相同只说明必要条件满足，类型与嵌套顺序仍需栈顶验证。递归空间题要看最大同时活跃的调用层数，而不是总调用次数；二叉递归可能总调用很多但深度较小。

BFS 题中，若在出队时才设访问标记，结点可能重复入队，复杂度和父结点记录都受影响。正确做法通常是发现并入队时标记。

复杂度辨析也要分开“总处理次数”和“同时保存状态数”。后缀求值每个记号至多进出栈一次，时间 $O(n)$；BFS 中每个顶点入队一次、每条边被检查有限次，邻接表下时间 $O(V+E)$。递归则还要从调用树判断总时间，从最长根到叶路径判断栈空间，二者不必相同。

错解反馈：把所有“遍历”一概归入队列；把表达式字符从左到右直接计算；用总调用次数当递归栈深度；括号只数数量，都是未识别状态依赖关系。

迁移题（多选）：A 浏览器后退 B 打印排队 C 树的层序遍历 D 撤销最近编辑。使用栈的是 A、D，使用队列的是 B、C。验收要求不是只报答案，还要写“谁应最先被处理”。