Question

Java Language

Add a recursive method to the program shown in the previous section that allows remove the last node from 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)); } }

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

Answer 1

Concept to Solve the problem of deleting the last node:

• Make the node (Second last node pointing to last node) point to null.
• then the Second last node will become the last node

Description:

The method to remove the last node from the stack is given below:

/**
         * This method will delete the last node from the stack
         * @param head : Starting of the head
         * @return : head of  the new list
         */
        public Node delete( Node head )
        {
                Node solution, smallerSol;

                /*** ============================
              Handle Base cases
              ============================ ***/
                
                /**Check if the head is null**/
                if ( head == null )           /**Base case 1**/
                {
                        solution = null;

                        return solution;
                }
                /**check if node's next node is null*/
                else if ( head.nextNode == null )  /** Base case 2**/
                {
                        solution = null;

                        return solution;
                }
                else
                {
                        /** =================================================
                   Assume that the list is not empty...
                    And "head.next" points to a SHORTER list !
                    ================================================= **/

                        /**
                         * recursive call to delete method
                         */
                        smallerSol = delete( head.nextNode ); /** Have someone else delete the last**/      
                        /** node in a SHORTER list and return
                         back the new list**/

                        head.nextNode = smallerSol;    /** Solve problem with smaller solution**/

                        solution = head;           /** Solution = list starting at head**/

                        return solution;           /** Return the head of the new list**/
                } 
        }

Complete Class:

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

                }

        }

        /**
         * This method will delete the last node from the stack
         * @param head : Starting of the head
         * @return : head of  the new list
         */
        public Node delete( Node head )
        {
                Node solution, smallerSol;

                /*** ============================
              Handle Base cases
              ============================ ***/
                
                /**Check if the head is null**/
                if ( head == null )           /**Base case 1**/
                {
                        solution = null;

                        return solution;
                }
                /**check if node's next node is null*/
                else if ( head.nextNode == null )  /** Base case 2**/
                {
                        solution = null;

                        return solution;
                }
                else
                {
                        /** =================================================
                   Assume that the list is not empty...
                    And "head.next" points to a SHORTER list !
                    ================================================= **/

                        /**
                         * recursive call to delete method
                         */
                        smallerSol = delete( head.nextNode ); /** Have someone else delete the last**/      
                        /** node in a SHORTER list and return
                         back the new list**/

                        head.nextNode = smallerSol;    /** Solve problem with smaller solution**/

                        solution = head;           /** Solution = list starting at head**/

                        return solution;           /** Return the head of the new list**/
                } 
        }

}

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();
                
                /** Add to stack */

                myStack.push(5);

                myStack.push(7);

                myStack.push(9);

                myStack.push(19);

                myStack.push(91);

                myStack.push(93);

                myStack.push(10);

                myStack.push(20);

                System.out.println("check if stack has value 11");
                System.out.println(myStack.hasValue(11));

                System.out.println("Print the stack");
                myStack.printStack();

                System.out.println("delete the last node from stack");
                myStack.delete(myStack.top);

                System.out.println("print the stack again");
                myStack.printStack();
                
                System.out.println("Push another item to stack");
                
                myStack.push(100);
                
                System.out.println("Print the stack again");
                myStack.printStack();

                System.out.println("delete the last node from stack");
                myStack.delete(myStack.top);

                System.out.println("Print the stack again");
                myStack.printStack();
        }

}

Console output of working of delete method to remove the last node: