Homework 3
Linked Lists

Due Date: Wednesday, November 3
Point Value: 100 points 

Overview and Specifications

In this homework assignment, you will create an OrderedQueue class and an UnorderedQueue class both of which implement a PriorityQueue interface. The classes will be used by a program that maintains a list of prioritized printer jobs. Each job has a number and a positive integer priority with a higher number signifying a higher priority. For example, a priority of 100 is considered higher than a priority of 25. The same job number may NOT appear in the list more than once. The priority must be > 0.

The OrderedQueue class will maintain a linked list in sorted order by priority, with the highest priority job occuring first in the list and the lowest priority job occuring last. For example: 

[25 #45897]->[10 #89870]->[5 #94510]->[5 #90888]->NULL
where the first number is the priority and the second number is the job number.

The UnorderedQueue class will simply add new jobs to the end of the list. For example: 

[5 #94510]->[25 #45897]->[10 #89870]->[5 #90888]->NULL
In both lists, jobs with the same priority should appear in the order in which they were added to the list. So if a job with priority 25 for job #89933 was added to the Ordered list shown above it would become: 
[25 #45897]->[25 #89933]->[10 #89870]->[5 #94510]->[5 #90888]->NULL
The same message added to the Unordered list would result in the following list: 
[5 #94510]->[25 #45897]->[10 #89870]->[5 #90888]->[25 #89933]->NULL
The job, [25 #45897], would be considered the maximum priority job in both lists.

The Node class and the PriorityQueue interface along with the TestQueue program are provided for you in the directory, /afs/eos.ncsu.edu/courses/csc/csc216/common/www/Homework/5_HW.

The Node class contains as data members an integer priority, priority, a job number represented by the String jobNumber, and a link to the next Node, link. It also contains a toString() method.

Please take the time to examine the TestQueue program listed above to see how it makes use of an interface to use two different data structures to provide the same functionality.

The OrderedQueue Class

You must write the OrderedQueue class which implements the provided PriorityQueue interface. The class must maintain a linked list of Nodes in sorted order by priority, with the first Node in the list containing the highest (maximum) priority. Nodes with the same priority should appear in the list in the order in which they were added to the list. The class must contain ONLY one instance variable defined as 
protected Node head;
Some methods, as specified in the interface file, must be implemented recursively using helper methods with NO loops or static variables!

The UnorderedQueue Class

You must write the UnorderedQueueclass which implements the provided PriorityQueue interface. The class should simply add new Nodes to the end of the list resulting in an "unordered" list. The class must contain EXACTLY two instance variables defined as 
protected Node head;
protected Node tail;
Some methods, as specified in the interface file, must be implemented recursively using helper methods with NO loops or static variables!

Testing

Use the TestQueue program to test your class implementations. Use O which stands for "O"rderedQueue and U which stands for "U"norderedQueue as command line arguments to test your OrderedQueue and UnorderedQueue classes respectively: 
csc% java TestQueue O
OR 
csc% java TestQueue U
The expected output from the test programs is provided in the files, OrderedQueueOutput and UnorderedQueueOutput

README file

You will also need to create and submit a file named exactly README containing your answers to the following questions:
  1. Which methods were easy to implement in the OrderedQueue class?
  2. Which were more difficult to implement?
  3. How many Nodes needed to be examined to return the job with the maximum priority in an OrderedQueue containing n Nodes?
  4. On average how many Nodes needed to be considered to add a new Node to an Ordered List containing n Nodes?
  5. Which methods were easy to implement in the UnorderedQueue class?
  6. Which were more difficult to implement?
  7. How many Nodes needed to be examined to return the job with the maximum prioriy in an UnorderedQueue containing n Nodes?
  8. How many Nodes must be considered to add a new Node to an UnorderedQueue containing n Nodes?
  9. If an application program returned the job with the maximum priority 20 times as often as it added a new Node to the list, would it be more efficient to use the Ordered or Unordered queue?

Submit and Grading

Your code must follow the CSC 116/216 Style Guidelines. Every method and class must be documented using javadoc comments. The documentation for each class must contain the "@author" tag as well as the basic description of the class. The documentation of each method must contain a basic description, the "@param" tag for every parameter, the "@return" tag for any non-void returns, and the "@throws" tag if it throws an exception. For example, 


/**
 * Inserts the integers in the other IntegerList in this Integer List beginning at
 * the given index
 * @param other other IntegerList
 * @param n index in IntegerList where first integer in the other IntegerList should
 *          be inserted
 * @throws java.lang.ArrayIndexOutOfBoundsException
 */
  public void insert(IntegerList other, int n) 
                             throws ArrayIndexOutOfBoundsException {