Java code please

implement a stack and a queue data structure. After testing the class, complete the depth-first search method (provided). The method should indicate whether or not a path was found, and, in the case that a path is found, output the sequence of coordinates from start to end.

A MazeCell class that models a cell in the maze. Each MazeCell object contains data for the row and column position of the cell, the next direction to check, and a bool variable that indicates whether or not the cell has already been visited.

A Source file that creates the maze and calls your depth-first search method.

An input file, maze.in, that may be used for testing.

write the following:

a generic stack class, called MyStack, that supports the provided API (see file stackAPI.png)

a generic queue class, called MyQueue, that supports the provided API (see file queueAPI.png)

an implementation for the depth-first algorithm

Driver class

------------------------------------------------------------------------------------------

import java.io.File; import java.io.FileNotFoundException; import java.util.Scanner;

//starter code for MazeSolver

public class Driver {

/** * * @param start * @param end * find a path through the maze * if found, output the path from start to end * if not path exists, output a message stating so * */ // implement this method public static void depthFirst(MazeCell start, MazeCell end) { }

public static void main(String[] args) throws FileNotFoundException { //create the Maze from the file Scanner fin = new Scanner(new File("Maze.in")); //read in the rows and cols int rows = fin.nextInt(); int cols = fin.nextInt(); //create the maze int [][] grid = new int[rows][cols]; //read in the data from the file to populate for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { grid[i][j] = fin.nextInt(); } }

//look at it for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if (grid[i][j] == 3) System.out.print("S "); else if (grid[i][j] == 4) System.out.print("E "); else System.out.print(grid[i][j] + " "); } System.out.println(); }

//make a 2-d array of cells MazeCell[][] cells = new MazeCell[rows][cols]; //populate with MazeCell obj - default obj for walls

MazeCell start = new MazeCell(), end = new MazeCell(); //iterate over the grid, make cells and set coordinates for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { //make a new cell cells[i][j] = new MazeCell(); //if it isn't a wall, set the coordinates if (grid[i][j] != 0) { cells[i][j].setCoordinates(i, j); //look for the start and end cells if (grid[i][j] == 3) start = cells[i][j]; if (grid[i][j] == 4) end = cells[i][j]; }

} } //testing System.out.println("start:"+start+" end:"+end); //solve it! //depthFirst(start, end); } }

/* * * Provided starter code MazeCell class DO NOT CHANGE THIS CLASS * * models an open cell in a maze each cell knows its coordinates (row, col), * direction keeps track of the next unchecked neighbor\ cell is considered * 'visited' once processing moves to a neighboring cell the visited variable is * necessary so that a cell is not eligible for visits from the cell just * visited * */

class MazeCell { private int row, col; // direction to check next // 0: north, 1: east, 2: south, 3: west, 4: complete private int direction; private boolean visited;

// set row and col with r and c public MazeCell(int r, int c) { row = r; col = c; direction = 0; visited = false; }

// no-arg constructor public MazeCell() { row = col = -1; direction = 0; visited = false; }

// copy constructor MazeCell(MazeCell rhs) { this.row = rhs.row; this.col = rhs.col; this.direction = rhs.direction; this.visited = rhs.visited; }

public int getDirection() { return direction; }

// update direction. if direction is 4, mark cell as visited public void advanceDirection() { direction++; if (direction == 4) visited = true; }

// change row and col to r and c public void setCoordinates(int r, int c) { row = r; col = c; }

public int getRow() { return row; }

public int getCol() { return col; }

@Override public boolean equals(Object obj) { if (this == obj) return true; if (obj == null) return false; if (getClass() != obj.getClass()) return false; MazeCell other = (MazeCell) obj; if (col != other.col) return false; if (row != other.row) return false; return true; }

// set visited status to true public void visit() { visited = true; }

// reset visited status public void reset() { visited = false; }

// return true if this cell is unvisited public boolean unVisited() { return !visited; }

// may be useful for testing, return string representation of cell public String toString() { return "(" + row + "," + col + ")"; } } // end of MazeCell class

---------------------------------------------------------------------

API to be used

MyQ() {}

VOID PUSH (T v){..}

Void pop(){}

Bool empty()cont{.}

Bool empty()cont{.}

Int size() const{.}

T front{.}

My stack(){}

Void push(T v){..}

Int size()const{..}

T & top(){.}

T top()cont{}

Void pop(){}

4 6 1 1 3 1 1 1 1 0 1 0 0 1 1 0 1 0 1 1 1 1 0 0 4 0