Sudheer S Sudheer S - 2 months ago 6
Java Question

Sorting numbers in Stack using one int variable

I have a Stack variable (java collection) which holds five integers and I was also given one int variable. Is it possible to sort the numbers in the given stack. I am not able to solve that. Please post here if you have ideas.

Stack<Integer> s = new Stack<Integer>();
s.push(5);s.push(3);s.push(4);s.push(1);s.push(1);
int a;


We should not create any new variable except the one given in the above code snippet and also should not use Collections.sort(s).

Answer

Here i found the perfect answer from geeksforgeeks which uses recursion. http://www.geeksforgeeks.org/sort-a-stack-using-recursion/ Just posting the same algorithm here.

Algorithm:

We can use below algorithm to sort stack elements:

sortStack(stack S)
if stack is not empty:
    temp = pop(S);  
    sortStack(S); 
    sortedInsert(S, temp);

Below algorithm is to insert element is sorted order:

sortedInsert(Stack S, element)

if stack is empty OR element > top element
    push(S, elem)
else
    temp = pop(S)
    sortedInsert(S, element)
    push(S, temp)