Non-recursive (iterative) DFS with $O(n)$ size stack

I usually deal with traversal algorithms such as DFS and BFS, and I have to implement them iteratively. However, in case of DFS, one challenge is that the size of stack can be $O(n+m)$ in worst case.

I was wondering if there is an iterative implementation of DFS that requires an $O(n)$ size stack instead of heavy $O(n+m)$ stack. I know that this is a worst case analysis, but I am concerned with this and want this to be really bounded.

Just as a reference, I am copying the algorithm from this solution, where vertices can be pushed into stack more than once and in the worst case, the stack size can be $O(n+m)$:

DFS(source):
  s <- new stack
  visited <- {} // empty set
  s.push(source)
  while (s is not empty):
    current <- s.pop()
    if (current is in visited):
        continue
    visited.add(current)
    // do something with current
    for each node v such that (current,v) is an edge:
        s.push(v)

You can keep only the topmost copy of a node on the stack:

dfs(source):
   s 
   s.push(source)
   on_stack.add(source,s.top())
   while s is not empty:
      current = s.pop()
      on_stack.remove(current)
      if visited.contains(current):
         continue
      # handle current
      visited.add(current)
      for v a neighbor of current:
         if on_stack.contains(v):
            stack_element <- on_stack.get(v)
            unlink stack_element from s
         stack.push(v)
         on_stack.add(v,s.top())

If your stack is a linked list, the asymptotic runtime stays the same. I doubt however that it will be much faster in practice unless your graphs are very dense, because the constants involved are much bigger.

StackExchange Computer Science Q#62283, answer score: 3