Application #3

The ADT stack lets you peek at its top entry without removing it. For some applications of stacks, you also need to peek at the entry beneath the top entry without removing it. We will call such an operation peek2:

 If the stack has more than one entry, peek2 method returns the second entry from the top without altering the stack. 

 If the stack has fewer than two entries, peek2 throws InsufficientNumberOfElementsOnStackException. 

Write a linked implementation of a stack that includes a method peek2

Skeleton of LinkedStack class is provided. The class includes main with test cases to test your methods.

public final class LinkedStack implements TextbookStackInterface { private Node topNode; // references the first node in the chain public LinkedStack() { this.topNode = null; // 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 // These methods are only for testing of array implementation public int getTopIndex() { return 0; } public int getCapacity() { return 0; } private class Node { private S data; // Entry in stack private Node next; // Link to next node private Node(S dataPortion) { this(dataPortion, null); } // end constructor private Node(S dataPortion, Node linkPortion) { this.data = dataPortion; this.next = linkPortion; } // end constructor } // end Node public static void main(String[] args) { System.out.println("*** Create a stack ***"); LinkedStack myStack = new LinkedStack<>(); System.out.println("--> Add to stack to get: " + "Joe Jane Jill Jess Jim "); myStack.push("Jim"); myStack.push("Jess"); myStack.push("Jill"); myStack.push("Jane"); myStack.push("Joe"); System.out.println("Done adding 5 elements. "); System.out.println("--> Testing peek, peek2, and pop:"); while (!myStack.isEmpty()) { String top = myStack.peek(); System.out.println(top + " is at the top of the stack."); try { String beneathTop = myStack.peek2(); System.out.println(beneathTop + " is just beneath the top of the stack."); } catch (InsufficientNumberOfElementsOnStackException inoeose) { System.out.println(" CORRECT - exception has been thrown: " + inoeose.getMessage()); } top = myStack.pop(); System.out.println(top + " is removed from the stack. "); } // end while System.out.println("--> The stack should be empty: "); System.out.println("isEmpty() returns " + myStack.isEmpty()); try { String top = myStack.peek(); System.out.println(top + " is at the top of the stack."); } catch (InsufficientNumberOfElementsOnStackException inoeose) { System.out.println(" CORRECT - exception has been thrown: " + inoeose.getMessage()); } try { String top = myStack.pop(); System.out.println(top + " is at the top of the stack."); } catch (InsufficientNumberOfElementsOnStackException inoeose) { System.out.println(" CORRECT - exception has been thrown: " + inoeose.getMessage()); } try { String beneathTop = myStack.peek2(); System.out.println(beneathTop + " is just beneath the top of the stack."); } catch (InsufficientNumberOfElementsOnStackException inoeose) { System.out.println(" CORRECT - exception has been thrown: " + inoeose.getMessage()); } System.out.println("*** Done ***"); } // end main } // end LinkedStack

public class InsufficientNumberOfElementsOnStackException extends RuntimeException { public InsufficientNumberOfElementsOnStackException(String reason) { super(reason); } } 

SAMPLE RUN

*** Create a stack ***

--> Add to stack to get: Joe Jane Jill Jess Jim

Done adding 5 elements.

--> Testing peek, peek2, and pop:

Joe is at the top of the stack.

Jane is just beneath the top of the stack.

Joe is removed from the stack.

Jane is at the top of the stack.

Jill is just beneath the top of the stack.

Jane is removed from the stack.

Jill is at the top of the stack.

Jess is just beneath the top of the stack.

Jill is removed from the stack.

Jess is at the top of the stack.

Jim is just beneath the top of the stack.

Jess is removed from the stack.

Jim is at the top of the stack.

CORRECT - exception has been thrown: cannot complete peek2() - only one element on the stack

Jim 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

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

*** Done ***