CPSC 170 Lab 11: Stacks

Implementing Stacks

The file Stack.java contains an interface for the stack abstract data type. Note that this class does not require that the elements it contains implement Comparable like the Set interface from the last lab because duplicate elements are allowed and the value of the elements does not affect the ordering of the elements. In class, we have discussed two ways to implement this useful data type - arrays and linked structures. The file ArrayStack.java provides a working implementation of a stack using arrays. Look through the code to make sure that you understand how it is functioning. Some things to observe:

• All the methods in Stack (push, pop, peek, isEmpty, and size) are defined - understand what each is doing.
• There is also an additional private method, expandCapacity.
• The pop and peek methods throw an EmptyStackException, this is implemented in the class EmptyStackException.java.

The file StackTest.java contains code to test a Stack. Download this code and run it. Use this code to confirm your understanding of how a stack operates.

Create a class LinkedStack that implements the Stack interface using links. Note, like the linked set class you will need a separate wrapper class for the stack data. When you think that you have a working linked stack, test the class using the StackTest program. At the interface level, the functionality of the array stack is identical to the linked stack - all of the public methods are the same (as defined in Stack). So, to test your LinkedStack change the definition of the stack variable to be a LinkedStack. Verify that your linked stack does, in fact, behave the same way as the array stack.

Simulating the Call Stack

In class we talked about the difference between head and tail recursion. One of the implications of this difference is that head recursive code can not be converted to looping code without simulating the call stack. The call stack is a stack that the java runtime creates in order 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. Now that you have learned (and created) stacks you can create a looping version of the merge sort algorithm. The file Sorting.java contains all of the sorting methods that we have learned in this class. Add to it a version of the merge sort algorithm that does not use recursion. To help understand what the stack will be used for go through a very simple example of the merge sort algorithm on paper paying attention to the call stack. That is, every time the mergeSort method is called, push the values of the method parameters to a stack. Every time the mergeSort method returns, pop the top set of parameters off of the stack.

Test your non-recursive merge sort method to be sure that it works. Finally, compare the steady state run time of the two methods using the program in the file MergeSortTime.java. Does converting the merge sort algorithm to looping code improve its performance? What about the amount of memory it uses, does that change?

Hand In: Tar your lab directory and e-mail it to your instructor with cpsc170 lab11 in the subject.