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

Game of three stacks

With three stacks S (source stack, the stack with unsorted elements), A, B you can start playing a game similar to merge sort.

I think it is clear that if you have ordered elements on A and B (in the same direction, both ascending or both descending), that you can use S to merge sort A and B and then move the result to, for example, B.

The fact that you have some elements on A, B or S does not stop you from being able to use A, B or S for merging(, as long as you have the marker of the current size of A, B and S so you would not overshoot). If your procedure brings ordered elements on S, it is no brain to use A and B to remove the sorted portion to A or B in any direction you like: you can place it in reverse order to A or B directly, or, for example, place all elements to A and than reverse once again to B.

Assume that you have 4 sorted elements on A, 16 on B and some unsorted elements on S.

A.push(S.pop) and now create a 2-element sorted merge. Again B.push(S.pop) and create another one 2-element sorted merge. If the merges are not separated and/or not in the same direction, you can manipulate elements any way you like until you reach 4-element sorted merge on B (or even S). Now merge the initial 4-element sorted merge from A and that part on B, until you reach 8-element sorted merge.

You repeat everything until you create another 8-element sorted merge. You place it in right order on B (or S) and merge in order to get 16-element sorted merge. Now you place it on A (or S) and merge with 16-element merge that we've had on B all along.

The optimized implementation is tricky since you need to reduce moving (reverting) sorted merge from one stack to another. However if you fix and decide what for you are going to use A, B and S and force for example: A to contain the smaller and B larger merged portion in descending order then the algorithm is simpler.

The fact that you need to move some top elements from one stack to another is adding a constant factor to complexity, but it is never more than 2. Other than that the complexity is n*log(n) (you reach a 2n-element sorted merge by merging 2 n-element sorted merges, and a merging requires no more than 2n steps.)

Implementation in C# (other similar languages are obvious)

    void Stacking(Stack<int> sourceStack, Stack<int> mainStack, Stack<int> childStack, int n)
    {
        if (n == 0) return;

        if (n == 1)
        {
            mainStack.Push(sourceStack.Pop());
            return;
        }

        int mainSize = n/2;
        int childSize = n - n/2;

        Stacking(sourceStack, mainStack, childStack, mainSize);
        Stacking(sourceStack, childStack, mainStack, childSize);

        while (true)
        {
            while (mainSize > 0 && mainStack.Peek() >= childStack.Peek())
            {
                sourceStack.Push(mainStack.Pop());
                mainSize--;
            }

            if (mainSize == 0) break;

            while (childSize > 0 && childStack.Peek() >= mainStack.Peek())
            {
                sourceStack.Push(childStack.Pop());
                childSize--;
            }

            if (childSize == 0) break;
        }

        while (mainSize > 0)
        {
            sourceStack.Push(mainStack.Pop());
            mainSize--;
        }

        while (childSize > 0)
        {
            sourceStack.Push(childStack.Pop());
            childSize--;
        }

        for (int i = 0; i < n; i++)
            mainStack.Push(sourceStack.Pop());
    }

    void SortStack(Stack<int> sourceStack)
    {
        int n = sourceStack.Count();

        // possible optimization: if (n < 2) return;

        Stack<int> mainStack = new Stack<int>();
        Stack<int> childStack = new Stack<int>();

        Stacking(sourceStack, mainStack, childStack, n);

        for (int i = 0; i < n; i++)
            sourceStack.Push(mainStack.Pop());
    }

Game of log(n) stacks

The above procedure could be simplified if you are allowed to use at most log(n) stacks. This number of stacks does not mean that you will ever use an additional space larger than order of n. You simply mark stacks that will be used for merging 1, 2, 4... elements. In this case you do not care about the order since merging parts of 2^n will always be sorted in the same direction. However, this solution is only circumventing the fact that you are limited to use push and pop operation; other than that it is equivalent to merge sort in all aspects. In essence, if the number of stacks is not limited then you can easily emulate quick sort as well.

Answer 2

I think that the bubble sort could work on the stack with recursion.

   void sortStack(stack<int>& st){
        bool flag = true;
        int n = st.size();
        for(int i = 1; i <= n - 1 && flag; i++){
            flag = false;
            bubbleSortStack(st, flag, i);
        }
    }
    void bubbleSortStack(stack<int>& st, bool& flag, int endSize){
        if(st.size() == endSize)
            return;
        int val = st.top();
        st.pop();
        if(val > st.top()){
            flag = true;
            int tmp = st.top();
            st.push(val);
            val = tmp;
        }
        bubbleSortStack(st, flag);
        st.push(val);
    }

Answer 3

/* the basic idea is we go on
 *  popping one element (o) from the original stack (s) and we
 *  compare it with the new stack (temp)
 * if o (the popped element from original stack)
 *  is < the peek element from new stack temp
 * then we push the new stack element to original stack
 *  and recursively keep calling till temp is not empty
 *  and then push the element at the right place.
 * else we push the element to the new stack temp
 *  (o >= new temp stack.
 *
 * Entire logic is recursive.
 */

public void sortstk( Stack s )
{
    Stack<Integer> temp = new Stack<Integer>();

    while( !s.isEmpty() )
    {
        int s1 = (int) s.pop();

        while( !temp.isEmpty() && (temp.peek() > s1) )
        {
            s.push( temp.pop() );
        }
        temp.push( s1 );
    }

    // Print the entire sorted stack from temp stack
    for( int i = 0; i < temp.size(); i++ )
    {
        System.out.println( temp.elementAt( i ) );
    }
}

Answer 4

It can be done recursively using the same stack. O(n^2) I have coded it in C++ but the conversion to C is trivial. I just like templates and you did tag your question as C++

template<typename T>
void Insert(const T& element, Stack<T>& stack)
{
  if(element > stack.Top())
  {
    T top = stack.Pop();
    Insert(element, stack);
    stack.Push(top);
  }
  else
  {
    stack.Push(element);
  }
}

template<typename T>
void StackSort(Stack<T>& stack)
{
  if(!stack.IsEmpty())
  {
    T top = stack.Pop();
    StackSort(stack);
    Insert(top, stack);    
  }    
}

Edited to get my vote back! :))

Answer 5

Modified code from T33C's answer
(given before Svante corrected the language tag from c++ to c):
stack.top() can only be checked if !stack.empty()

void insert(int element, stack<int> &stack) {
    if (!stack.empty() && element > stack.top()) {
        int top = stack.top();
        stack.pop();
        insert(element, stack);
        stack.push(top);
    }
    else {
        stack.push(element);
    } 
}

void sortStack(stack<int> & stack) {
    if (!stack.empty()) {
        int top = stack.top();
        stack.pop();
        sortStack(stack);
        insert(top, stack);
    }
}

Answer 6

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));
  }
}