Please read all parts carefully:
Part1: You are to create a file called Stack.java. It will implement a LIFO Stack class with the following requirements:
• It should implement the 5 same exact methods as the Java built-in Stack class (see the Java website).
• Your methods should also throw the same exceptions as the Java built-in Stack class. Specifically, pop and peek should both throw a new EmptyStackException if nothing is in the Stack. Please note that EmptyStackException is one of the very few exceptions that does not accept a descriptive String to its constructor.
• It should also implement a toString() method. The toString() method should just return the Stack as a String. If you used an ArrayList (internal or inherited) to hold the data, toString() should just return that ArrayList’s toString() (like our Queue demo). The tester (see below) relies on toString() being implemented.
• It should implement Generics so that the user can decide what it will hold at the time it is created.
You can look at our Queue.java and QueueDriver.java demo as a guide for how to implement it.
For testing, you can use the provided StackTester.java – it tests each method with an empty Stack, a Stack with a single element in it, and a Stack with many elements in it. It compares your results with that of java.util.Stack.
Part2 (just background, but very important so you will know how to call the Maze’s methods): Look at the Maze.java file; it contains the code for the Maze.
• At the very end of the Maze class is defined an enumerated data type called Direction. When working with a Maze, the directions that you can use are UP, DOWN, LEFT, and RIGHT. Since Direction is defined inside Maze, you have to refer to it as Maze.Direction and refer to the various directions as Maze.Direction.UP etc. You can use enumerated data types as a type in the same way that you would use other types or classes. For example, you could have:
o Maze.Direction whichWay; //whichWay is a Maze.Direction; can have a value of
//Maze.MazeDirection.LEFT for example.
o Stack<Maze.Direction> myStack; //Generics
o whichWay = Maze.Direction.UP; //note
This will be extremely important, as the Maze methods that you have available are expecting Maze.Directions…
• For background only (not needed to know or use) is a class that is defined at the very end of Maze.java. It is a custom type of exception called IllegalMazeMoveException. I am simply pointing it out because it is very easy to create your own exceptions. IllegalMazeMoveException is a subclass of IllegalArgumentException and will inherit all the data and methods it needs to work. A constructor had to be written, but by calling super(str), it just does whatever its parent would do if it received the str. So we don’t have to know exactly how exceptions work in order to write our own because all of the functionality is inherited. The Maze class will throw this exception if an illegal move is made.
Part3 (familiarizing yourself with Maze and MazeDisplay). You are given the Maze class and the MazeDisplay class. You can create and work with a Maze by itself, but when you also create a MazeDisplay (passing in the Maze), then it becomes animated. Write a small driver program and try this code:
Maze aMaze = new Maze(8, 10); //creates an 8x10 Maze
aMaze.build(75); //builds it, animation delay is set to 75 milliseconds
//(if you want it faster, make the delay smaller)
MazeDisplay display = new MazeDisplay(aMaze); //creates a MazeDisplay with aMaze in it. Since aMaze
//has already been built, no animation will be shown yet.
…Or you could try this code, where the order is slightly different:
Maze aMaze = new Maze(8, 10); //creates a 8x10 Maze
MazeDisplay display = new MazeDisplay(aMaze); //creates a MazeDisplay with aMaze in it. Since build
//comes after it is displayed, it will show it being built.
aMaze.build(140); //builds it, animation delay is set to 140 milliseconds
//if you want it faster, make the delay smaller
You are to write a program called Program3.java. In it, your main method should do the following:
• Ask the user how many rows the Maze should have (minimum 5, which could be stored as a constant).
Read in their answer.
• Ask the user how many columns the Maze should have (minimum 6, which could be stored as a constant).
Read in their answer.
• Create a new instance of Maze, passing in the numRows and numCols to the Maze’s constructor (like the previous examples, except with variables…)
• Create a new instance of MazeDisplay, passing in the Maze. You can watch it being built or not, with any animation delay you want.
• Tell the new Maze instance to setSolveAnimationDelay, passing in how long it should wait between moves. This is so the animation does not happen so fast that you cannot watch it or so slow it wastes time…
• Once the Maze is built and displayed, you are to write code to solve it. You cannot change or add code to the Maze class, but only use Maze’s existing public methods. They are:
//-------- getCurrentRow - returns the current (real) row
public int getCurrentRow()
//-------- getCurrentCol - returns the current (real) col
public int getCurrentCol()
//-------- isOpen - returns true if there is no wall in the direction that is passed in
public boolean open(Direction direction)
// -------- move - receives a Direction and moves there if OK. Calls the other arrayMove to do this
// returns true if successful.
public boolean move(Direction direction)
//-------- goalReached - returns true if the maze is solved (current location == goal)
public boolean goalReached()
//------- setSolveAnimationDelay - sets the delay (milliseconds) for the maze being solved (in case its
public void setSolveAnimationDelay(int theDelay)
• Since many of these methods receive a Direction (a Maze.Direction since you will be outside the Maze class), you will have to pass in things like Maze.Direction.DOWN when you use it.
• You will also have to have a Stack that holds Maze.Direction to keep track of where you have gone so you know what to do if you come to a dead end. You also will need some sort of data structure to keep track of which cells have been “visited” as you go through the Maze. My suggestion is a 2-dimensional array of booleans so you can mark a (row,col) as true once the corresponding cell in the maze has been visited.
• The basic algorithm is to try going UP, DOWN, LEFT, or RIGHT to legally move through the Maze and taking care to go to a cell (location) that you have already been to. If there is no new location to go to, you have to use the Stack to backtrack. This can be done as follows:
Tell the Maze to setSolveAnimationDelay, passing in an int that is the “delay,” or how many milliseconds to delay between each move. This will regulate the animation as it is displayed.
Mark the current (starting) cell you are at as “visited.” Set to true if you are using a 2-D array to keep track of whether or not cells have been visited.
Repeat the following actions until the goal location is reached
If it is open (there is not a wall) in the UP direction (Maze.Direction.UP) and you have not visited the cell above you (the UP direction), then push Maze,Direction.UP onto your Stack and mark the cell you arrived at as “visited.” Tell the maze instance to move UP.
Else if it is open (there is not a wall) in the DOWN direction (Maze.Direction.DOWN) and you have not visited the cell below you (the DOWN direction), then push Maze.Direction.DOWN onto your Stack and mark the cell you arrived at as “visited.” Tell the maze instance to move DOWN.
Else ….(try the same thing for the LEFT direction. Same logic)
Else …(try the same thing for the RIGHT direction. Same logic)
Else – you have come to a dead end. Pop the Stack to see the direction you came from. Tell the maze instance to move in the opposite direction, which will accomplish thebacktracking.
After the loop ends successfully, print “Maze is solved.”
Comments and formatting: For maintainability, you should be sure to comment your classes, methods, and logic. Also (for maintainability) indent correctly and use appropriate white space, variable names, and constants.
This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden./* This program implements a Maze. Internally, walls and data are stored
in a single 2D array; the entries whose row/col are even-odd or odd-even
are the walls and the entries whose row/col are odd-odd are the cells
themselves. Therefore, a 4x5 maze will be stored in a 9x11 array so the
walls can be stored as well as the cells. In the code, the variable names
try to make it clear which it is working with (realRow vs arrayRow).
public class Maze implements Serializable
private int[ ][ ] mazeArray;
private int currentArrayRow;
private int currentArrayCol;
private int goalArrayRow;
private int goalArrayCol;
private int buildAnimationDelay;
private int solveAnimationDelay;
private boolean alreadyBuilt;
public Maze(int numRealRows, int numRealCols)
//since the maze is being created, initialize alreadyBuilt to false
alreadyBuilt = false;
//set the buildAnimationDelay and solveAnimationDelay to 0; they can be reset with methods
buildAnimationDelay = 0;
solveAnimationDelay = 0;
//make sure that the numRealRows and numRealCols are both > 1 (start cannot == goal)
if (numRealRows < 2)
throw new IllegalArgumentException("number of rows must be > 1");
if (numRealCols < 2)
throw new IllegalArgumentException("number of columns must be > 1");
//create the 2D array to hold the maze (its even rows/cols hold the walls, odd rows/cols hold the paint
mazeArray = new int[2*numRealRows+1][2*numRealCols+1];
//since the even values are the walls, set anything with an even component to 1 (wall exists to start)
for (int row=0; row<mazeArray.length; row++)
for (int col=0; col<mazeArray[row].length; col++)
if (row%2==0 || col%2==0) //if either dimension is even...
mazeArray[row][col] = 1; //its a wall, so set value to 1
//initialize the currentArrayRow and currentArrayCol to the upper left corner
currentArrayRow = 1;