Learning To Reverse A Stack Using Recursion

A stack is a data structure based on the concept of last-in, first-out(LIFO). The last inserted element is the first to get removed from the Stack. In this blog, we will be looking at a demonstration of how to reverse a stack using recursion.

To reverse a Stack, we will have to use the following functions,

  • isEmpty(stack);
  • pop(stack);
  • push(stack);

There are multiple ways to reverse a Stack, and we will look at two of them here,

  • Reverse a Stack using non-recursion.
  • Reverse a Stack using recursion.

Using Non-Recursive Function

The best approach to revers a Stack is by removing the elements from the Stack one after another and inserting them into another stack. Since stacks are based on LIFO, the last element will be removed first. To reverse a Stack, we will use the pop function to remove the element from the Stack, the push element to push the elements in the Stack, and the isEmpty function to check whether the Stack is empty or not. For example, the structure to reverse a Stack would look like this,

 

1 <- top

2

3

4

 

Stack 1 Stack 2

2 <- top 1 <- top

3

4

 

Stack 1 Stack 2

3 <- top 2 <- top

4 1

 

Stack 1 Stack 2

4 <- top 3 <- top

2

1

 

Stack 1 Stack 2

4 <- top

3

2

1

 

As observed, we can quickly reverse a Stack using recursion which is mentioned above.

Let us look at the code for the scenario to reverse the Stack.

import java.io.*;

import java.util.*;

class solution{

static void stackReverse(Stack st){

Stack<Integer> st1 = new Stack<Integer>();

while(!st.isEmpty()){

int elm = (int)st.pop();

st1.push(elm);

}

System.out.println(“nnReversed Stack: “);

System.out.println(st1);

}

public static void main(String args[]){

Stack<Integer> st = new Stack<Integer>();

st.push(1);

        st.push(2);

        st.push(3);

        st.push(4);

        System.out.println(“nnOriginal Stack: “);

        System.out.println(st);

        stackReverse(st);

}

}

In the above example, we pass the original Stack to the reverseStack() function to reverse a Stack. The time complexity in this scenario is O(n), where n is the number of elements in the Stack.

 

Using Recursive Function

Recursion can be defined as a process in which a function calls itself directly or indirectly. In this section, we will reverse a Stack using recursion. The idea behind using this approach is to keep the values of the Stack in a Function until the Stack becomes empty. Once the Stack is empty, we insert the values one after another. Let us look at the code to reverse a Stack using recursion,

import java.util.*;

class Test {

static Stack<Character> st = new Stack<>();

static void insertAtBottom(char x){

if(st.isEmpty())

st.push(x);

else{

char a = st.peek();

st.pop();

insertAtBottom(x);

st.push(a);

}

}

static void reverseStack()

{

if(st.size() > 0){

char x = st.peek();

st.pop();

reverseStack();

insertAtBottom(x);

}

}

public static void main(String[] args)

{

st.push(‘1’);

st.push(‘2’);

st.push(‘3’);

st.push(‘4’);

System.out.println(“nnOriginal Stack”);

System.out.println(st);

reverseStack();

System.out.println(“nnReversed Stack”);

System.out.println(st);

}

}

The time complexity in this scenario is O(n^2), where n is the number of elements in the Stack.

Related Articles

Responses