Application #6

Part1

Implement the following algorithm (method sort()) that sorts entries on a stack: original stack contains entries that are not sorted. First create two empty stacks, destination and temp. At any given time, destination stack must hold the entries in sorted order, with the smallest at the top of the stack. Move the top entry of original stack to destination stack. Pop and consider the top entry topO of original stack. Using a while loop pop entries of destination stack and push them onto temp stack until you reach the correct place to put topO. Then push topO onto destination stack. Next using a while loop move all the entries from temp stack to destination stack. Repeat the process for as long as the original stack is not empty.

Part2

Now consider the following revision of the above algorithm (method sortRevised()) : after moving the top entry of original stack to destination stack, compare the new top entry topO of the original stack with the top entry of destination stack. Then either move entries from destination stack to temp stack or from temp stack to destination stack until you locate the correct position for topO. Push topO onto destination stack. Continue until original stack is empty. Finally move any entries remaining in temp stack to destination stack.

Your finished program should produce the following output:

import java.util.*; public class SortStack> { private Stack stack; public SortStack() { this.stack = new Stack<>(); } /**  * Sorts a stack.  *  * @return a sorted stack  */  public Stack sort() { // TODO PROJECT #6 Part1  // this.stack represents the original stack Stack destination = new Stack<>(); Stack temp = new Stack<>(); return destination; } /**  * Sorts a stack. (revised version)  *  * @return a sorted stack  */  public Stack sortRevised() { // TODO PROJECT #6 Part2  // this.stack represents the original stack Stack destination = new Stack<>(); Stack temp = new Stack<>(); return destination; } public void setStack(T... elements) { this.stack.clear(); System.out.println("Setting the original stack to:"); for (int i = 0; i < elements.length; i++) { this.stack.push(elements[i]); System.out.print(elements[i] + " "); } System.out.println(); } public static void main(String[] args) { SortStack sc = new SortStack(); sc.setStack("03", "09", "01", "04", "06", "05", "07", "08", "00", "02"); System.out.println(" ***Calling sort method***"); Stack sortedStack = sc.sort(); System.out.println(" Stack should be sorted (with sort()) ...."); while (!sortedStack.isEmpty()) System.out.print(sortedStack.pop() + " "); System.out.println(); System.out.println(" ==================================="); System.out.println(" Testing the revised method"); sc.setStack("03", "09", "01", "04", "06", "05", "07", "08", "00", "02"); System.out.println(" ***Calling sortRevised method***"); sortedStack = sc.sortRevised(); System.out.println(" Stack should be sorted (with sortRevised()) ...."); while (!sortedStack.isEmpty()) System.out.print(sortedStack.pop() + " "); System.out.println(); } // end main } // end SortStack

***Calling sort method***

push 02 from original to destination

Moving entries from destination to temp

push 00 to destination

Moving entries from temp to destination

Moving entries from destination to temp

--> push 00 from destination to temp

--> push 02 from destination to temp

push 08 to destination

Moving entries from temp to destination

--> push 02 from temp to destination

--> push 00 from temp to destination

Moving entries from destination to temp

--> push 00 from destination to temp

--> push 02 from destination to temp

push 07 to destination

Moving entries from temp to destination

--> push 02 from temp to destination

--> push 00 from temp to destination

Moving entries from destination to temp

--> push 00 from destination to temp

--> push 02 from destination to temp

push 05 to destination

Moving entries from temp to destination

--> push 02 from temp to destination

--> push 00 from temp to destination

Moving entries from destination to temp

--> push 00 from destination to temp

--> push 02 from destination to temp

--> push 05 from destination to temp

push 06 to destination

Moving entries from temp to destination

--> push 05 from temp to destination

--> push 02 from temp to destination

--> push 00 from temp to destination

Moving entries from destination to temp

--> push 00 from destination to temp

--> push 02 from destination to temp

push 04 to destination

Moving entries from temp to destination

--> push 02 from temp to destination

--> push 00 from temp to destination

Moving entries from destination to temp

--> push 00 from destination to temp

push 01 to destination

Moving entries from temp to destination

--> push 00 from temp to destination

Moving entries from destination to temp

--> push 00 from destination to temp

--> push 01 from destination to temp

--> push 02 from destination to temp

--> push 04 from destination to temp

--> push 05 from destination to temp

--> push 06 from destination to temp

--> push 07 from destination to temp

--> push 08 from destination to temp

push 09 to destination

Moving entries from temp to destination

--> push 08 from temp to destination

--> push 07 from temp to destination

--> push 06 from temp to destination

--> push 05 from temp to destination

--> push 04 from temp to destination

--> push 02 from temp to destination

--> push 01 from temp to destination

--> push 00 from temp to destination

Moving entries from destination to temp

--> push 00 from destination to temp

--> push 01 from destination to temp

--> push 02 from destination to temp

push 03 to destination

Moving entries from temp to destination

--> push 02 from temp to destination

--> push 01 from temp to destination

--> push 00 from temp to destination

Stack should be sorted (with sort()) ....

00 01 02 03 04 05 06 07 08 09

===================================

Testing the revised method

Setting the original stack to:

03 09 01 04 06 05 07 08 00 02

***Calling sortRevised method***

--> push 02 from original to destination

Moving entries from destination to temp

Moving entries from temp to destination

push 00 from original to destination

Moving entries from destination to temp

--> push 00 from destination to temp

--> push 02 from destination to temp

Moving entries from temp to destination

push 08 from original to destination

Moving entries from destination to temp

Moving entries from temp to destination

push 07 from original to destination

Moving entries from destination to temp

Moving entries from temp to destination

push 05 from original to destination

Moving entries from destination to temp

--> push 05 from destination to temp

Moving entries from temp to destination

push 06 from original to destination

Moving entries from destination to temp

Moving entries from temp to destination

--> push 05 from temp to destination

push 04 from original to destination

Moving entries from destination to temp

Moving entries from temp to destination

--> push 02 from temp to destination

push 01 from original to destination

Moving entries from destination to temp

--> push 01 from destination to temp

--> push 02 from destination to temp

--> push 04 from destination to temp

--> push 05 from destination to temp

--> push 06 from destination to temp

--> push 07 from destination to temp

--> push 08 from destination to temp

Moving entries from temp to destination

push 09 from original to destination

Moving entries from destination to temp

Moving entries from temp to destination

--> push 08 from temp to destination

--> push 07 from temp to destination

--> push 06 from temp to destination

--> push 05 from temp to destination

--> push 04 from temp to destination

push 03 from original to destination

Moving any remaining entries from temp to destination

--> push 02 from temp to destination

--> push 01 from temp to destination

--> push 00 from temp to destination

Stack should be sorted (with sortRevised()) ....

00 01 02 03 04 05 06 07 08 09