Home » Technical Interview Questions » Stack Interview Questions » Reverse a Stack Using Recursion

Reverse a Stack Using Recursion


Difficulty Level Easy
Factset Fourkites Recursion Stack

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.

Reverse a Stack Using Recursion

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.
READ  Check if stack elements are pairwise consecutive

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

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions

AD Blocker Detected !

Advertisements help running this website for free.

To view the content please disable AdBlocker and refresh the page.

Wait !!! You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Abhishek

Abhishek was able to crack Microsoft after practicing questions from TutorialCup