Sort Stack

Problem Statement:

              Recursive In-place Stack Sorting.

Fig: Sort given Stack in O(1)

Source Code

Solution:

            In this problem we will empty the stack and hold in values  in the function call Stack. Then each element from the Function Call Stack is picked and compared with the given stack elements, which again is handled by another  nested Function Call Stack. No extra space is used in sorting the stack.

Sort() Subroutine empties the stack

Below is the implementation: 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

/** * Recursive Inplace Stack Sorting * @author Prateek */ public class SortStack { //input stack private Stack<Integer> stack; public SortStack(Stack<Integer> stack) { this.stack=stack; } /** * Sorting Subroutine */ public void sort(){ if(stack.isEmpty()) return; int item=stack.pop(); sort(); compareAndPush(item); } /** * Pushing each element of stack by recursion * @param item: each item of stack which is compared and pushed to stack */ public void compareAndPush(int item){ if(stack.isEmpty() || item <= stack.peek()) stack.push(item); else { int val=stack.pop(); compareAndPush(item); stack.push(val); } } }

Please comment and post suggestions if any.
Happy Coding !! :)