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…

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 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())
				stack.push(auxiliary.pop());
			auxiliary.push(value);
		}
		return auxiliary;
	}
Advertisements

1 Comment (+add yours?)

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

    very nice thanks you 🙂

    Reply

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s

%d bloggers like this: