I found this question on the web.
Given a stack S, write a C program to sort the stack (in the ascending order). We are not allowed to make any assumptions about how the stack is implemented. The only functions to be used are:
Push
Pop
Top
IsEmpty
IsFull
I think we can build heap and sort it. What is optimal solution to this?
If there is no limitation on using other data structures, I would say the minimum heap. whenever popping a element from stack, put into the heap. When popping is done, taking element from the top of heap (minimum of the rest) and pushing it into the stack. Repeating such process until heap is empty.
For creating a heap, the average time is O(nlogn); for deleting elements from heap and putting elements back in ascending order, the average time is O(nlogn) too.
How does it look?