用Stack.push()和pop()实现DFS非递归版本的核心是手动模拟递归调用栈：栈存待访问节点，出栈时标记访问并处理，邻接节点逆序入栈以保证与递归顺序一致，需配合visited集合防重访。
用 Stack.push() 和 pop() 实现 DFS 的非递归版本，核心是**手动模拟递归调用栈的行为**：把待访问的节点按“后进先出”顺序压入栈，每次取出栈顶节点处理，并将其未访问的邻接节点依次压入——这样就能保证沿着一条路径尽可能深入，回溯时自然弹出上层节点。
明确栈中存什么
栈里一般存的是待探索的节点（如图的顶点编号、树的节点引用等）。有时需额外信息，比如：
- 只遍历：存节点本身即可（如
stack.push(node)） - 需要路径或深度：可存对象，如
{ node: n, depth: d } - 避免重复访问：配合 visited 数组/集合使用，入栈前检查，或出栈时检查
基本流程（以无向图邻接表为例）
假设图用 graph[node] 返回邻居列表，起点为 start：
- 初始化空栈，将
start压入 - 维护
visited集合，记录已访问节点 - 当栈非空：
– 弹出栈顶节点cur
– 若未访问，标记为已访问，处理它（如打印、收集）
– 遍历cur的所有邻居，对每个未访问邻居调用stack.push(neighbor)
注意：若希望与递归 DFS 的访问顺序完全一致（比如按邻接表索引升序深入），应**逆序压入邻居**（例如邻居是 [2,5,3]，就按 [3,5,2] 顺序 push），否则栈的 LIFO 特性会使最先 push 的最后处理。
树的前序遍历（非递归）示例
二叉树 DFS 前序（根→左→右）可直接用栈：
- 栈初始存根节点
- 循环中：
– pop 得到当前节点
– 访问该节点（如加入结果数组）
– 先 push 右子节点（若存在），再 push 左子节点（若存在）
（这样左子节点在栈顶，下一轮优先处理）
关键细节提醒
不要在入栈时标记 visited——因为节点可能被多次压入（尤其在图中多路径可达时），应在 出栈并准备处理时才标记和访问，避免遗漏；
避免无限循环：图中必须用 visited 控制，树则天然无环；
栈为空即搜索结束，无需额外终止条件。
