The Stack Search in Code

Let’s turn the stack search from the previous section into code.

The recursion carries the current cell as two parameters, row and col. Our stack needs to hold cells as data we can push and pop, so we bundle a row and column into a small object:

private static class Position {
  int row;
  int col;

  Position(int row, int col) {
    this.row = row;
    this.col = col;
  }
}

With that, here is the whole search:

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

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

  toExplore.push(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.top();
    toExplore.pop();

    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.push(new Position(nextRow, nextCol));
        visited[nextRow][nextCol] = true;
      }
    }
  }

  return false;
}

The Stack<Position> is the stack we drew. We use the ArrayStack from the stack chapter, though a LinkedStack would work just as well. Before the loop, we push the start cell and mark it visited. That is the first picture in the trace:

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

The guard above them, if (!isOpen(maze, 0, 0)), is the start check from the previous section. The recursion catches the same case with its first base case: if the start itself is a wall, there is no path to look for.

Each pass of the while loop takes the cell on top and removes it, which is one pop in the trace:

Position current = toExplore.top();
toExplore.pop();

We read the top with top and then remove it with pop, because the stack ADT keeps those two actions separate. Once we have the cell, we check it with isExit. If we just popped the exit, the search ends there.

The for loop is where we try the four neighbors. The recursion writes them out as four separate recursive calls; here a single loop iterates over four offsets instead. The arrays rowChange and colChange are meant to be read together. Index 0 adds 0 to the row and 1 to the column, which moves right; index 1 moves down; the last two move left and up. So the loop checks the neighbors in the clockwise order that we decided on in the last section: right, down, left, up.

For each neighbor, the if asks the question we asked for every neighbor in the trace: is it valid and unvisited? Only a cell that passes this test is pushed:

toExplore.push(new Position(nextRow, nextCol));
visited[nextRow][nextCol] = true;

We mark the cell when we push it. That is the timing we were careful about in the trace.

When current has no open, unvisited neighbor, the for loop simply pushes nothing, and the next pass of the while loop pops the cell that is now on top of the stack. And when the stack empties without ever popping the exit, the loop ends and the method returns false.

Edge Cases

Let’s check the stack search against the edge cases from the problem statement:

• If the start cell is a wall, the guard at the top returns false before anything is pushed.
• If the exit cell is a wall, it fails the isOpen check, so it is never pushed. The search never pops it, and it returns false once the stack is empty.
• If the maze has one open cell, the guard passes, and the first cell we pop is the exit. The search returns true.
• The search does not keep revisiting the same cells forever. A cell is marked as visited when it is pushed, so it is never pushed again.