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).
class provides an implementation of a bounded capacity queue abstract
data type (ADT) that uses a fixed-size, circular array buffer to store
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
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
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
maxElementspositions and is
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
public void enqueue(Object item)
itemis appended to the back of queue
public void dequeue()
public Object front()
public boolean full()
Trueif and only if no more elements can be added to this queue instance
public boolean empty()
Trueif and only if there are no elements in this queue instance
public int capacity()
public int length()
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
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_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 ENGR 691 Lecture Notes root document?