tree - How to create an iterator wrapper for DAG structure in Java? -

i want have iterator on data structure. don't know data structure is, mayebe dag (directed acyclic graph), maybe linked list. want wrap iterator , don't think @ particular data structure.

i know how visit dag recursive-like visitor, can't figure out simple , clean structure implementing iterator methods next() , hasnext().

inside iterator i've created current node instance , iterate for-loop on children , parent. 'already-visited' flag needed. dagelement has these more attributes:

dagelement parent boolean alreadyvisited 

i don't think clean solution.

any advice?

the quick-and-dirty method converting recursive heuristic iterative 1 use (lifo) stack or (lilo) queue hold "roads not taken" - paths found not yet taken. in case, iterator have stack or queue instance variable. like:

    class dagiterator<t>     extends iterator<t> {          private stack<dagnode<t>> nodes;          private dagiterator(dag<t> dag) {             nodes.push(dag.getrootnode());         }          public boolean hasnext() {             return ! nodes.isempty();               }          public t next() {             final dagnode node = nodes.pop();             (final dagnode child : node.getchildren()) {                 nodes.push(child);             }             return node.getvalue();         }      } 

you tweak visitation order based on data structure (lifo or lilo), order in children queued, , when queued. wouldn't suprise me visitation orders may require queuing entire set of nodes in proper order right off bat (in constructor).