Recursion: You are given a stack, reverse it using recursion

Problem Statement:

You are given a stack, you need to reverse it using recursion.

You are allowed to use all the stack operation

Example:

Input: s = [1, 2, 3, 4]

Output: s = [4, 3, 2, 1]

Solution Explanation:

We will use recursion to solve the problem.

Keep removing the elements till the stack is empty.

Create a helper function “insertAtBottom” to insert the value at the bottom of the stack.

When you remove the element from the stack, push the element into the helper function.

Then recursively insert all the elements at the bottom and then pop the elements into the stack

Time Complexity: O(n*n)
Space Complexity: O(n)

Code Solution

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;

void insertAtBottom(stack<int> &st, int x) 
{
    
    if (st.empty()) 
    {
        st.push(x);
        return;
    }

    int top = st.top();
    st.pop();

    insertAtBottom(st, x);

    st.push(top);
}

void reverseStack(stack<int> &st) 
{
    
    if (st.empty()) return;

    int top = st.top();
    st.pop();

    reverseStack(st);

    insertAtBottom(st, top);
}

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

    reverseStack(st);

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

    return 0;
}

Output

1 2 3 4