Question

Java Data Structures (Stack and Recursion)

Using the CODE provided BELOW (WITHOUT IMPORTING any classes from Java Library) modify the classes and add the following methods to the code provided below.

1. Add a recursive method hmTimes() to the CODE BELOW that states how many times a particular value appears on the stack.

2. Add a recursive method insertE() to the CODE BELOW that allows insert a value at the end of the stack.

3. Add a recursive method popLast() to the CODE BELOW that allows removal of the last node from the stack.

4. Add a recursive method hmNodes() to CODE BELOW that states how many nodes does the stack have.

Prove that every method works, MULTIPLE TIMES, in the MAIN StackWithLinkedList2.

CODE:

class Node {

  int value;

  Node nextNode;

  

  Node(int v, Node n)

  {

    value = v;

nextNode = n;

  }

  

  Node (int v)

  {

     this(v,null);

  }

}

class Stack {

  protected Node top;

  

  Stack()

  {

    top = null;

  }

  

  boolean isEmpty()

  {

    return( top == null);

  }

  void push(int v)

  {

    Node tempPointer;

    tempPointer = new Node(v);

tempPointer.nextNode = top;

top = tempPointer;

  }

  

  int pop()

  {

    int tempValue;

tempValue = top.value;

top = top.nextNode;

return tempValue;

  }   

  

  void printStack()

  {

    Node aPointer = top;

String tempString = "";

while (aPointer != null)

{

tempString = tempString + aPointer.value + "\n";

aPointer = aPointer.nextNode;

}

System.out.println(tempString);

  }

  

  boolean hasValue(int v)

  {

    if (top.value == v)

{

return true;

}

else

{

return hasValueSubList(top,v);

}

  }

  

  boolean hasValueSubList(Node ptr, int v)

  {

    if (ptr.nextNode == null)

{

return false;

}

else if (ptr.nextNode.value == v)

{

return true;

}

else

{

return hasValueSubList(ptr.nextNode,v);

}

  }

}

public class StackWithLinkedList2{

  public static void main(String[] args){

    int popValue;

    Stack myStack = new Stack();

myStack.push(5);

myStack.push(7);

myStack.push(9);

    System.out.println(myStack.hasValue(11));

  }

}

Answer 1

Recursion is the concept of forming a loop using a call of function within its own function body.

as we are calling a function again and again in its body it forms a loop and a memory stack as we use that function.

the code and solutioin that is asked in the question is provided below and is teested with several test cases

CODE:

class Node {

    int value;

    Node nextNode;



    Node(int v, Node n)
    {
        value = v;
        nextNode = n;
    }



    Node(int v)
    {
        this(v, null);
    }
}

class Stack {
    protected Node top;

    Stack()
    {
        top = null;
    }



    boolean isEmpty()
    {
        return (top == null);
    }

    void push(int v)
    {
        Node tempPointer;
        tempPointer = new Node(v);
        tempPointer.nextNode = top;
        top = tempPointer;
    }



    int pop()
    {
        int tempValue;
        tempValue = top.value;
        top = top.nextNode;
        return tempValue;
    }



    void printStack()
    {
        Node aPointer = top;
        String tempString = "";
        while (aPointer != null)
        {
            tempString = tempString + aPointer.value + "\n";
            aPointer = aPointer.nextNode;
        }
        System.out.println(tempString);
    }
    void hmNodes(){
        coutt(top,0);
    }
    void coutt(Node ptr,int cout){
        if (ptr.nextNode==null){
            System.out.println("the number of elements in stack are "+ cout);
            return;
        }
        cout++;
        coutt(ptr.nextNode,cout);
    }
    void popLast(){
        poped(top);
    }
    void poped(Node ptr){
        if (ptr.nextNode.nextNode==null){
            System.out.println(ptr.nextNode.value+"is the poped element from last");
            ptr.nextNode=null;
            return;
        }
        poped(ptr.nextNode);
    }
    void insertE(int val)
    {
        insertatend(top,val);
    }
    
    void insertatend(Node tra,int val){
        
        if(tra.nextNode==null){
            tra.nextNode=new Node(val);
            return;
        }
        insertatend(tra.nextNode,val);
    }
    
    void hmTimes(int val){
        int count = TIMES(top,val,0);
        System.out.println("the value "+val+" is present "+count+" times in stack");
    }
    
    int TIMES(Node ptr, int vall,int coun)
    {
        if(ptr.value==vall){
            coun++;
        }
        if (ptr.nextNode==null){
            return coun;
        }
        return TIMES(ptr.nextNode,vall,coun);
    }
    
    boolean hasValue(int v)
    {
        if (top.value == v)
        {
            return true;
        } 
        else
        {
            return hasValueSubList(top, v);
        }
    }


    boolean hasValueSubList(Node ptr, int v)
    {
        if (ptr.nextNode == null)
        {
            return false;
        } 
        else if (ptr.nextNode.value == v)
        {
            return true;
        } 
        else
        {
            return hasValueSubList(ptr.nextNode, v);
        }

    }

}

public class StackWithLinkedList2 {

    public static void main(String[] args) {

        int popValue;

        Stack myStack = new Stack();

        myStack.push(5);
        myStack.push(5);
        myStack.push(7);
        myStack.push(5);
        myStack.push(9);
        myStack.push(7);
        myStack.push(5);
        myStack.push(7);
        myStack.push(5);
        myStack.push(7);
        myStack.push(5);
        myStack.push(7);
        myStack.insertE(8);
        myStack.hmNodes();
        myStack.insertE(8);
        myStack.hmNodes();
        myStack.insertE(8);
        myStack.hmNodes();
        myStack.insertE(8);
        myStack.hmNodes();
        myStack.insertE(8);
        myStack.hmNodes();
        myStack.hmTimes(8);
        myStack.popLast();
        myStack.hmTimes(8);
        myStack.hmNodes();
    }

}

OUTPUT: