Data structures and Algorithms concept. Create a generic class that implements the StackInterface and then create a driver application with the methods to test the methods.

public interface StackInterface { public boolean isEmpty(); // Determines whether the stack is empty. // Precondition: None. // Postcondition: Returns true if the stack is empty; // otherwise returns false. public void popAll(); // Removes all the items from the stack. // Precondition: None. // PostCondition: Stack is empty. public void push(T newItem) throws StackException; // Adds an item to the top of a stack. // Precondition: newItem is the item to be added. // Postcondition: If insertion is successful, newItem // is on the top of the stack. // Exception: Some implementations may throw // StackException when newItem cannot be placed on // the stack. public T pop() throws StackException; // Removes the top of a stack. // Precondition: None. // Postcondition: If the stack is not empty, the item // that was added most recently is removed from the // stack. // Exception: Throws StackException if the stack is // empty. public T peek() throws StackException; // Retrieves the top of a stack. // Precondition: None. // Postcondition: If the stack is not empty, the item // that was added most recently is returned. The // stack is unchanged. // Exception: Throws StackException if the stack is // empty. public String toString(); // Return the String representation of the items in the // collection (top to bottom; single space delimited) // - no additional narratives } // end StackInterface

public class Node { private T item; private Node next; public Node(T newItem) { item = newItem; next = null; } // end constructor public Node(T newItem, Node nextNode) { item = newItem; next = nextNode; } // end constructor public void setItem(T newItem) { item = newItem; } // end setItem public T getItem() { return item; } // end getItem public void setNext(Node nextNode) { next = nextNode; } // end setNext public Node getNext() { return next; } // end getNext } // end class Node

public class StackException extends java.lang.RuntimeException { public StackException(String s) { super(s); } // end constructor } // end StackException

1. Using the StackInterface and StackException, implement it as a generic class using a) Resizable Array-based implementation (StackRA-data fields items array and top integer: index of the top item in the Stack) and b) Simply Linked Structure-based implementation Stack:SLS - only data field top: reference to the node containing the top item in the Stack) using the generic Node class and test them both thoroughly using a menu driven test program with the options below on your own input data. DO NOT add any additional functionality to the stack than the one specified in StackInterface. We will use the convention for toString() to collect the items starting with the top item and ending with the one at the bottom or the stack. 0. Exit Push item onto stack. 2. Pop item from stack. 3. Display top item in the stack. 4. Display items in stack 5. Clear stack Note: More on generics on page 291 of the textbook. When using an array, use the following (separately or combined) which will cause a compiler warning (not error!), which you can disregard. T[] arrayvariable; //declaration arrayvariable = (T() new Object[desiredlength]; //memory allocation for array and assignment array variable When declaring and creating an instance of a generic class, the appropriate type parameter(s) has to be instantiated. Ex: Stack stackl= new Stack0; Stack0; Extra Credit 1. Using the StackInterface and StackException, implement it as a generic class using a) Resizable Array-based implementation (StackRA-data fields items array and top integer: index of the top item in the Stack) and b) Simply Linked Structure-based implementation Stack:SLS - only data field top: reference to the node containing the top item in the Stack) using the generic Node class and test them both thoroughly using a menu driven test program with the options below on your own input data. DO NOT add any additional functionality to the stack than the one specified in StackInterface. We will use the convention for toString() to collect the items starting with the top item and ending with the one at the bottom or the stack. 0. Exit Push item onto stack. 2. Pop item from stack. 3. Display top item in the stack. 4. Display items in stack 5. Clear stack Note: More on generics on page 291 of the textbook. When using an array, use the following (separately or combined) which will cause a compiler warning (not error!), which you can disregard. T[] arrayvariable; //declaration arrayvariable = (T() new Object[desiredlength]; //memory allocation for array and assignment array variable When declaring and creating an instance of a generic class, the appropriate type parameter(s) has to be instantiated. Ex: Stack stackl= new Stack0; Stack0; Extra Credit