Question

Java Language

Add a recursive method to the program shown in the previous section that allows
insert a value at the end of the stack.

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 is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. If not, PLEASE let me know before you rate, I’ll help you fix whatever issues. Thanks

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

        // method to insert a value at the end of the stack
        void insertEnd(int v) {
                // if stack is empty, adding v as the top node
                if (isEmpty()) {
                        top = new Node(v);
                } else {
                        // else, calling the private recursive method, passing top node and
                        // v
                        insertEnd(top, v);
                }
        }

        // private helper method to assist the above method. this is where the
        // actual recursion takes place
        private void insertEnd(Node n, int v) {
                // if n is the last node (no next node), adding a new node after n, with
                // value v
                if (n.nextNode == null) {
                        n.nextNode = new Node(v);
                } else {
                        // otherwise calling method recursively, passing next node
                        insertEnd(n.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);
                // printing stack
                myStack.printStack();
                // adding 11 to the end
                myStack.insertEnd(11);
                // printing stack again
                myStack.printStack();
        }
}

/*OUTPUT*/

9
7
5

9
7
5
11