Swapping in a Queue

Look back at the loop we just wrote. It does four things: take a waiting cell, check whether it is the exit, add its valid, unvisited neighbors, and stop when nothing is left waiting. We first chose a stack because we wanted to turn the recursive search into an iterative one, with an explicit stack in place of the call stack. But the tidied-up version already stopped following the recursion’s visiting order, and it still finds a path whenever one exists. So the stack is not what makes the search correct. The only thing the stack decides is which waiting cell we take next. That does not have to be the most recently added one.

So we can replace the structure that holds the waiting cells. We already know one other structure that keeps waiting items in order: the queue. Let’s replace the stack with a queue and see whether the search still works.

Before running the code, we can reason about whether the search will still be correct. Swapping the structure changes which waiting cell comes out next. The visited array still stops us from exploring a cell twice, so the search still cannot loop forever. isExit still recognizes the goal. An empty structure still means there is nowhere left to go, and so no path. The guard for the start cell is unchanged, so a start cell that is a wall is handled the same way. None of those depended on the stack’s last-in, first-out rule. So the search should still work with a queue.

Here is the queue version. Compared to the stack version, only a few words change: the type of the structure, and the three operation names.

public static boolean hasPathWithQueue(char[][] maze) {
  if (!isOpen(maze, 0, 0)) {
    return false;
  }

  boolean[][] visited = new boolean[maze.length][maze[0].length];
  Queue<Position> toExplore = new LinkedQueue<>();

  toExplore.enqueue(new Position(0, 0));
  visited[0][0] = true;

  int[] rowChange = {0, 1, 0, -1};
  int[] colChange = {1, 0, -1, 0};

  while (!toExplore.isEmpty()) {
    Position current = toExplore.front();
    toExplore.dequeue();

    if (isExit(maze, current.row, current.col)) {
      return true;
    }

    for (int i = 0; i < rowChange.length; i++) {
      int nextRow = current.row + rowChange[i];
      int nextCol = current.col + colChange[i];
      if (isOpen(maze, nextRow, nextCol) && !visited[nextRow][nextCol]) {
        toExplore.enqueue(new Position(nextRow, nextCol));
        visited[nextRow][nextCol] = true;
      }
    }
  }

  return false;
}

The difference is in the order in which cells are processed. The stack-based search follows a single path as far as it can go before backtracking, because it processes the most recently added cell first. The queue-based search, on the other hand, processes cells in the order they were added, which means it explores all cells one move from the start before moving to any cell two moves from the start.

Like the stack-based search and the recursive search, the queue-based search finds a path whenever one exists. But if there is more than one path, the three searches may reach the exit by different routes.