In this lab, we will implement generic versions of the Stack and Queue data types within the context of searching a maze.
In this lab, we will explore searching a maze for a goal using stacks and queues to organize our potential Trails. The stack allows us to search in a depth-first search manner. In other words, we can explore down a trail as far as possible, and backtrack if we reached a dead end in our journey, because we search the youngest potential trail next. While the queue will allow us to search in a breadth-first search manner, always exploring the oldest potential trail next.
In this lab, you will create the necessary data structures to search a maze in these two ways
To start, run the code in MazeApp. You should see the GUI layout here.
MazeApp
There are a few new pieces to this GUI. First, you will see a choice for either ArrayStack, ListStack, ArrayQueue, or ListQueue. You will find the starter code for these included in the maze.searchers directory.
ArrayStack
ListStack
ArrayQueue
ListQueue
maze.searchers
Second, you will notice that there are statistics in the middle portion of the GUI, recording the number of OPEN, CLOSED, and VISITED squares.
OPEN
CLOSED
VISITED
Third, there is a box at the bottom, to report errors when things go wrong with the underlying implementations. It will also report the number of steps taken when a solution trail is found through searching.
Our first task is to implement a generic Stack interface that can be used in many pieces of the code, for generating and then solving mazes.
Write a class called ArrayStack<E>. This will need to implement the Stack<E> interface. The fields and constructor are provided for you.
ArrayStack<E>
Stack<E>
public void push(E item)
If there is no more room in the stuff array, you will need to resize.
stuff
Now, you can always add the new item to top spot in the stuff array, and increment the top.
top
public E pop()
Call the emptyCheck method. This will throw an IllegalStateException if the stack is empty.
emptyCheck
IllegalStateException
Decrement the value of top, and then return the item in the top spot of the stuff array.
public E peek()
Return the item in the top - 1 spot of the stuff array.
top - 1
public int size()
Return the number of items in stuff.
public String toString()
Return a String representing the elements in the stack separated by spaces. For example, a stack of integers with 3 on top of 2 on top of 1 should return “1 2 3”. The oldest element in the stack should be the first in the string.
String
Run the ArrayStackTest suite, and ensure your above methods are passing these tests.
ArrayStackTest
Next we will implement the generic version of a Stack with nodes, called ListStack<E>. This will need to implement the Stack<E> interface, and have at least a ListNode<E> called top as a field.,
ListStack<E>
ListNode<E>
Look over the file called ListNode.java. This class implements the Node class we discussed. It should have an E value and a ListNode next reference as private components, along with public get and set methods for the value and next fields. There are two constructors. The first brings in and stores only an E value, and leaves the ListNode next as null. The second brings in both an E value, and a ListNode next, storing both.
ListNode.java
E value
ListNode next
null
public void push(E data)
Study the code provided. It will create a new ListNode that stores the data, has the current topas its next, and finally redirects top to reference this new ListNode.
ListNode
data
next
Save the value stored in top, and redirect top to point to the next ListNode.
Return the value you stored.
Return the value stored in the top ListNode.
If top is null, return 0. Otherwise, return the number of ListNode that are chained from the top node.
Run the ListStackTest suite, and ensure your above methods are passing these tests.
ListStackTest
To implement the generic version of a Queue with nodes, you should use the generic ListNode<E> class we implemented last lab.
Write a class called ListQueue<E>. This will need to implement the Queue<E> interface, and have at least a ListNode<E> called front and another called back as fields.
ListQueue<E>
Queue<E>
front
back
public void add(E item)
Create a new ListNode<E> that stores the item.
item
If the queue isEmpty, then set front to this new ListNode<E>.
isEmpty
Otherwise, the current back should refer to this new ListNode<E> as its next.
Finally, redirect back to reference this new ListNode<E>.
public E remove()
Call the emptyCheck method. This will throw an IllegalStateException if the queue is empty.
Save the value stored in front, and redirect front to point to the next ListNode<E>.
public E element()
Return the value stored in the front ListNode<E>.
If front is null, return 0.
Otherwise, return the number of ListNode<E> that are chained from the front node.
Run the ListQueueTest suite, and ensure your above methods are passing these tests.
ListQueueTest
You should now be able see new mazes when you click the Randomize button.
Run the GUI to interact with your code and make random mazes. You should see mazes similar to the image below.
A Trail is another recursive data structure, similar to a ListNode. The two fields of a Trail are a Position, denoting the end of the trail, and a link to another Trail called prev, which is a record of how you arrived at the current Trail. For the first step of a Trail, the prev is left as null.
Trail
Position
end
prev
In this step, you will use Trails to write an algorithm in the Puzzle class that solves a maze using either a Stack or a Queue. This is because the behavior of both is abstracted into a Searcher class. The Searcher class has method names like the Queue.
Trails
Puzzle
Searcher
Queue
public Trail solve(Searcher<Trail> solver)
If there is no Explorer in the maze or no goal in the maze, then return null.
Explorer
Otherwise, add a new Trail starting at the Explorer’s position onto the solver.
solver
While the solver still has potential Trails:
Cell
Maze
If you empty the solver and have still not found the goal, then return null.
Run the PuzzleTest suite, and ensure your above methods are passing these tests.
PuzzleTest
Run the GUI to interact with your code. When you Randomize to create a random maze, add an Explorer and goal, and then click the Solve button, you should see something similar to the following image.
Create 10 mazes of size 30x30 and record the number of visited nodes as a percentage of the total number of open spaces in the initial maze. Also, record the number of steps used by your solver. You can choose either implementation for each data type.
Use this data to compare the Stack versus Queue search strategies. Does either strategy have any clear strengths or weaknesses?