The instructor developed this example circa 1997 using the then current nongeneric Java implementation. The design approach is still relevant, but the Java implementation may be dated.
A queue is a first-in-first-out (FIFO) sequential data structure in which elements are added (enqueued) at one end (the back) and elements are removed (dequeued) at the other end (the front).
The
Queue class provides an implementation of a bounded
capacity queue abstract data type (ADT) that uses a fixed-size,
circular array buffer to store the queue.
The
QueueList class provides an implementation of a
bounded capacity queue ADT that uses a linked list to store the queue.
Of course, it usually makes more sense to have an unbounded capacity
queue when a linked implementation is used.
Below we give the specification of the queue ADT. Or, more
precisely, we give the interface to the two Java implementations of
the queue ADT, the classes Queue and
QueueList.
We do not handle error conditions, such as the violation of the precondition, very robustly in the given implementations. The queues classes should use the Java exception mechanism.
1997 Note: A better Java specification would use the Java
interface or abstract class constructs to
enforce a common interface across all implementations.
Once created and intialized properly, each instance represents a valid queue.
public Queue(int maxElements) public QueueList(int maxElements) 0 < maxElements maxElements
positions and is empty() empty() and full() As was the case with the stack ADTs given in the Data Abstraction notes, we
separate the traditional "dequeue" operation into its two atomic
subparts, a pure mutator operation dequeue() and a pure
accessor operation front().
public void enqueue(Object item) not full() item is appended to the back of queue
public void dequeue() not empty() public Object front() not empty()
public boolean full() True True if and only if no more elements can be
added to this queue instance
public boolean empty() True True if and only if there are no elements in
this queue instance
public int capacity() True
public int length() True No destructor is specified.
If a destructor were to be implemented, it should assign
null to most reference variables in the implementation.
After call of the destructor, the queue instances should be both empty
and full.
Note that both the circular array and the linked list
implementations both include a main method that gives a
test driver for the queue class.
It is an excellent idea to include such a test driver with every ADT implementation. However, for production code, the test driver probably should be in a separate class. To include the code in a class makes the loading of the class (which occurs at run time) slower than necessary.
Note also that special methods TEST_back() and
TEST_print() were also included in the class as
private methods. The test driver program uses these
methods in the testing process. They are not intended to be part of
the public interface of the class because they are not part of the
queue abstraction. If the test driver is moved outside the class,
then other techniques will be needed to give that type of access to
the internal implementations.
UP to CSci 556 Lecture Notes root document?