c - How to sort a stack using only stack operations?

Question

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?

Answer 1

Assuming that the only data structure allowed here is the Stack, then you could use 2 Stacks.

Iterate until the original stack is empty and in each iteration, pop an element from the original stack, while the top element in the second stack is bigger than the removed element, pop the second stack and push it to the original stack. Now you can push the element you originally popped off the original stack to the second stack.

The time complexity of this approach is O(N^2).

C code to implement this algorithm would be (excuse my rusty C skills):

void SortStack(struct Stack * orig_stack)
{
  struct Stack helper_stack;
  while (!IsEmpty(orig_stack))
  {
    int element = Pop(orig_stack);
    while (!IsEmpty(&helper_stack) && Top(&helper_stack) < element)
    {
      Push(orig_stack, Pop(&helper_stack));
    }
    Push(&helper_stack, element);
  }
  while (!IsEmpty(&helper_stack))
  {
    Push(orig_stack, Pop(&helper_stack));
  }
}