A stack is a last-in, first-out structure: newly discovered elements are pushed onto the top, and the next element to process is popped from the top. This ordering drives depth-first search toward the deepest available node before backtracking. section 3.3.2
In depth-first search, the stack supports a simple processing cycle:
- Initialize it with the source node. section 3.3.2
- Pop the most recently discovered node and expand it. section 3.3.2
- Push eligible successors onto the stack, continuing until the destination is found or the stack is empty. section 3.3.2
Algorithm 3.2 Depth-first search (DFS)
Inputs: Source node, Destination node Output: Route from source to destination Initialize Stack ← a LIFO initialized with sourcenode Initialize Explored ← empty Initialize Found ← False While stack is not empty and found is False do Set node ← stack.pop() Add node to explored For child in node.expand() do If child is not in explored and child is not in stack then If child is destination then Update route ← child.route() Update found ← True Add child to stack Return route
The DFS pseudocode makes the stack’s push, pop, explored-node checks, and route construction explicit. section 3.3.2
8-puzzle search
DFS uses a stack to explore puzzle states deeply, then returns to the last decision point when it reaches a dead end. A depth bound can limit expansion. section 3.3.2
