Sort a stack

Problem Statement:

You are given a stack, you need to sort it.

Solution

This problem can be solved in 2 different methods:

1. Sorting using another stack

2. Sorting using recursion

1. Sorting using another stack

1. Create a temp stack.

2. Till the input stack is not empty repeat below steps:

3. Pop the element from the original stack and store the value

4. Till the temp_stack is not empty, and the top if temp_stack > temp_value, pop data from aux_stack and push to the input_stack.

5. Push temp value to temp_stack

6. Return temp_stack

2. Sorting using recursion

In this method we recursively call the stack and store the element in temp variable till stack becomes empty and while inserting the elements, we sort them and insert.

Solution in C++

#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <queue>
#include <vector>
#include <stack> 

using namespace std;
  
stack<int> sort_stack_using_another_stack(stack<int> &input) 
{ 
    stack<int> temp_stack; 
  
    while (!input.empty()) 
    { 
        int temp_val = input.top(); 
        input.pop(); 

        while (!temp_stack.empty() && temp_stack.top() > temp_val) 
        { 

            input.push(temp_stack.top()); 
            temp_stack.pop(); 
        } 
  
        temp_stack.push(temp_val); 
    } 
  
    return temp_stack; 
} 

void sort_and_insert(stack<int> &stack, int key)
{

    if (stack.empty() || key > stack.top())
    {
        stack.push(key);
        return;
    }
  
    int top = stack.top();
    stack.pop();
 
    sort_and_insert(stack, key);
 
    stack.push(top);
}

void sort_stack_using_recursion(stack<int> &stack)
{
    if (stack.empty()) 
    {
        return;
    }
 
    int top = stack.top();
    stack.pop();
 
    sort_stack_using_recursion(stack);
 
    sort_and_insert(stack, top);
}

int main() 
{ 
    stack<int> input; 
    input.push(10); 
    input.push(2); 
    input.push(3); 
    input.push(40); 
    input.push(5); 
  
    stack<int> temp_stack = sort_stack_using_another_stack(input); 
    cout << "Sorted stack using another stack are:\n"; 
  
    while (!temp_stack.empty()) 
    { 
        cout << temp_stack.top()<< " "; 
        temp_stack.pop(); 
    } 

    input.push(10); 
    input.push(2); 
    input.push(3); 
    input.push(40); 
    input.push(5);   

    sort_stack_using_recursion(input); 
    cout << "\nSorted stack using recursion stack are:\n"; 
  
    while (!input.empty()) 
    { 
        cout << input.top()<< " "; 
        input.pop(); 
    }
    cout<<endl; 
}

Output:

Sorted stack using another stack are:
40 10 5 3 2
Sorted stack using recursion stack are:
40 10 5 3 2