Sort a stack using temporary stack and recursion

Sort a stack using temporary stack and recursion

There are two different methods to sort a stack. They are


  • Method 1:In this approach, a stack is sorted using another temporary stack.
  • Method 2:In this approach, a stack is sorted using recursion.



Method 1 to sort a stack using a temporary stack


The push and pop operations are carried out between the input_stack and the temporary_stack in such a way that the temporary stack contains the sorted input stack. The algorithm to sort a stack using another temporary stack is discussed below.


Algorithm


  1. Create a temporary stack say temp_stack.
  2. Repeat until the input_stack is not empty
  3. Pop an element from input_stack call it temp.
  4. While temp_stack is not empty and top of the temp_stack > temp, pop data from temp_stack and push it to the input_stack
  5. Push temp to the temp_stack
  6. Print the temp_stack.


@@coding::1@@


Method 2 to sort a stack using recursion


The algorithm given below describes how to sort a stack using recursion .


Algorithm


sort_stack(stack)


  1. If the stack is not empty,


  • Pop element from the stack and store it in a temporary variable say temp.
  • Sort_and_insert(stack, temp)



sort_and_insert(stack, temp)


  • If the stack is empty or temp >stack.top()
  • Push temp to the top of the stack.
  • else,
  • Pop data from stack and store it in temp2.
  • sort_and_insert(stack, temp)
  • push(stack, temp2)


@@coding::2@@



Test case :


  • Input: 10 2 1 6 19
  • Output: 19 10 6 2 1


Recommended Programs








c