Data Structures Project 1

Due Wed, October 4 2000 at 10:59am

In this project, you will construct your own reusable implementation of the queue ADT. The purpose of this assignment simply is to get the feel of Java programming and to develop a reusable class.

Chapter 4 of the textbook describes the queue class. Your queue should be implemented using a linked list and should support the following interface:

public interface IntegerQueue {
   public int size();
   public boolean isEmpty();
   public Integer first() throws EmptyStructureException;
   public Integer dequeue() throws EmptyStructureException;
   public void enqueue(Integer N);
}

Note: Be sure to take into account that one might try to Dequeue from an empty queue. Put (or download) the following exception in the file EmptyStructureException.java. Then you can throw new EmptyStructureException(), for example. See Appendix A for more information about exceptions.

public class EmptyStructureException extends RuntimeException {
   public EmptyStructureException() { super(); }
   public EmptyStructureException(String s) { super(s); }
}

You should create a MyQueue class that implements the IntegerQueue interface with the following additional functions:

  public void print();
  public void sort();

The print() function should simply output every element the queue contains in the queue order, with a space between each element. The print() method should leave its queue in the same state it begins with. The sort() function should rearrange the elements of the queue so that they are in ascending order (or non-decreasing order if there are ties), using only the queue itself and up to five temporary variables.

In the end, the main method of your MyQueue class should fill the queue with 50 randomly generated Integer objects whose values are in the range from 1 to 100 and then print the queue out. It should then be able to sort the queue and then print it again.

So, to sum up, then, you need to do the following in Project 1:

Create the IntegerQueue interface.
Create a class, MyQueue which implements the IntegerQueue interface and contains the print() and sort() functions for the Queue class.
Run your program with 50 randomly generated Integer objects whose values are in the range 1 to 100 to see if it prints and sorts correctly. (Be sure to test several times!)
Submit all of your source files, including the source code for the MyQueue class (MyQueue.java) and also the IntegerQueue interface (IntegerQueue.java).

This project is due at 10:59 am on Wednesday, Oct 4, 2000. Late projects will be marked down 10% for each day they are late.

To submit your project, you need to submit all your source code (all *.java files).

You may download the following file (described above) for your use:

EmptyStructureException.java