Project 10

In class I constructed several stack implementations. For this project, use the implementation supplied by Java itself, which can be found in java.util.*.

Your problem is to write a sorting method for Comparable objects. Your method will use two stacks, both of which should be generic on Comparable. More specifically, create a class called StackSorter. An instance of this manages two Stack<comparable> objects (let me call the stacks one and two). And there should be two methods (and a constructor). The methods are to be called addItem which takes a Comparable parameter and returns void , and getList which returns an array of Comparable but has an empty parameter list.

The method addItem works as follows.

  1. Assume that before addItem is called, the Objects in stack one are in order from smallest on top to biggest on the bottom, and stack two is empty. When a Comparable Object, call it next, is supplied to addItem as a parameter, it is to be inserted into stack one so that stack is still in order. First the proper location for the insertion must be found. To do this, pop objects from one and push them onto two, until either the top of one is bigger than next, or one empties out. Then
  2. Push next onto one, and finally
  3. Pop objects from two and push them back onto one, until two empties out.
  4. At this point next has been added to stack one, and that stack is still in proper order.

The method getList works as follows.

  1. When called, each item is popped from stack one, counted, and pushed onto stack two, until one is empty.
  2. Now that it is known how many objects there are, an array of type Comparable is created, whose size is the number of objects.
  3. Then integers are popped from stack two, put into the array, and also pushed back into one.
  4. Finally the filled array is returned.

You are to write the code for the class StackSorter. I will combine it with my Driver. So you should also try running it with my Driver. It generates 20 random Integer objects, uses StackSorter to sort them, and prints the results. It then generates 10 more random integers, adds them to the set that StackSorter has, and prints the combined results.

Solution: