Question

The todo section in java please

LinkedStack class (provided as a skeleton) is to implement TextbookStackInterface using chain of nodes to manage the data (see the textbook implementation).

The instance variable topNode is defined as chain head reference. The empty stack should have this variable set to null.

Skeleton of LinkedStack class is provided. Please note that in addition to all the methods defined in the TextbookStackInterface there are two methods: displayStack and remove that you also need to implement:

• displayStack method should display all the entries on the stack without destroying it
• remove(n) method should remove the topmost n entries from the stack; in case the stack contains less than n entries, the method should remove as many as possible.

The class includes main with test cases to test your methods. The output of your program must match the sample run below:

SAMPLE RUN

*** Create a stack ***

--> Pushing A B C D E on the stack

Done adding 5 elements.

The content of the stack:

E

D

C

B

A

--> Testing peek, pop, isEmpty:

E is at the top of the stack.

E is removed from the stack.

D is at the top of the stack.

D is removed from the stack.

C is at the top of the stack.

C is removed from the stack.

B is at the top of the stack.

B is removed from the stack.

A is at the top of the stack.

A is removed from the stack.

--> The stack should be empty:

isEmpty() returns true

CORRECT - exception has been thrown: cannot complete peek() - stack is empty

CORRECT - exception has been thrown: cannot complete pop() - stack is empty

The stack is empty

--> Testing clear:

--> Pushing A B C D E F G on the stack

Done adding 7 elements.

The content of the stack:

G

F

E

D

C

B

A

--> Calling clear()

The stack is empty

--> Testing remove:

--> Calling remove(4) on empty stack

0 elements have been removed.

The stack is empty

--> Pushing A B C D E F G H I J on the stack

Done adding 10 elements.

The content of the stack:

J

I

H

G

F

E

D

C

B

A

--> Calling remove(4)

removing J

removing I

removing H

removing G

4 elements have been removed.

The content of the stack:

F

E

D

C

B

A

--> Calling remove(10)

removing F

removing E

removing D

removing C

removing B

removing A

6 elements have been removed.

The stack is empty

*** Done ***

Process finished with exit code 0

public final class LinkedStack<T> implements TextbookStackInterface<T>
{
    private Node<T> topNode; // references the first node in the chain

    public LinkedStack()
    {
        // TODO PROJECT #3
    } // end default constructor

    public void push(T newEntry)
    {
        // TODO PROJECT #3
    } // end push

    public T peek() throws InsufficientNumberOfElementsOnStackException
    {
        // TODO PROJECT #3
        return null; // THIS IS A STUB
    } // end peek

    public T peek2() throws InsufficientNumberOfElementsOnStackException
    {
        // TODO PROJECT #3
        return null; // THIS IS A STUB
    } // end peek2

    public T pop() throws InsufficientNumberOfElementsOnStackException
    {
        // TODO PROJECT #3
        return null; // THIS IS A STUB
    } // end pop

    public boolean isEmpty()
    {
        // TODO PROJECT #3
        return false;  // THIS IS A STUB
    } // end isEmpty

    public void clear()
    {
        // TODO PROJECT #3

    } // end clear

    public int remove(int numberOfElements)
    {

        // TODO PROJECT #3
        return 0; // THIS IS A STUB
    } // end remove

    public void displayStack()
    {
        // TODO PROJECT #3
    } // end displayStack

public interface TextbookStackInterface<T>
{
   /** Adds a new entry to the top of this stack.
       @param newEntry  An object to be added to the stack. */
   public void push(T newEntry);
  
   /** Removes and returns this stack's top entry.
       @return  The object at the top of the stack. 
       throws  appropriate exception if the stack is empty before the operation. */
   public T pop();
  
   /** Retrieves this stack's top entry.
       @return  The object at the top of the stack.
       throws  appropriate exception if the stack is empty. */
   public T peek();
  
   /** Detects whether this stack is empty.
       @return  True if the stack is empty. */
   public boolean isEmpty();
  
   /** Removes all entries from this stack. */
   public void clear();
} // end StackInterface

Answer 1

LinkedStack.java file:

package linkedstack;

public final class LinkedStack<T> implements TextbookStackInterface<T>
{
    private Node<T> topNode; // references the first node in the chain

    public LinkedStack()
    {
        // default constructor to initialize member variable
       topNode = null; // stack is empty    
    } // end default constructor

    public void push(T newEntry)
    {
        // adds new entry to top of this stack
       // check if topNode is null
       if(topNode == null) { // stack is empty
           // create a new Node with data newEntry and assign it to topNode
           topNode = new Node<T>(newEntry);
       }
       else {
           // stack is not empty
           // create a new node
           Node<T> newNode = new Node<T>(newEntry);
           // link newNode on top of topNode
           newNode.next = topNode;
           // change topNode to top most element in stack
           topNode = newNode;
       }
    } // end push

    public T peek() throws InsufficientNumberOfElementsOnStackException
    {
        // returns top most element in the stack
       // check if stack is Empty
       if(isEmpty()) {
           // throw exception
           throw new InsufficientNumberOfElementsOnStackException("- stack is empty");
       }
        return topNode.getData();
    } // end peek

    public T peek2() throws InsufficientNumberOfElementsOnStackException
    {
       // check if stack is Empty
       if(isEmpty()) {
           // throw exception
           throw new InsufficientNumberOfElementsOnStackException("- stack is empty");
       }
       return topNode.getData();
    } // end peek2

    public T pop() throws InsufficientNumberOfElementsOnStackException
    {
        // remove and returns top element from stack
       // check if stack is Empty
       if(isEmpty()) {
           // throw exception
           throw new InsufficientNumberOfElementsOnStackException("- stack is empty");
       }
       Node<T> n = topNode; // create a Node variable and assign it to topNode
       // move topNode to one element down
       topNode = topNode.next;
        return n.getData(); // return the removed element
    } // end pop

    public boolean isEmpty()
    {
        // check if topNode is null
       if(topNode == null) {
           // stack is empty
           return true;
       }
        return false; // stack contains elements
    } // end isEmpty

    public void clear()
    {
        // remove all elements from stack
       while(topNode != null) {
           try {
               pop();
           } catch (InsufficientNumberOfElementsOnStackException e) {
               e.printStackTrace();
           }
       }
    } // end clear

    public int remove(int numberOfElements)
    {
        // removes numberOfElements from stack
       // if stack contains less element then numberOfElements then remove all elements from stack
       // returns number of elements removed
       int counts = 0; // create a variable to track number of elements removed
       for(int i=0;i<numberOfElements;i++) { // loop till numberOfElements are removed OR till stack became empty
           // check if stack is empty
           if(isEmpty()) {
               break; // break the loop and return
           }
           else {
               try {
                   pop(); // remove top element
                   counts++; // Increment counts by 1
               } catch (InsufficientNumberOfElementsOnStackException e) {
                   e.printStackTrace();
               }
           }
       }
        return counts; // return number of elements removed
    } // end remove

    public void displayStack()
    {
        // display all the entries on stack
       // create a iterator
       Node<T> itr = topNode; // assign it to topNode
       while(itr != null) {
           // loop till last element
           System.out.println(itr.getData()); // print each element on stack
           itr = itr.next;
       }
    } // end displayStack

}

TextbookStackInterface.java file:

package linkedstack;

public interface TextbookStackInterface<T>
{
   /** Adds a new entry to the top of this stack.
       @param newEntry An object to be added to the stack. */
   public void push(T newEntry);

   /** Removes and returns this stack's top entry.
       @return The object at the top of the stack.
       throws appropriate exception if the stack is empty before the operation.
* @throws InsufficientNumberOfElementsOnStackException */
   public T pop() throws InsufficientNumberOfElementsOnStackException;

   /** Retrieves this stack's top entry.
       @return The object at the top of the stack.
       throws appropriate exception if the stack is empty.
* @throws InsufficientNumberOfElementsOnStackException */
   public T peek() throws InsufficientNumberOfElementsOnStackException;

   /** Detects whether this stack is empty.
       @return True if the stack is empty. */
   public boolean isEmpty();

   /** Removes all entries from this stack. */
   public void clear();
} // end StackInterface

InsufficientNumberOfElementsOnStackException.java file:

package linkedstack;

public class InsufficientNumberOfElementsOnStackException extends Exception {

   public InsufficientNumberOfElementsOnStackException(String string) {
       super(string);
   }

   /**
   *
   */
   private static final long serialVersionUID = 1L;

}

Node.java file:

package linkedstack;

public class Node<T> {
  
   private T data;
   public Node<T> next;
   public Node(T e) {
       data = e;
       next = null;
   }
   public T getData() {
       return data;
   }

}

Main.java file:

package linkedstack;

public class Main {

   public static void main(String args[]) {
      
       LinkedStack<Character> stack = new LinkedStack<Character>() ; // create a stack
       System.out.println("Pushing A B C D E on the stack");
       stack.push('A');
       stack.push('B');
       stack.push('C');
       stack.push('D');
       stack.push('E');
       System.out.println("Done adding 5 elements.");
       System.out.println("The content of the stack:");
       stack.displayStack();
      
       System.out.println();
       System.out.println("Testing peek,pop,isEmpty:");
       for(int i=0;i<5;i++) {
           try {
               System.out.print(stack.peek());
               System.out.println(" is at the top of the stack.");
               System.out.print(stack.pop());
               System.out.println(" is removed from the stack.");
           } catch (InsufficientNumberOfElementsOnStackException e) {
               e.printStackTrace();
           }
       }
      
       System.out.println();
       System.out.println("The stack should be empty:");
       System.out.print("isEmpty() returns: ");
       System.out.println(stack.isEmpty());
       try {
           stack.peek();
       } catch (InsufficientNumberOfElementsOnStackException e) {
           System.out.print("exception has been thrown: cannot complete peek()");
           System.out.println(e.getMessage());
       }
       try {
           stack.pop();
       } catch (InsufficientNumberOfElementsOnStackException e) {
           System.out.print("exception has been thrown: cannot complete pop()");
           System.out.println(e.getMessage());
       }
      
       System.out.println();
       System.out.println("Testing clear:");
       stack.clear();
      
       System.out.println();
       System.out.println("Pushing A B C D E F G on the stack");
       stack.push('A');
       stack.push('B');
       stack.push('C');
       stack.push('D');
       stack.push('E');
       stack.push('F');
       stack.push('G');
       System.out.println("Done adding 7 elements.");
       System.out.println("The content of the stack:");
       stack.displayStack();
      
       System.out.println();
       System.out.println("Calling clear()");
       stack.clear();
       System.out.println("The stack is empty");
      
       System.out.println();
       System.out.println("Testing remove:");
       System.out.println("Calling remove(4) on empty stack");
       System.out.print(stack.remove(4));
       System.out.println(" elements have been removed.");
       System.out.println("The stack is empty");
      
       System.out.println();
       System.out.println("Pushing A B C D E F G H I J on the stack");
       stack.push('A');
       stack.push('B');
       stack.push('C');
       stack.push('D');
       stack.push('E');
       stack.push('F');
       stack.push('G');
       stack.push('H');
       stack.push('I');
       stack.push('J');
       System.out.println("Done adding 10 elements.");
       System.out.println("The content of the stack:");
       stack.displayStack();
      
       System.out.println();
       System.out.println("Calling remove(4)");
       System.out.print(stack.remove(4));
       System.out.println(" elements have been removed.");
       System.out.println("The content of the stack:");
       stack.displayStack();
      
       System.out.println();
       System.out.println("Calling remove(10)");
       System.out.print(stack.remove(10));
       System.out.println(" elements have been removed.");
   }
}