Sort a stack using a temporary stack  

Difficulty Level Medium
Frequently asked in Amazon Goldman Sachs IBM Kuliza Yahoo
Sorting Stack

Problem Statement  

The problem “Sort a stack using a temporary stack” states that you are given a stack data structure. Sort the elements of the given stack using a temporary stack.

Sort a stack using a temporary stackPin

Example  

9 4 2 -1 6 20
20 9 6 4 2 -1
2 1 4 3 6 5
6 5 4 3 2 1

For instance

Let Stack = [9 4 2 -1 6 20] and Temporary stack = []

Please click Like if you loved this article?

Steps for sorting -
1.Top of stack = 20
Stack = [9 4 2 -1 6]
Temporary stack = [20]

2. Top of stack = 6
Stack = [9 4 2 -1 20]
Temporary stack = [6]

3. Top of stack = 20
Stack = [9 4 2 -1]
Temporary stack = [6 20]

4. Top of stack = -1
Stack = [9 4 2 20 6]
Temporary stack = [-1]

5. Top of stack = 6
Stack = [9 4 2 20]
Temporary stack = [-1 6]

6. Top of stack = 20
Stack = [9 4 2]
Temporary stack = [-1 6 20]

7. Top of stack = 2
Stack = [9 4 20 6]
Temporary stack = [-1 2]

8. Top of stack = 6
Stack = [9 4 20]
Temporary stack = [-1 2 6]

9. Top of stack = 20
Stack = [9 4]
Temporary stack = [-1 2 6 20]

10. Top of stack = 4
Stack = [9 20 6]
Temporary stack = [-1 2 4]

11. Top of stack = 6
Stack = [9 20]
Temporary stack = [-1 2 4 6]

12. Top of stack = 20
Stack = [9]
Temporary stack = [-1 2 4 6 20]

13. Top of stack = 9
Stack = [20]
Temporary stack = [-1 2 4 6 9]

14. Top of stack = 20
Stack = []
Temporary stack = [-1 2 4 6 9 20]

As the Stack is empty and the temporary stack is in sorted, print the temporary stack starting from it’s top.

See also
Dijkstra Algorithm

Therefore, Output : 20 9 6 4 2 -1

Algorithm to Sort a stack using a temporary stack  

  1. Initialize a stack data structure and insert/push the elements in it.
  2. After that create a function sort() which accepts a stack as it’s parameter. Initialize another temporary/auxiliary stack tmpStack in it.
  3. Traverse while the original stack is not empty, create a variable tmp and store the top of the original stack in it. After that pop the top of the original stack.
  4. Again Traverse while tmpStack is not empty and the top of the tmpStack i.e. the temporary stack is greater not less than or equal to the variable tmp, push the top of the temporary stack in the original stack and pop the top of the temporary stack.
  5. Push variable tmp in the temporary stack.
  6. While the temporary stack is not empty, print it’s top and pop it’s top.

Code  

C++ Program to sort a stack using recursion

#include <iostream> 
#include <stack>
using namespace std; 
  
stack<int> sort(stack<int> &input){ 
    stack<int> tmpStack; 
  
    while(!input.empty()){ 
        
        int tmp = input.top(); 
        input.pop(); 
  
        while(!tmpStack.empty() && tmpStack.top() > tmp){ 
            input.push(tmpStack.top()); 
            tmpStack.pop(); 
        } 
  
        tmpStack.push(tmp); 
    } 
  
    return tmpStack; 
} 
  
int main(){ 
    stack<int> input; 
    
    input.push(20); 
    input.push(6); 
    input.push(-1); 
    input.push(2); 
    input.push(4); 
    input.push(9); 
  
    stack<int> tmpStack = sort(input); 
    
    while (!tmpStack.empty()){ 
        cout << tmpStack.top()<< " "; 
        tmpStack.pop(); 
    } 
}
20 9 6 4 2 -1

Java Program to sort a stack using recursion

import java.util.*; 
  
class SortStack{ 
    
    public static Stack<Integer> sort(Stack<Integer> input){
        
        Stack<Integer> tmpStack = new Stack<Integer>(); 
        
        while(!input.isEmpty()){ 
            int tmp = input.pop(); 
          
            while(!tmpStack.isEmpty() && tmpStack.peek() > tmp){ 
                input.push(tmpStack.pop()); 
            } 
              
            tmpStack.push(tmp); 
        } 
        return tmpStack; 
    } 
      
    public static void main(String args[]){
        
        Stack<Integer> input = new Stack<Integer>(); 
        
        input.add(20); 
        input.add(6); 
        input.add(-1); 
        input.add(2); 
        input.add(4); 
        input.add(9); 
      
        Stack<Integer> tmpStack=sort(input); 
        
        while (!tmpStack.empty()){ 
            System.out.print(tmpStack.pop()+" "); 
        }  
    } 
}
20 9 6 4 2 -1

Complexity Analysis  

Time Complexity

O(n^2) where n is the number of elements in the stack. Since we are pushing the elements back from the temporary stack to the original stack in case the top of the temporary stack is lesser than the element to be pushed. For better understanding, consider a descending order sequence and try to run the algorithm.

See also
Height of a generic tree from parent array

Space Complexity

O(n) because we used temporary stack space for n elements. The space used by the original stack is not counted for the algorithm.

Please click Like if you loved this article?