Editing Flood fill (section)

=== Moving the recursion into a data structure ===

{{multiple image
| align = right
| image1 = Wfm floodfill animation queue.gif
| width1 = 200
| alt1 = 
| caption1 = Four-way flood fill using a queue for storage
| image2 = Wfm floodfill animation stack.gif
| width2 = 200
| alt2 = 
| caption2 = Four-way flood fill using a stack for storage
| footer = 
}}

Moving the recursion into a data structure (either a [[Stack (abstract data type)|stack]] or a [[Queue (abstract data type)|queue]]) prevents a [[stack overflow]]. It is similar to the simple recursive solution, except that instead of making recursive calls, it pushes the nodes onto a [[Stack (abstract data type)|stack]] or [[Queue (abstract data type)|queue]] for consumption, with the choice of data structure affecting the proliferation pattern:

{{clear}}

 '''Flood-fill''' (node):
   1. Set ''Q'' to the empty queue or stack.
   2. Add ''node'' to the end of ''Q''.
   3. While ''Q'' is not empty:
   4.   Set ''n'' equal to the first element of ''Q''.
   5.   Remove first element from ''Q''.
   6.   If ''n'' is ''Inside'':
          ''Set'' the ''n''
          Add the node to the west of ''n'' to the end of ''Q''.
          Add the node to the east of ''n'' to the end of ''Q''.
          Add the node to the north of ''n'' to the end of ''Q''.
          Add the node to the south of ''n'' to the end of ''Q''.
   7. Continue looping until ''Q'' is exhausted.
   8. Return.