# Reverse a Stack Using Recursion

Difficulty Level Easy
Recursion StackViews 1734

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.

Translate »