Java Program to Reverse a Stack Using Recursion

In this article we are going to see how we can reverse a stack using recursion by Java programming language.

Java Program to Reverse a Stack Using Recursion

Stack is a linear data structure which works on the principle of Last In First Out(LIFO). As per the problem statement we have to reverse all the elements of a stack.

Let’s see the program to understand it clearly.

Method-1: Java Program to Reverse a Stack Using Recursion By Using Static Input Value

Approach:

  • Create an empty stack.
  • Push some elements onto the stack.
  • Print the original stack.
  • Call the user defined method rev( ) to reverse the stack. It runs a while loop and pushes the elements from top to the bottom using another method which uses recursion to contain the elements and push them.
  • Print the reversed stack.

Program:

import java.util.*;
// Main class
public class Main
{
    // Create a stack to operate on
    static Stack<Character> st = new Stack<>();
    // Recursive function to insert the element at bottom
    static void insertBottom(char x)
    {
        // Checks if stack is empty then pushes the element
        if(st.isEmpty())
            st.push(x);
        // If stack is not empty then holds all elements in the instances of recursive calls
        // until the end of the stack is reached
        else
        {
            char a = st.peek();
            st.pop();
            insertBottom(x);
            //once item is inserted at bottom push all other elements
            st.push(a);
        }
    }
    
    // Method to reverse the stack
    public static void rev()
    {
        if(st.size() > 0)
        {
            // contain all elements until we reach the end of the stack then push
            char x = st.peek();
            st.pop();
            rev();
            // push the item at bottom
            insertBottom(x);
        }
    }

    public static void main(String[] args)
    {
        // Static initialisation of elements to the stack
        st.push('1');
        st.push('2');
        st.push('5');
        st.push('6');
        st.push('9');
        st.push('0');
        // Print the original stack
        System.out.println("Original Stack");
        System.out.println(st);
        // call the reverse method to reverse the stack
        rev();
        // Print the reversed stack
        System.out.println("Reversed Stack");
        System.out.println(st);
    }
}
Output:

Original Stack
[1, 2, 5, 6, 9, 0]
Reversed Stack
[0, 9, 6, 5, 2, 1]

Method-2: Java Program to Reverse a Stack Using Recursion By Using User Input Value

Approach:

  • Create an empty stack.
  • Ask the user to enter the number of elements.
  • Use a for loops to store and push the elements to the stack.
  • Print the original stack.
  • Call the user defined method rev( ) to reverse the stack. It runs a while loop and pushes the elements from top to the bottom using another method which uses recursion to contain the elements and push them.
  • Print the reversed stack.

Program:

import java.util.*;
// Main class
public class Main
{
    // Create a stack to operate on
    static Stack<Character> st = new Stack<>();
    // Recursive function to insert the element at bottom
    static void insertBottom(char x)
    {
        // Checks if stack is empty then pushes the element
        if(st.isEmpty())
            st.push(x);
        // If stack is not empty then holds all elements in the instances of recursive calls
        // until the end of the stack is reached
        else
        {
            char a = st.peek();
            st.pop();
            insertBottom(x);
            //once item is inserted at bottom push all other elements
            st.push(a);
        }
    }
    
    // Method to reverse the stack
    public static void rev()
    {
        if(st.size() > 0)
        {
            // contain all elements until we reach the end of the stack then push
            char x = st.peek();
            st.pop();
            rev();
            // push the item at bottom
            insertBottom(x);
        }
    }

    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        // Asks the user for input
        System.out.println("How many elements you want to enter ?");
        int num = sc.nextInt();
        char ch;
        // Ask the user to enter the elements and push them onto the stack
        for(int i = 0; i < num; i++)
        {
            System.out.println("Enter "+(i+1)+"th element!");
            ch = sc.next().charAt(0);
            st.push(ch);
        }
        // Print the original stack
        System.out.println("Original Stack");
        System.out.println(st);
        // call the reverse method to reverse the stack
        rev();
        // Print the reversed stack
        System.out.println("Reversed Stack");
        System.out.println(st);
    }
}
Output:

How many elements you want to enter ?
3
Enter 1th element!
A
Enter 2th element!
B
Enter 3th element!
C
Original Stack
[A, B, C]
Reversed Stack
[C, B, A]

Don’t miss the chance of Java programs examples with output pdf free download as it is very essential for all beginners to experienced programmers for cracking the interviews.

Leave a Comment