Question

Write a java code for LinkedStack implementation and the code is:

public final class LinkedStack<T> implements StackInterface<T> {    private Node topNode; // References the first node in the chain       public LinkedStack()    {        topNode = null;    } // end default constructor       public void push(T newEntry)    { topNode = new Node(newEntry, topNode); //       Node newNode = new Node(newEntry, topNode); //       topNode = newNode;    } // end push    public T peek()    {        if (isEmpty())            throw new EmptyStackException();        else return topNode.getData();    } // end peek    public T pop()    {    T top = peek(); // Might throw EmptyStackException    assert (topNode != null); topNode = topNode.getNextNode();    return top;    } // end pop /* // Question 1, Chapter 6: Does not call peek    public T pop()    { if (isEmpty()) throw new EmptyStackException(); else        { assert (topNode != null);            top = topNode.getData();            topNode = topNode.getNextNode();        } // end if               return top;    } // end pop */          public boolean isEmpty()    {        return topNode == null;    } // end isEmpty       public void clear()    {        topNode = null; // Causes deallocation of nodes in the chain    } // end clear    private class Node    { private T data; // Entry in stack private Node next; // Link to next node private Node(T dataPortion) { this(dataPortion, null); } // end constructor private Node(T dataPortion, Node linkPortion) { data = dataPortion; next = linkPortion;   } // end constructor private T getData() { return data; } // end getData private void setData(T newData) { data = newData; } // end setData private Node getNextNode() { return next; } // end getNextNode private void setNextNode(Node nextNode) { next = nextNode; } // end setNextNode    } // end Node } // end LinkedStack

Write the method of type T in this class to pop’s the bottom/last element in the stack if stack is not empty otherwise it returns null. and another method of type boolean to removes the first element in the stack to the last element in the stack. If successful return true otherwise return false

Answer 1

Here is the completed code for this problem. Added codes for popBottom() method and moveFirstToLast() method. Change method names as you wish. 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

// LinkedStack.java

public final class LinkedStack<T> implements StackInterface<T> {

      private Node topNode; // References the first node in the chain

      public LinkedStack() {

            topNode = null;

      }

      // end default constructor

      public void push(T newEntry) {

            topNode = new Node(newEntry, topNode);

            // Node newNode = new Node(newEntry, topNode);

            // topNode = newNode;

      } // end push

      public T peek() {

            if (isEmpty())

                  throw new EmptyStackException();

            else

                  return topNode.getData();

      } // end peek

      public T pop() {

            T top = peek(); // Might throw EmptyStackException

            assert (topNode != null);

            topNode = topNode.getNextNode();

            return top;

      } // end pop

      /*

      * // Question 1, Chapter 6: Does not call peek public T pop() { if

      * (isEmpty()) throw new EmptyStackException(); else { assert (topNode !=

      * null); top = topNode.getData(); topNode = topNode.getNextNode(); } // end

      * if return top; } // end pop

      */

      public boolean isEmpty() {

            return topNode == null;

      } // end isEmpty

      public void clear() {

            topNode = null; // Causes deallocation of nodes in the chain

      } // end clear

      // method to pop and return the bottom most element

      public T popBottom() {

            // if stack is empty, returning false

            if (isEmpty()) {

                  return null;

            }

            // if stack has only one element, setting top node to null, and

            // returning the removed value

            if (topNode.getNextNode() == null) {

                  T data = topNode.getData();

                  topNode = null;

                  return data;

            }

            // otherwise taking reference to first two nodes

            Node prev = topNode;

            Node next = topNode.getNextNode();

            // looping until next is the last node

            while (next.getNextNode() != null) {

                  // advancing nodes

                  prev = next;

                  next = next.getNextNode();

            }

            // now we simply removing next node (the last node) by setting null as

            // next node of prev

            T data = next.getData();

            prev.setNextNode(null);

            return data; // returning removed data

      }

      // method to move first element (top) to the last (bottom)

      public boolean moveFirstToLast() {

            // returning false if stack is empty

            if (isEmpty()) {

                  return false;

            }

            // returning true if stack has only one element (we dont have to do

            // anything in that case, you may return false if you prefer that)

            if (topNode.getNextNode() == null) {

                  return true;

            }

            // popping top value

            T data = pop();

            // and finding the last node starting from new topNode

            Node n = topNode;

            while (n.getNextNode() != null) {

                  n = n.getNextNode();

            }

            // adding the removed value as the next of current last node

            n.setNextNode(new Node(data));

            return true; // success

      }

      private class Node {

            private T data; // Entry in stack

            private Node next; // Link to next node

            private Node(T dataPortion) {

                  this(dataPortion, null);

            } // end constructor

            private Node(T dataPortion, Node linkPortion) {

                  data = dataPortion;

                  next = linkPortion;

            } // end constructor

            private T getData() {

                  return data;

            } // end getData

            private void setData(T newData) {

                  data = newData;

            } // end setData

            private Node getNextNode() {

                  return next;

            } // end getNextNode

            private void setNextNode(Node nextNode) {

                  next = nextNode;

            } // end setNextNode

      } // end Node

} // end LinkedStack