All needed classes below:

public interface Worklist { /** * Add one String to the worklist. * @param item the String to add */ void add(String item); /** * Test whether there are more elements in the * worklist; that is, test whether more elements have * been added than have been removed. * @return true if there are more elements */ boolean hasMore(); /** * Remove one String from the worklist and return it. * There must be at least one element in the worklist. * @return the String item removed */ String remove(); }

public class Node { private String data; // Each node has a String... private Node link; // ...and a link to the next Node /** * Node constructor. * @param theData the String to store in this Node * @param theLink a link to the next Node */ public Node(String theData, Node theLink) { data = theData; link = theLink; } /** * Accessor for the String data stored in this Node. * @return our String item */ public String getData() { return data; } /** * Accessor for the link to the next Node. * @return the next Node */ public Node getLink() { return link; } }

public class Stack implements Worklist { private Node top = null; // The top Node in the stack /** * Push a String on top of this stack. * @param data the String to add */ public void add(String data) { top = new Node(data,top); } /** * Test whether this stack has more elements. * @return true if this stack is not empty */ public boolean hasMore() { return (top != null); } /** * Pop the top String from this stack and return it. * This should be called only if the stack is * not empty. * @return the popped String */ public String remove() { Node n = top; top = n.getLink(); return n.getData(); } }

a. Write a class Queue that implements the Worklist interface, using a first-in- first-out order. Implement your Queue using a linked list. b. Write a class PriorityQueue that implements the Worklist interface. No matter in what order strings are added with the add method, the remove method should always return the alphabetically first string still in the worklist. (To compare two strings alphabetically, use the compare to method of the String class. s.compareTo (r) is less than zero if s comes before r, equal to zero if s and r are equal, and greater than zero if s comes after r.) You need not implement a high-efficiency data structure; an implementation using linked lists will do. You may modify the Node class if necessary, but do not change it in a way that breaks the original Stack class. You will need to write some code to test your classes. You can implement Driver-type classes to test your code, as in Chapter 13. An alternative is to add a main method directly to each class you want to test. For example, if you add the following method to the Stack class, you can then run Stack as an application and check that the strings come out in stack order: a. Write a class Queue that implements the Worklist interface, using a first-in- first-out order. Implement your Queue using a linked list. b. Write a class PriorityQueue that implements the Worklist interface. No matter in what order strings are added with the add method, the remove method should always return the alphabetically first string still in the worklist. (To compare two strings alphabetically, use the compare to method of the String class. s.compareTo (r) is less than zero if s comes before r, equal to zero if s and r are equal, and greater than zero if s comes after r.) You need not implement a high-efficiency data structure; an implementation using linked lists will do. You may modify the Node class if necessary, but do not change it in a way that breaks the original Stack class. You will need to write some code to test your classes. You can implement Driver-type classes to test your code, as in Chapter 13. An alternative is to add a main method directly to each class you want to test. For example, if you add the following method to the Stack class, you can then run Stack as an application and check that the strings come out in stack order