CSCI 151 Lab 8: Generic Stacks and Queues (with mazes!)

Overview

In this lab, we will implement generic versions of the Stack and Queue data types within the context of solving mazes.

Setup

Download the skeleton for this project.
Unpack the code into a new Eclipse Java project.

Description

When searching a maze for a path to the exit, we need a way to organize the potential paths we have not yet explored. When visiting a new cell, we take all the potential exits from the cell which we have not yet visited and add them to some data structure. We then pick an unvisited cell from this data structure as the next cell to search, and repeat the process. Both stacks and queues work well as this data structure. If we use a stack, we search the maze in a depth-first manner: we explore down a trail as far as possible, and backtrack only if we reach a dead end, because we always search the youngest potential trail next.

On the other hand, using a queue results in a breadth-first search of the maze, where the oldest potential trail is always expanded next.

In this lab, you will create the necessary data structures to search a maze with either depth-first or breadth-first search.

To start, run the code in MazeApp. After you click on "Randomize", you should see a GUI layout like this:

There are a few new pieces to this GUI. First, you will see a way for you to select a search strategy, either a Stack or a Queue. For each strategy, you will see a list of implementations available. To start, you will find the code for the ArrayStack<E> included in the maze.models.searchers directory.

Second, you will notice that there are statistics in the lower portion of the GUI, recording the number of cells that are open (i.e. in the data structure waiting to be searched), visited (i.e. on the current path), or closed (i.e. lead to a dead end).

Third, there is an error box underneath the Solve button, to report 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.

Step 1 - ListNode<E>

To implement the generic version of a Stack and Queue with nodes, your first task is to reimplement the Node class to be generic. All of your implementations for this lab should be located in the maze.models.searchers directory.

Step 1.1 - Implementation

You will first need to create a class called ListNode that implements a generic singly-linked node. You should be able to copy your implementation of ListIntNode from Lab 5, and modify it to be generic. It should have an E value and a ListNode next reference as components, along with getter and setter methods for the value and next fields.

Step 2 - ListStack<E>

We will next revise your earlier ListIntStack code to be generic.

Step 2.1 - Implementation

Write a class called ListStack<E>. This will need to implement the Stack<E> interface, and have at least a ListNode<E> called top as a field.

Note that there is an additional method to implement, capacity. For implementations based on ListNode, the capacity method should just return the size.

Step 2.2 - Testing

Run the ListStackTest test suite, and ensure your above methods are passing these tests.

Step 2.3 - GUI

Now, run the MazeApp class, and test out your code with the GUI. You should be able to select between the ArrayStack and ListStack implementations.

Step 3 - ListQueue<E>

Now that you are comfortable with generic implementations and the maze framework, implement a Queue using the ListNode<E> from Step 1, as discussed in class.

Step 3.1 - Implementation

Your implementation will have two fields as discussed in class, front and back (also sometimes called head and tail). Create a new generic ListQueue class implementing the Queue<E> interface and completing all of the necessary methods.

Step 3.2 - Testing

Test your code with the ListQueueTest suite.

Step 3.3 - GUI

Run the GUI to try solving mazes with your ListQueue.

Step 4 - ArrayQueue<E>

Finally, you will implement a queue using a circular array-based implementation.

Step 4.1 - Implementation

As discussed in class, your implementation should have three fields:

A front index
size
An array of Objects (which will actually store objects of class E). You should not use an ArrayList, since we need to explicitly manage the storage and keep track of used/unused elements ourselves.

Create a new generic ArrayQueue class implementing the Queue<E> interface and completing all of the necessary methods.

Your code needs to be efficient in terms of the space used. You should treat your array of elements as a circular array, and only resize the array when all positions are full of valid elements in the queue.

The capacity() method should return the length of the array used to store the elements.

Step 4.2 - Testing

Verify that your ArrayQueue is working with the ArrayQueueTest suite.

Step 4.3 - GUI

Run the GUI to interact with your code.

Step 5 - Evaluation

Create 10 mazes of size 30x30 and for each maze and strategy (Stack and Queue), record the number of visited nodes as a percentage of the total number of open spaces in the initial maze. You can choose either implementation for each data type.

Use this data to compare the Stack (depth-first) versus Queue (breadth-first) search strategies. Does either strategy have any clear strengths or weaknesses?

What to Hand In

Submit your ListNode.java, ListStack.java, ListQueue.java and ArrayQueue.java implementations, along with a document for your evaluation in Step 5.

Grading

To earn a D, finish Step 1.
To earn a C, finish the above and Step 2.
To earn a B, finish the above and Step 3.
To earn a A, finish the above and Step 4.
To earn a 100, finish the above and Step 5.