CPSC 170 Lab 10: Stacks

In the last lab you created unsorted and sorted implementations of a map. In this lab you will create yet another variation on a list, a stack. You have seen stacks in your debugging of Java programs when a program encounters an uncaught exception the stack trace is printed. A stack is a collection that is ordered by when they are added to the collection with the added restriction that only the most recently added element can be removed. Using a stack we can fix the stack overflow problem from the last post lab.

Implementing Stacks

The file Stack.java contains an interface that defines all of the methods for stack classes. Look at the file and read through the comments for the methods to make sure that you understand all of them. Notice that the interface does not require that the elements it contains implement Comparable like the Map interface from the last lab because duplicate elements are allowed and the value of the elements does not affect the ordering of the elements. For this lab you should create a class, either ArrayStack or LinkedStack, that implements the Stack interface using an array or linked implementation. Feel free to use your code from lab 8 to help write these classes. If you would prefer you can use the code in the files List.java, ArrayList.java, and LinkedList.java. Remember to code in small pieces and test thoroughly. Proceed only when you are sure that your classes are functioning properly.

Simulating the Call Stack

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 method call stack can be simulated using a stack and a loop. The Java runtime uses the call stack to know where in the program to return to after a method finishes executing. 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 from the last post-lab 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.

You can use your own code from the post-lab or the code in the file DrawShapes.java. The looping version of the fill algorithm should begin by pushing the coordinates of the initial fill location to 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.

To submit your code: Tar the files in your lab10 directory and copy the tgz file to the directory /home/staff/bouchard/CPSC170A/lab10. Be sure to name the tar file with your names, not lab10.tgz.