It is possible to implement Stacks and Queues with both arrays and with links. Instead of implementing all four combinations in this lab, you will implement a stack with links and a queue with an array. These classes can then be used to improve two programs we previously implemented with recursion.
The file LinkedStack.java contains the outline for a linked stack implementation. Look at the file and read through the comments for the methods to make sure that you understand all of them. Complete each of the methods that has a todo comment. Feel free to use your doubly linked list code from the last assignment, but your linked stack should implement a singly linked stack. Remember to code in small pieces and test thoroughly. Proceed only when you are sure that your class is functioning properly.
In class we talked about how all recursive algorithms can be rewritten to not use recursion. The reason this can be done is that the Java runtime uses a stack to know where in the program to return to after a method finishes executing. This is also why the runtime error produced with infinite recursion is called stack overflow. The call stack also stores the local variables of a method so that the state can be restored after a method call.
The paint bucket program that we created in class would fail if the area being filled was so large that the Java runtime ran out of memory for the call stack. Now that you have learned (and created) stacks you can create a looping version of the paint bucket program that will not crash. The file PaintBucket.java contains the program that we created in class. Rewrite the fill method to use a loop and a stack instead of recursion. The looping version of the fill algorithm should begin by pushing the coordinates of the initial fill location onto an empty stack. Then, while the stack is not empty it should pop the top of the stack. If the top coordinate is of the same color as the initial click location, then it should set the color of the pixel at the coordinate and push the coordinates of each of the four neighboring pixels onto the stack.
The file ArrayQueue.java contains the outline for a circular array queue implementation. Look at the file and read through the comments for the methods to make sure that you understand all of them. Complete each of the methods that has a todo comment. Feel free to use your array list code from previous assignments, but your array queue should implement a circular array. Remember to code in small pieces and test thoroughly. Proceed only when you are sure that your class is functioning properly.
Queues are useful for storing data that needs to be processed. In the maze traversal program that we created in class we needed to store the location of branches in the path for future processing. Using a queue it is possible to create a looping version of the maze traversal program.
The file Maze.java contains the maze traversal program that we created in class. Rewrite the canTraverse method to use a loop and a queue instead of recursion. The looping version should begin by adding the location of the start cell to an empty queue. Then, while the queue is not empty it should remove a cell from the queue. If the removed cell is the end cell then the loop should stop and the method should return true. If the cell is not the end cell it should add all of its neighboring cells that are valid to the queue. If the queue becomes empty without ever traversing to the end cell, then the method should return false.
To submit your code: Tar your lab9 directory and submit your code on the course Inquire site.