 Explore
Placement Prep Edit 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  