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.

## 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.

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