Reverse a Stack Using Recursion

In reverse a stack using recursion problem, we have given a stack data structure. Reverse its elements using recursion. Only the below-listed functions of the stack can be used –

• push(element) – to insert the element in the stack.
• pop() – to remove/delete the element at the top of the stack.
• isEmpty() – to check if there is any element in the stack or not.

Example

Input : 5 4 3 2 1

Output : 1 2 3 4 5

Input : 300 200 100

Output : 100 200 300

Method

Create the stack and two functions. First bottom_insert() to insert the elements at the bottom of the stack and another one reverse() to pop all the elements and call for bottom_insert() which will result in the reversed stack.

Algorithm for Reverse a Stack Using Recursion

1. Initialize a stack and push elements in it.
2. Create a function to insert the elements at the bottom of the stack which accepts an element as a parameter. Check if the size of the stack is equal to 0, push the element in the stack.
3. Else create a variable a and store the top of the stack in it. Pop the top of the stack and make the recursive call to the function itself. Push the variable a in the stack.
4. Similarly, create a function reverse(). Check if the size of the stack is greater than 0, create a variable x, and store the top of the stack in it. Pop the top of the stack. Make a recursive call to the function itself. Call the function to insert the elements at the bottom of the stack.
5. Call the reverse function in the main(). Initialize a string.
6. Traverse while the stack is not empty, create a variable p and store the top of the stack in it. Pop the top of the stack. Add the popped element in the string.
7. Print the string.

C++ Program to Reverse a Stack Using Recursion

#include<bits/stdc++.h> 
using namespace std; 
  
stack<char> st; 
  
string s; 
  
char bottom_insert(char x){ 
  
    if(st.size() == 0){ 
        st.push(x); 
    }
  
    else{ 
        char a = st.top(); 
        st.pop(); 
        bottom_insert(x); 
  
        st.push(a); 
    } 
} 
  
char reverse(){ 
    
    if(st.size()>0){ 
        char x = st.top(); 
        st.pop(); 
        reverse(); 
          
        bottom_insert(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; 
}

[5, 4, 3, 2, 1]

Java Program to Reverse a Stack Using Recursion

import java.util.Stack; 
  
class ReverseStack{ 
      
    static Stack<Character> st = new Stack<>(); 
      
    static void bottom_insert(char x){ 
  
        if(st.isEmpty()){ 
            st.push(x); 
        }    
  
        else{ 
            char a = st.peek(); 
            st.pop(); 
            bottom_insert(x); 
  
            st.push(a); 
        } 
    } 
      
    static void reverse(){
        
        if(st.size() > 0){ 
              
            char x = st.peek(); 
            st.pop(); 
            reverse(); 
              
            bottom_insert(x); 
        } 
    } 
      
    public static void main(String[] args){ 
          
        st.push('1'); 
        st.push('2'); 
        st.push('3'); 
        st.push('4'); 
        st.push('5'); 
          
        reverse(); 
        
        System.out.print(st);
        
    } 
}

[5, 4, 3, 2, 1]

Complexity Analysis

Time Complexity: O(n*n) where n is the number of elements pushed in the stack.

Auxiliary Space: O(n*n) because we are using n*n extra stack space.

Reference1   references2