Question

Write a RECURSIVE algorithm (different from the ones your provided in 3) implemented in Java a in a complete Java program to reverse a stack of characters using recursion. You are not allowed to use loop constructs like while, for..etc, and you can only use the following functions on Stack S shown below (15pts)

Provide an explanation of the running time.

You will need to implement your own stack if needed

isEmpty(S)

push(S)

pop(S)

Make your own assumption and your own OOP design on the method(s) signature, inputs, outputs, and the full main program.

Answer 1

import java.util.Stack;
 
class Test {
     
    //  I am using Stack class for implementation of the stacks

    static Stack<Character> s = new Stack<>(); // making an object "s" of stack class.

    // the idea is to write a recursive function insertAtEnd that insert the 
    //topmost element at the end or the bottom-most end of the stack
    
    static void insertAtEnd(char x)
    {
 
        if(s.isEmpty())
            s.push(x);
 
        else
        {
            
            //all the elements are stored in a stack of the function call, until we 
            //reach the end of the Stack. if the stack becomes empty
            // i.e. the s.size() becomes zero, the above mentioned part(base condition) 
            //is executed and the element is inserted at the bottom


            char a = s.peek();         //store the topmost element
            s.pop();                   // remove the topmost element
            insertAtEnd(x);            //recursive call
                                        
            s.push(a);                 //Now we will push back all the elements 
                                       //that are stored in the function
                                       //call stack once the element is inserted at 
                                       //the end or the bottom of stack
        }
    }
     
     // now we will implement a function 
     //reverseStack() that reverses the
     //stack using insertAtEnd() function
   
    static void reverseStack()
    {
        if(s.size() > 0)
        {
             //all the elements are stored in a stack of the 
             //function call until we reach the end of the stack
            
            char x = s.peek();//store the topmost element
            s.pop();          // remove the topmost element
            reverseStack();   // recursive call to the function 
                              //again to reverse the remaining elements
             
            // insert back all the elements stored in the
            //function call, from bottom to the top. Every 
            //element inserted at the end by using the function
            // insertAtEnd()
          
            insertAtEnd(x);
        }
    }
     
    //  Code to check the working of the functions made
    public static void main(String[] args) 
    {
         
        //pushing elements in stack
        s.push('A');
        s.push('B');
        s.push('C');
        s.push('D');
         
        System.out.println("Stack before the Reversal:");
         
        System.out.println(s);
         
        // calling the function to reverse the stack
        reverseStack();
         
        System.out.println("Stack after the Reversal:");
         
        System.out.println(s);
    }
}

I have mentioned all the necessary comments to explain each line of code.

This program takes the worst time complexity of O(n^2).

Explanation:

The idea is to store all values in the stack of the function call until the stack becomes empty or its size becomes zero.

Now, if the stack is empty, insert all stored items one by one at the bottom of the stack.

example:

let the input stack be:

[ E, F, G, H] where E is the topmost element.

so the approach is to insert the topmost element into the bottom of the stack:

• H is inserted at the bottom as the stack becomes empty and H is the topmost of the function call stack:
  • stack:{H(top)}
• G is inserted at the bottom as G is the topmost of the function call stack.
  • stack:{H(top),G}
• F is inserted at the bottom as F is the topmost of the function call stack.
  • stack:{H(top),G,F}
• E is inserted at the bottom as E is the topmost of the function call stack.
  • stack:{H(top),G,F,E}

the final REVERSED stack is :[ H, G, F, E,]