Stack: Reverse a stack using recursion

Problem Statement:

You are given a stack, you need to reverse the stack without using while, for.

You need to reverse using recursion.

Solution

The solution is very simple.

We will use 2 functions reverse and insert at bottom.

The reverse function will create a recursion to reverse the stack.

We pop the element from the stack and hold in a temp variable till we reach end of the stack.

Then we call insert at bottom function to insert the element at the bottom.

Example:

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<char> st; 
  
//to store the result of reverse stack elements
string s; 
  
char insert_at_bottom(char x)
{ 
  
    if(st.size() == 0)
    { 
        st.push(x); 
    }
  
    else
    { 
        char a = st.top(); 
        st.pop(); 
        insert_at_bottom(x); 
  
        st.push(a); 
    } 
} 
  
char reverse()
{ 
    
    if(st.size()>0)
    { 
        char x = st.top(); 
        st.pop(); 
        reverse(); 
          
        insert_at_bottom(x); 
    } 
} 
  
int main()
{ 
      
    st.push('1'); 
    st.push('2'); 
    st.push('3'); 
    st.push('4');
    st.push('5');
      
    reverse(); 
    
    while(!st.empty())
    { 
        char p=st.top(); 
        st.pop(); 
        s+=p; 
    } 
    
    cout<<"[";
    for(int i=s.size()-1; i>=0; i--){
        cout<<s[i]<<", ";
    }
    cout<<"]";
    return 0; 
}

Output:

[5, 4, 3, 2, 1, ]