我们使用 LIFO 队列，即堆栈，来实现深度优先搜索算法，因为深度优先搜索总是扩展搜索树当前边界中最深的节点。

Norvig 和 Russell 在第 3.4.3 节中写道

搜索立即进行到搜索树的最深层，其中节点没有后继。随着这些节点的扩展，它们从边界被删除，因此搜索“备份”到下一个最深的节点，该节点仍有未探索的后继节点。

LIFO 队列意味着选择最近生成的节点进行扩展。这必须是最深的未扩展节点，因为它比其父节点深一个 - 反过来，当它被选中时，它是最深的未扩展节点。