JAVA please!

For this project, 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.

The following code and related files are provided. Carefully ready the code and documentation before beginning.

• 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.

You will 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.

*I will include all the sources below.

Queue

Stack

//Source for MazeSolver

#include #include #include #include #include "myStack.h" #include "MyQ.h" #include "MazeCell.h"

using namespace std;

#define NORTH 0 #define EAST 1 #define SOUTH 2 #define WEST 3 #define DONE 4 #define SUCCESS 10 #define FAILURE 20

//method headers*******************************************************

//depthFirst header void depthFirst(MazeCell start, MazeCell end);

//global variables*****************************************************

//# rows and cols in the maze int rows, cols; //pointer to the grid (2-d array of ints) int** grid; //pointer to the maze cells (2-d array of MazeCell objects) MazeCell** cells;

int main() { //create the Maze from the file ifstream fin("maze.in"); if(!fin){ cout

//read in the rows and cols fin >> rows >> cols;

//create the maze rows grid = new int* [rows]; //add each column for (int i = 0; i

//read in the data from the file to populate for (int i = 0; i > grid[i][j]; } }

//look at it for (int i = 0; i

//make a 2-d array of cells cells = new MazeCell * [rows]; for (int i = 0; i

//all MazeCell in the cells grid has a default init //only update those cells that are not walls

MazeCell start, end; //iterate over the grid for (int i = 0; i

} } //testing cout

return 0; }

//this function should find a path through the maze //if found, output the path from start to end //if not path exists, output a message stating so

void depthFirst(MazeCell start, MazeCell end) { }

MAZECELL

//models an open cell in a maze //each cell knows its coordinates (row, col), //direction keeps track of the next unchecked neighbor. //a 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 int direction; bool visited;

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

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

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

int getDirection()const { return direction; }

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

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

int getRow()const { return row; }

int getCol()const { return col; }

//cells are equal if they have the same row and col, respectively bool operator==(const MazeCell& rhs)const { return row == rhs.row && col == rhs.col; }

bool operator!=(const MazeCell& rhs)const { return !((*this) == rhs); }

//output cell as ordered pair friend ostream& operator

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

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

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

//may be useful for testing, return string representation of cell string toString()const { string str = "(" + to_string(getRow()) + "," + to_string(getCol())+ ")"; return str; }

MyQ() { ... } void push(T v) { ... } void pop() { ... } bool empty() const { ... } } int size() const { ... } I front() const { ... } MyStack() {...} void push(T v) { ... } int size() const {...} bool empty() const {...} T& top() { ... } I top() const {...} void pop() {...}]