A stack is a linear data structure where the last element added is the first one processed: last in, first out (LIFO). section 2.12
Stacks are useful when an algorithm should follow the newest available choice first, exploring deeply before returning to earlier alternatives. section 2.12
A depth-first search uses a stack to:
- Add the starting node. section 2.12
- Pop the next node and make it current. section 2.12
- Push neighboring nodes so they can be explored later. section 2.12
- Continue until the goal is found or the stack is empty. section 2.12
Maze search
In a maze, DFS pushes neighboring positions onto the stack. The most recently added position is explored first, carrying the search to leaf-node depth before backtracking. Parent links can reconstruct the path to the start. section 2.12
def run_dfs(maze_game, current_point):
visited_points = [] #A
stack = [current_point] #A
while stack: #B
next_point = stack.pop() #C
if not is_in_visited_points(next_point,
➥visited_points): #D
visited_points.append(next_point) #D
if maze_game
➥.get_current_point_value(next_point)
➥== '*': #E
return next_point #E
else:
neighbors =
➥maze_game.get_neighbors(next_point) #F
for neighbor in neighbors: #F
neighbor.set_parent(next_point) #F
stack.append(neighbor) #F
return 'No path to the goal found.'
The listing demonstrates stack initialization, repeated popping, visited tracking, neighbor insertion, and termination. section 2.12
