Question

1. a) Write two algorithms of different time complexity implemented in Java methods in complete Java program to reverse a stack of characters. Make your own assumption and your own design on the methods signature, inputs, outputs, and the full main program.

Answer 1

___________________________________________________________________

/* Java program to reverse a stack of characters*/

/* import packeges and necessary classs */
import java.lang.*;
import java.util.Scanner;

/* Java class to reverse a stack using two stack*/
public class Main {

    /* stacks are declared globally */
    char[] stack1 = new char[50];
    char[] stack2 = new char[50];
    int top1;
    int top2;

    public void display(int stackIndex) {
        /* 
                Method for displaying stack
                @Param: Index of stack   
                Return:     
        */
        /* declare variable(s) */
        int i;

        if (stackIndex == 1) {
            /* show stack1 */
            System.out.println("\nStack 1:");
            i = top1;
            if (i > -1) {
                System.out.println(stack1[i] + "   <-- top");
                for (i = top1 - 1; i >= 0; i--) {
                    System.out.println(stack1[i]);
                }
            }
        } else {
            /* show stack2 */
            System.out.println("\nStack 2:");
            i = top2;
            if (i > -1) {
                System.out.println(stack2[i] + "   <-- top");
                for (i = top2 - 1; i >= 0; i--) {
                    System.out.println(stack2[i]);
                }
            }
        }
    }

    public char pop(int stackIndex) {
        /* 
                Method for popping items from stack1/sttack 2
                @Param: stack index    
                Return:     
        */
        /* return top of first stack */
        if (stackIndex == 1) {
            top1--;
            return (stack1[top1 + 1]);
        }
        /* return top of second stack */
        else
            top2--;

        /* return */
        return (stack2[top2 + 1]);
    }


    public void push(int stackIndex, char item) {
        /* 
                Method for pushing items to stack1/stack2
                @Param: The stack index and top value     
                Return:     
        */
        if (stackIndex == 1) {
            /* increase top1 */
            top1++;
            /* insert element */
            stack1[top1] = item;
        } else {
            /* increase top2 */
            top2++;
            /* insert element */
            stack2[top2] = item;
        }
    }

    /* Driver method */
    public static void main(String[] args) {
        /* declare object(s) */
        Main obj = new Main();
        Scanner sc = new Scanner(System.in);

        /* declare variable(s) */
        int i, max_size;
        char item;

        /* Take input(s) */
        System.out.print("\nEnter the no of items for stack: ");
        max_size = sc.nextInt();

        /* keep pushing element in stack 1*/
        i = 0;
        obj.top1 = -1;
        System.out.println("Pushing items to Stack 1:");
        while (i < max_size) {
            /* enter items */
            System.out.print("\nEnter item: ");
            item = sc.next().charAt(0);

            /* push */
            obj.push(1, item);

            /* show stack */
            obj.display(1);

            /* increment */
            i++;

            /* new line */
            System.out.print("\n**************\n");
        }



        /* Now pop stack1 and push items in stack2 */
        i = 0;
        obj.top2 = -1;
        System.out.println("\n\nPop items from Stack 1 and push to Stack 2:");
        while (i < max_size) {
            /* pop items */
            item = obj.pop(1);

            /* show stack1 */
            obj.display(1);

            /* push item to stack 2 */
            obj.push(2, item);

            /* show stack 2 */
            obj.display(2);

            /* increment */
            i++;

            /* new line */
            System.out.print("\n**************\n");
        }

        /* stack 1 from top */
        System.out.print("Stack 1:");
        for (i = max_size - 1; i >= 0; i--)
            System.out.print(obj.stack1[i] + " ");
        System.out.print("\n\n");

        /* stack 2 from top */
        System.out.print("Stack 2:");
        for (i = max_size - 1; i >= 0; i--)
            System.out.print(obj.stack2[i] + " ");
        System.out.print("\n\n");
    }
}

___________________________________________________________________

___________________________________________________________________

Enter the no of items for stack: 5
Pushing items to Stack 1:

Enter item: A

Stack 1:
A   <-- top

**************

Enter item: B

Stack 1:
B   <-- top
A

**************

Enter item: C

Stack 1:
C   <-- top
B
A

**************

Enter item: D

Stack 1:
D   <-- top
C
B
A

**************

Enter item: E

Stack 1:
E   <-- top
D
C
B
A

**************


Pop items from Stack 1 and push to Stack 2:

Stack 1:
D   <-- top
C
B
A

Stack 2:
E   <-- top

**************

Stack 1:
C   <-- top
B
A

Stack 2:
D   <-- top
E

**************

Stack 1:
B   <-- top
A

Stack 2:
C   <-- top
D
E

**************

Stack 1:
A   <-- top

Stack 2:
B   <-- top
C
D
E

**************

Stack 1:

Stack 2:
A   <-- top
B
C
D
E

**************
Stack 1:E D C B A

Stack 2:A B C D E

___________________________________________________________________

___________________________________________________________________

___________________________________________________________________

/* Java program to reverse a stack of characters*/

/* import packeges and necessary classs */
import java.lang.*;
import java.util.Scanner;

/* Java class to reverse a stack using recursion*/
public class Main {

    /* stacks are declared globally */
    char[] stack = new char[50];
    int top;
    int MAX = 50;

    public void display() {
        /* 
                Method for displaying stack
                @Param:     
                Return:     
        */
        /* declare variable */
        char item;

        /* if stack is not empty */
        if (!isStackEmpty()) {
            item = pop();
            display();
            System.out.print(" " + item);
            push(item);
        }
    }

    public void init() {
        /* 
                Method for initialize top
                @Param:     
                Return:     
        */
        top = -1;
    }

    public boolean isStackFull() {
        /* 
                Method to check if stack is full or not
                @Param:     
                Return: True/ False    
        */
        /* return */
        return (top >= MAX - 1) ? true : false;
    }

    public boolean isStackEmpty() {
        /* 
                Method to check if stack is empty or not
                @Param:     
                Return: True/ False    
        */
        /* return */
        return (top == -1) ? true : false;
    }

    public void push(char item) {
        /* 
                Method to push into stack
                @Param: Character items     
                Return:  
        */
        if (isStackFull())
            System.out.print("The stack is full\n");
        else
            stack[++top] = item;
    }


    public char pop() {
        /* 
                Method to pop from stack
                @Param:     
                Return:  
        */
        /* if stack is empty */
        if (isStackEmpty())
            System.out.print("The stack is empty\n");
        /* if stack is not empty */

        return stack[top--];
    }

    public void bottomInsertion(char item) {
        /* 
                Method to insert items to bottom
                @Param: chatcater items    
                Return:  
        */
        /* declare variable */

        if (isStackEmpty())
            push(item);
        else {
            char temp = pop();
            bottomInsertion(item);
            push(temp);
        }
    }

    public void doReverse() {
        /* 
                Method to reverse the stack
                @Param:    
                Return:  
        */
        /* declare variables */
        char top;
        /* check if stack is empty or not */
        if (!isStackEmpty()) {
            top = pop();
            doReverse();

            bottomInsertion(top);
        }
    }

    public int findSize() {
        /* 
                Method to get the size of stack
                @Param:    
                Return: size of stack 
        */
        return (top + 1);
    }

    /* Driver method */
    public static void main(String[] args) {
        /* declare object(s) */
        Main obj = new Main();
        Scanner sc = new Scanner(System.in);

        /* Initialize the top of stack */
        obj.init();

        /* push elements to stack */
        obj.push('A');
        obj.push('B');
        obj.push('C');
        obj.push('D');
        obj.push('E');
        /* display initial stack */
        System.out.print("Stack: \n");
        obj.display();

        /* do reverse of stack */
        obj.doReverse();
        /* display reversed stack */
        System.out.print("\nReversed Stack:\n");
        obj.display();

    }
}

___________________________________________________________________

___________________________________________________________________

Stack:
 A B C D E
Reversed Stack:
 E D C B A

___________________________________________________________________

Note: If you have queries or confusion regarding this question, please leave a comment. I would be happy to help you. If you find it to be useful, please upvote.