Towers of Hanoi

Objectives

Create a last-in-first-out (LIFO) data structure.

Write a program that will solve the Towers of Hanoi.

Solve the problem using both recursion and iteration.

Use stack data structures more extensively.

Getting Started

Create a new Java project called P5 and import TowersOfHanoi-starter.jar.

---> https://www.cs.colostate.edu/~cs165/.Spring18/assignments/P5/archive/TowersOfHanoi-starter.jar

Your directory should look like this:

P5/  resources   Towers.jpg  src  MyStack.java  MyStackTestProgram.java  UserInterface.java  TowersOfHanoi.java  StdDraw.java 

Description

There are two parts to this assignment.

The first part is gaining a better understanding of how stacks work.

The second part is to understand how to implement the Towers of Hanoi algorithm.

Part One - Building a Stack

You will be using a generic ArrayList to create a stack and using the MyStackTestProgram class to test your implementation. The last index of the ArrayList is the top of the stack.

NOTE	You may use any method in ArrayList except contains, indexOf, and lastIndexOf.

Open the MyStack class.

Declare a private field of type ArrayList

Implement each method using the javadoc. https://www.cs.colostate.edu/~cs165/.Spring18/assignments/P5/doc/javadoc/MyStack.html

Start by implementing the toString() method since all of the tests in the MyStackTestProgram class depend on this method being correct.

Remember to incrementally develop. Test one method at a time.

WARNING

Your implementation of MyStack.java MUST pass all testing in order to use it for this assignment.

Part Two - Implementing Towers of Hanoi

Add code to the main method to initialize the puzzle by pushing all the discs onto the left stack, in descending order. Run the program with the command line arguments "10 -recursive" and you should see the picture shown below.

Use the specifications in the javadoc to implement the recursive method.

https://www.cs.colostate.edu/~cs165/.Spring18/assignments/P5/doc/javadoc/TowersOfHanoi.html#recursiveHanoi-int-int-int-int-

Use the specifications in the javadoc to implement the Move class.

https://www.cs.colostate.edu/~cs165/.Spring18/assignments/P5/doc/javadoc/TowersOfHanoi.Move.html

Use the specifications in the javadoc to implement the iterative version

https://www.cs.colostate.edu/~cs165/.Spring18/assignments/P5/doc/javadoc/TowersOfHanoi.html#iterativeHanoi-int-int-int-int-

Standard Draw File 2 4