Write a program to sort a stack in ascending order. You should not make any assumptions about how the stack is implemented. The following are the only functions that should be used to write this program: push | pop | peek | isEmpty.

I have no idea about this initially…

**Solution**

The idea is simple enough: we use another stack as an auxiliary one. Then we pop items from the original stack and push into the auxiliary stack into the correct position. The time complexity is . It’s similar as Insertion Sort.

public static Stack<Integer> sort(Stack<Integer> stack) {
Stack<Integer> auxiliary = new Stack<Integer>();
while (!stack.isEmpty()) {
Integer value = stack.pop();
while (!auxiliary.isEmpty() && value < auxiliary.peek())
stack.push(auxiliary.pop());
auxiliary.push(value);
}
return auxiliary;
}

### Like this:

Like Loading...

*Related*

thanks

Apr 28, 2014@ 16:38:56very nice thanks you 🙂