图DFS遍历：顶点能否共存于未访问栈与已访问队列？判断语句是否必要？

先把你提供的英文算法代码翻译成中文伪代码：

算法 DFS(起始顶点)
{
    将起始顶点加入 notVisited 栈;
    初始化 Visited 队列为空（原代码写的place NULL，实际应为初始空队列）;
    当 notVisited 栈不为空时
    {
        从 notVisited 栈中弹出一个顶点;
        生成该顶点的所有后继节点;

        遍历每个后继节点
        {
            若（后继节点不在 Visited 队列中 且 后继节点不在 notVisited 栈中）
            则 将后继节点加入 notVisited 栈的顶部; // 原代码笔误写为add vertex，应为add successor
        }

        若（当前顶点不在 Visited 队列中）
        则 将当前顶点加入 Visited 队列;
    }
}

针对你的两个疑问，解答如下：

1. 顶点能否同时存在于notVisited栈和Visited队列中？ #

正常执行流程下，不可能。原因很直接：

• 一个顶点要被加入notVisited栈，必须满足「不在Visited队列」且「不在notVisited栈」的双重条件，从源头杜绝了已访问顶点进栈的可能；
• 顶点被加入Visited队列的时机是从栈中弹出之后，此时它已经脱离了栈，自然不可能同时出现在两个结构里。

简单来说，顶点的状态只会是「未被处理」「待处理（在栈中）」「已处理（在Visited中）」三者之一，不会出现状态重叠。

2. if(当前顶点不在 Visited 队列中) 则 将当前顶点加入 Visited 队列这句是否必要？ #

非常必要，它是防止重复记录的关键保险：

• 虽然正常逻辑下每个顶点只会被压入栈一次，弹出时必然不在Visited中，但如果代码出现疏漏（比如后继节点的判断漏了「不在栈中」的检查），同一个顶点可能被多次压入栈。此时这个判断能保证该顶点仅在第一次弹出时被加入Visited，后续弹出时直接跳过，避免Visited队列出现重复条目。
• 若后续对算法逻辑进行修改（比如调整入栈规则），这句能作为兜底防线，确保Visited队列始终每个顶点只记录一次。

内容的提问来源于stack exchange，提问作者Midhun Raj