Engr 556: Multiparadigm Programming
Spring Semester 2012
Lecture Notes

Queue Abstract Data Type

• Design notes

• Source code
  • Circular array implementation [Queue.java]
  • Linked list implementation [QueueList class]
  • Radix sort program that uses a "queue" class [RadixSort class]

Design Notes on the Queue ADT

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.

Note: A better Java specification would use the Java interface or abstract class constructs to enforce a common interface across all implementations.

Interface Invariant

Once created and intialized properly, each instance represents a valid queue.

Java Class Constructors

public Queue(int maxElements)

public QueueList(int maxElements)

Precondition:

0 < maxElements

Postcondition:

new queue instance has maxElements positions and is empty()

Error action:

if the precondition does not hold, the queue instance should be both empty() and full()

Mutators

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)

Precondition:

not full()

Postcondition:

item is appended to the back of queue

Error action:

if the precondition does not hold, then the queue is left unchanged

public void dequeue()

Precondition:

not empty()

Postcondition:

the front element is removed from this queue

Error action:

if the precondition does not hold, then the queue is left unchanged

Accessors

public Object front()

Precondition:

not empty()

Postcondition

returns the front element of the queue

Error action:

if precondition does not hold, a null is returned

public boolean full()

Precondition:

True

Postcondition:

returns True if and only if no more elements can be added to this queue instance

public boolean empty()

Precondition:

True

Postcondition:

returns True if and only if there are no elements in this queue instance

public int capacity()

Precondition:

True

Postcondition:

returns maximum number of elements possible in this queue instance

public int length()

Precondition:

True

Postcondition:

returns the number of elements currently in this queue instance

Destructor

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.

Testing

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?