Sort stack in ascending order?

Question

What is the best method to sort the stack in ascending order? I ran into this interview question, and I ran into some problems for a better and effective solution.

There are two methods that I can think of.

• To print the entire contents of the stack and store them in an array, and then sort the array into
  O(nLog n) , and then push the contents back O(nLog n) stack. Not the best way ...

• Recursive stack implementation for sorting it

 void sort(stack) { type x; if (!isEmpty(stack)) { x = pop(stack); sort(stack); insert(x, stack); } } void insert(x, stack) { type y; if (!isEmpty(stack) && top(stack) < x) { y = pop(stack); insert(x, stack); push(y, stack); } else { push(x, stack); } } 

But the second way seems to cause too many recursive calls, and overhead will be a problem if the stack turns out to be really big.

Is it possible to solve this problem much better for better spatial and temporal complexity?

There are so many recursive calls (overlapping subtasks), is this a candidate for the type of dynamic programming problems?

What would be the best way to solve this problem?

Answer 1

This is a stack. You do not see anything but the upper value. You will need to post everything at least once and push everything at least once. The first method is fine.

If stack operations are expensive, but you have a deadline, use insertion sort when you pop up, and you can click as soon as the last pop is done. But you say that this is in C ++, so I doubt that we are considering such a scenario.

Answer 2

You can solve by excluding recursion. To do this, you simply use a loop repeating under the stack until it becomes empty.

For example, pseudo code:

 Linekd Stack stack = new List (); while stack is not empty then element <- stack removes peek / / Recursiong push new elements on stack end 

Answer 3

This problem cannot be more complicated than O (n ^ 2). For more information see here .