Question

Java Language

Add a recursive method to the program shown in the previous section that states
how many nodes does the stack have.

Code:

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);

}

}

}

class Node {

int value;

Node nextNode;

Node(int v, Node n) {

value = v;

nextNode = n;

}

Node (int v) {

this(v,null);

}

}

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));

}

}

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

}

}

Answer 1

Here we have implemented a recursive function to count the number of elements/nodes in the stack. We have passed the top node as parameter in calling the function and funtion calls itself again untill the we reach null.

The complete code is:

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);

        }
    }
    // implementation of count_nodes
    int count_nodes(Node n){
        //Terminating case 
        if (n==null)
            return 0;
        //normal case recursive call the function
        return (1 + count_nodes(n.nextNode));
    }

}


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));
        System.out.println(myStack.count_nodes(myStack.top));
        
    }
}

Output: