Sort a stack without assumptions of implementation

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…

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 O(N^{2}). 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())
		return auxiliary;

1 Comment (+add yours?)

  1. thanks
    Apr 28, 2014 @ 16:38:56

    very nice thanks you 🙂


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: