In this lab assignment, you will create a Java application that sorts a stack recursively.

Consider the following algorithm to sort the entries in a stack S _1:

1. First create two empty stacks, S ₂ and S ₃ . At any given time, stack S ₂ will hold the entries in sorted order, with the smallest at the top of the stack.

2. Put the top entry of S ₁ into T (a variable that can hold stack elements)

3. Pop and consider the top entry T of S ₁ .

4. Pop entries of stack S ₂ and push them onto stack S ₃ until you reach the correct place to put T .

5. Then push T onto S ₂ .

6. Next move entries from S ₃ to S ₂ .

7. Repeat until S ₁ is empty and S ₂ contains the sorted stack.

 

Requirements:

1. Your application uses unbounded stacks from chapter 2 in your text.

2. Write a main method to create an unsorted stack and display the unsorted stack.

3. Send the stack to a method for sorting. Upon return from the method, display the now sorted stack.

4. Write a recursive method that accepts an unsorted Stack and returns a sorted Stack. The method should be generic and work for all types of stacks.

5. Test your recursive method to make sure it works for different types of stacks.

May want to use a public method that accepts the original stack and then creates the two additional stacks needed. This method then calls a private method that accepts all three stacks and does the recursive sort. Your methods should make sure all types of stacks passed contain comparable objects. Refer to the generic presentation in Shared Files.