Stack: Sort a stack using a temporary stack

You are given integers in a stack.

You need to sort it in ascending order using another stack.

Input: [5, 3, 4, 2, 1]
Output: [1, 2, 3, 4, 5] 

Take a temp stack “tempStack”

Till the input stack is not empty,

1. Pop the element from the input stack and name it as temp_ele.

2. Till the temo stack is not empty, and top of the tempStack is less than original stack, pop from the tempStack and push into the input stack.

3. Push temp_ele into the tempStack

Time Complexity: O(n*n)

Space Complexity: O(n)

#include <iostream> 
#include <stack> 
#include <queue> 

using namespace std;

stack<int> solution(stack<int> &input)
{
    stack<int> tempStack;

    while (!input.empty())
    {
        int temp_elem = input.top();
        input.pop();

        while (!tempStack.empty() && tempStack.top() < temp_elem)
        {

            input.push(tempStack.top());
            tempStack.pop();
        }

        tempStack.push(temp_elem);
    }

    return tempStack;
}

int main()
{
    stack<int> input;
    input.push(5);
    input.push(4);
    input.push(3);
    input.push(2);
    input.push(1);

    
    stack<int> tempStack = solution(input);


    while (!tempStack.empty())
    {
        cout << tempStack.top()<< " ";
        tempStack.pop();
    }
}

Output

1 2 3 4 5