Explore
ProGrad Programs
Placement Prep
TCS Codevita
Live Placement Training
Live Aptitude Training
Live Programming Training
Webinars
About Us

Edit
Reply




Edit

Sort a stack using temporary stack and recursion

Published on 28 Feb 2019

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.


C++

Output
Input- Enter the number of elements to be pushed to the stack: 5 Enter the stack elements:19 7 2 6 4 Output- Sorted Stack :19 7 6 4 2


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)


C
C++

Output
Input- Enter the number of elements to be pushed to the stack: 5 Enter the stack elements:19 7 2 6 4 Output- Sorted Stack :19 7 6 4 2


Test case :


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


´╗┐Recommended Programs





If you have any feedback about this article and want to improve this, please write to enquiry@faceprep.in