Exercise 1 For this exercise you will need the definition of the Worklist interface:

the definition of the Node Class:

Stack class:

Write two additional classes, as follows:

Write a class Queue that implements the Worklist interface, using a first-in-first-out order. Implement your Queue using a linked list.

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 compareTo 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.

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.

Public static void main(String[] args) {

Worklist w = new Stack();

w.add(able);

w.add(charlie);

w.add(baker);

while (w.hasMore()) {

System.out.println(w.remove());

}

}

Creating a similar method to test Queue and PriorityQueue is a good place to start. (But dont stop there-test your code more thoroughly than this!)

You also might be interested in testing your code using an interactive tester with a graphical user interface. The class WorklistDemo, can be run as an application or as an applet. When you place WorklistDemo.java in a directory with the other class definitions it needs ( Worklist.java, Node.java, Stack.java, Queue.java, and PriorityQueue.java), you can compile and run it, testing your Worklist implementations interactively. WorklistDemo shows how to use the API to create a simple applet with a graphical user interface.

import java.awt.BorderLayout;

import java.awt.Container;

import java.awt.FlowLayout;

import java.awt.event.ActionEvent;

import java.awt.event.ActionListener;

import javax.swing.BoxLayout;

import javax.swing.ButtonGroup;

import javax.swing.JApplet;

import javax.swing.JButton;

import javax.swing.JFrame;

import javax.swing.JLabel;

import javax.swing.JPanel;

import javax.swing.JRadioButton;

import javax.swing.JTextField;

/**

* A JApplet / application to test the Worklist interface and its

* implementations.

* @author Adam Webber

*/

public class WorklistDemo extends JApplet {

private static final long serialVersionUID = 0L;

/**

* Our Worklist, initially a Stack.

*/

private Worklist theWorklist = new Stack();

/**

* A JLabel displaying the last String removed from our Worklist.

*/

private JLabel lastRemovedLabel;

/**

* Our remove button, to remove an item from the Worklist.

*/

private JButton remove;

/**

* A JLabel that shows the current value of hasMore().

*/

private JLabel hasMoreLabel;

/**

* Create our GUI components.

*/

@Override public void init() {

// Boilerplate: create components on event-dispatching thread.

try {

javax.swing.SwingUtilities.invokeAndWait(new Runnable() {

public void run() {

createGUI();

}

});

} catch (Exception e) {

System.err.println("createGUI didn't successfully complete");

}

}

/**

* Create the GUI components. This initializes the applet.

*

*/

public void createGUI() {

/*

* First, create our radio buttons and combine them into

* a button group. They are all in a panel together.

*/

final JRadioButton stackButton = new JRadioButton("Stack");

stackButton.setSelected(true);

stackButton.addActionListener(new ActionListener() {

public void actionPerformed(final ActionEvent evt) {

theWorklist = new Stack();

lastRemovedLabel.setText("");

updateHasMore();

}

});

final JRadioButton queueButton = new JRadioButton("Queue");

queueButton.addActionListener(new ActionListener() {

public void actionPerformed(final ActionEvent evt) {

theWorklist = new Queue();

lastRemovedLabel.setText("");

updateHasMore();

}

});

final JRadioButton priorityQueueButton = new JRadioButton("Priority Queue");

priorityQueueButton.addActionListener(new ActionListener() {

public void actionPerformed(final ActionEvent evt) {

theWorklist = new PriorityQueue();

lastRemovedLabel.setText("");

updateHasMore();

}

});

final ButtonGroup group = new ButtonGroup();

group.add(stackButton);

group.add(queueButton);

group.add(priorityQueueButton);

final JPanel radioPanel = new JPanel();

radioPanel.setLayout(new BoxLayout(radioPanel, BoxLayout.Y_AXIS));

radioPanel.add(stackButton);

radioPanel.add(queueButton);

radioPanel.add(priorityQueueButton);

/*

* Now the prompt and text field for entering items for the worklist.

* These are in a panel together.

*/

final JTextField lexeme = new JTextField(15);

lexeme.addActionListener(new ActionListener() {

public void actionPerformed(final ActionEvent evt) {

theWorklist.add(lexeme.getText());

lexeme.setText("");

updateHasMore();

}

});

JPanel itemPanel = new JPanel(new FlowLayout(FlowLayout.CENTER));

itemPanel.add(new JLabel("To add, type the item here and hit Enter:"));

itemPanel.add(lexeme);

/*

* Then the remove button, in a panel by itself.

*/

remove = new JButton("Remove");

remove.addActionListener(new ActionListener() {

public void actionPerformed(final ActionEvent evt) {

if (theWorklist.hasMore()) {

String s = theWorklist.remove();

lastRemovedLabel.setText("Last item removed: " + s);

}

lexeme.setText("");

updateHasMore();

}

});

final JPanel buttonPanel = new JPanel(new FlowLayout(FlowLayout.CENTER));

buttonPanel.add(remove);

/*

* Then the text displays: the last removed text, and the current

* state of hasMore(). These are in a panel together.

*/

hasMoreLabel = new JLabel();

lastRemovedLabel = new JLabel("");

final JPanel textPanel = new JPanel();

textPanel.setLayout(new BoxLayout(textPanel, BoxLayout.Y_AXIS));

textPanel.add(hasMoreLabel);

textPanel.add(lastRemovedLabel);

/*

* Now we'll put the radio buttons and the text panel in the center,

* the item in the north border, and the remove button in the

* south border.

*/

JPanel centerPanel = new JPanel(new FlowLayout(FlowLayout.CENTER));

centerPanel.add(radioPanel);

centerPanel.add(textPanel);

Container content = getContentPane();

content.add(itemPanel, BorderLayout.NORTH);

content.add(centerPanel, BorderLayout.CENTER);

content.add(buttonPanel, BorderLayout.SOUTH);

updateHasMore();

}

/**

* Update the hasMoreLabel, and the state of the remove button, to reflect

* whether the worklist has any more elements.

*/

private void updateHasMore() {

hasMoreLabel.setText("Current value of hasMore(): " + theWorklist.hasMore());

remove.setEnabled(theWorklist.hasMore());

}

/**

* A main method, so we can be run as an application, as well as a JApplet.

*/

public static void main(String[] args) {

final JApplet applet = new WorklistDemo();

applet.init();

final JFrame frame = new JFrame("Worklist Tester");

frame.setContentPane(applet.getContentPane());

frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

frame.pack();

frame.setVisible(true);

}

}

An interface for collections of strings. public interface worklist f Add one string to the worklist param item the String to add void add (String item); Test whether there are more elements in the work list; that is, test whether more elements have been added than have been removed. return true if there are more elements boolean has More 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 An interface for collections of strings. public interface worklist f Add one string to the worklist param item the String to add void add (String item); Test whether there are more elements in the work list; that is, test whether more elements have been added than have been removed. return true if there are more elements boolean has More 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