用栈和队列揭示边界

# 揭示栈与队列的前沿 来源：https://dystroy.org/blog/stack-and-queues/ 能够用栈和队列思考是一种被忽视的超能力。当涉及树和其他图结构时，这往往比递归更有利于看清问题本质。计算机科学课程喜欢教递归，因为它看起来简单又优雅——尤其在函数式编程成为课程内容时，更尤其是在黑板上画图演示时。你可能已经读过很多次，也可能亲身经历过：递归并不总是高效的，尤其在现代计算机上。但更有趣的一点是，它往往也是一种糟糕的心智模型，会让编程变得更复杂、更不易适应。而更有趣的是，递归有时确实大放异彩，这也是它至今未被淘汰的原因。但即便如此，这篇文章的真正重点也不在于此。 ## 树的遍历 我们先从文件树的遍历开始探索。在现实世界中，你永远不可能一次性列出目录中所有深层文件：你必须处理用户中断、超时以及各种限制。我们简化为仅设置一个最大项目数来模拟这种复杂度。 ### 深度优先遍历（自然顺序） 在 Rust 中，递归代码可能是这样： ```rust fn add_first_paths_recursive( dir: &Path, list: &mut Vec<PathBuf>, max: usize, ) -> Result<(), io::Error> { if list.len() >= max { return Ok(()); } list.push(dir.to_path_buf()); if dir.is_dir() { for entry in fs::read_dir(dir)? { let path = entry?.path(); add_first_paths_recursive(&path, list, max)?; if list.len() >= max { break; } } } Ok(()) } ``` 它的作用是以标准树表示的方式列出文件，即深度优先搜索（DFS），且文件顺序与系统返回的顺序一致。这段代码很直观，你知道不会有意外，顺序正如预期。当然存在栈分配的隐性开销，但这很小。提前退出的行为则稍显麻烦，无论是代码上（很难避免重复）还是执行上（调用栈展开时每一层都必须执行同样的检查）。 现在，让我们看看基于栈的、以同样顺序进行相同遍历的函数。它并没有想象中那么美观： ```rust fn add_first_paths_with_stack_dfs( dir: &Path, list: &mut Vec<PathBuf>, max: usize, ) -> Result<(), io::Error> { let mut todo = vec![dir.to_path_buf()]; while let Some(current) = todo.pop() { if list.len() >= max { break; } if current.is_dir() { let mut children = Vec::new(); for entry in fs::read_dir(¤t)? { let path = entry?.path(); children.push(path); } list.push(current); for path in children.into_iter().rev() { todo.push(path); } } else { list.push(current); } } Ok(()) } ``` 当我们向待办列表添加路径并出栈时，我们必须反向迭代（因此有了 `children.into_iter().rev()`）。这使得代码更难理解（甚至第一次很难写对）。提前退出的处理要好得多，但说实话，这段代码远没有那么直观。**这里递归大放异彩**。在处理现实应用中的约束（如中断）时，递归可能效率稍低，但在这个场景下，递归代码与我们的意图完美契合。 ### 当不需要特定顺序时 如果我们并不需要实时打印出树形结构，递归就不是最简单的方案了。下面这个方案非常简洁，使用一个栈作为待访问目录的待办列表： ```rust fn add_first_paths_with_stack( dir: &Path, list: &mut Vec<PathBuf>, max: usize, ) -> Result<(), io::Error> { let mut todo = vec![dir.to_path_buf()]; while let Some(current) = todo.pop() { if list.len() >= max { break; } if current.is_dir() { for entry in fs::read_dir(¤t)? { let path = entry?.path(); todo.push(path); } } list.push(current); } Ok(()) } ``` 这个版本没有任何别扭之处。而且由于我们将“前沿”具体化了，改变控制流、处理中断、暂停迭代、交错任务（比如同时遍历另一棵树）都非常容易。 ### 广度优先搜索 如果你想先完全探索当前层，再深入下一层呢？只需做个简单改动：把 LIFO 栈换成 FIFO 队列（在 Rust 中使用 `VecDeque` (https://doc.rust-lang.org/beta/std/collections/struct.VecDeque.html)）： ```rust fn add_first_paths_with_queue( dir: &Path, list: &mut Vec<PathBuf>, max: usize, ) -> Result<(), io::Error> { let mut todo = VecDeque::from([dir.to_path_buf()]); while let Some(current) = todo.pop_front() { if list.len() >= max { break; } if current.is_dir() { for entry in fs::read_dir(¤t)? { let path = entry?.path(); todo.push_back(path); } } list.push(current); } Ok(()) } ``` 控制流依然容易处理，逻辑也可以调优。例如，[broot](https://dystroy.org/broot) 正是基于此实现了高效搜索和并行下降，同时不会锁定 UI。 ## 图的探索 当图的连通性比树更强时，纯递归遍历变得不可能。但栈/队列的方法依然简单。例如，下面的代码返回所有从某个节点可达的节点： ```rust fn reachable_from(root: Node) -> HashSet<Node> { let mut visited = HashSet::new(); let mut todo = VecDeque::new(); visited.insert(root); todo.push_back(root); while let Some(current) = todo.pop_front() { for neighbour in neighbours_of(current) { if visited.insert(neighbour) { // 如果已存在则返回 false todo.push_back(neighbour); } } } visited } ``` 这非常容易调优： - 把 `VecDeque` 换成 `Vec` 作为 `todo`，你就会先探索远处的节点（等价于 DFS）。 - 不返回所有已访问节点，而是返回第一个满足某个约束的节点，从而检查能否到达某个集合。 只需做一点额外修改，你就得到了路径搜索：为每个节点存储它来自哪个节点。 ```rust fn find_path(from: Node, to: Node) -> Option<Vec<Node>> { let mut todo = VecDeque::from([from]); // 同时充当“已访问”集合和历史追踪器 let mut came_from: HashMap<Node, Node> = HashMap::new(); while let Some(current) = todo.pop_front() { if current == to { // 最后重建路径 let mut path = vec![current]; while let Some(&parent) = came_from.get(path.last().unwrap()) { path.push(parent); } path.reverse(); return Some(path); } for neighbour in neighbours_of(current) { if neighbour != from && !came_from.contains_key(&neighbour) { came_from.insert(neighbour, current); todo.push_back(neighbour); } } } None } ``` 把队列换成二叉堆，优先搜索估计离目标最近的节点，你就得到了 [A* 算法](https://en.wikipedia.org/wiki/A*_search_algorithm)。注意到这仍然是一个线性操作，你能添加测试、暂停，甚至存储搜索状态吗？ ## 核心思路 这种思路的核心不仅仅是栈、队列和二叉堆，而是将“前沿”具体化——把时序执行转化为数据，使其变得可管理、可暂停、更易于推理。一旦习惯了这种思考方式，整个世界的问题都会变得容易解决，不是通过照搬书本上的计算机科学算法，而是自然而然地，同时满足现实世界问题的所有约束。 我在这里只提到了图，但你在递归下降解析器、正则表达式引擎（可以重新设计为显式自动机）或游戏行为树中也会遇到完全相同的架构性挑战。每当你把执行流转化为数据时，你的系统就变得本质上可控、可测试、可操作。