1: GQueue
A queue is an ordered collection of items in which the removal of items is restricted to the FIFO ( rst in rst out) principle. That is, the rst item added to the queue will be the rst
one removed, the second added will be the second removed, etc.
When you are standing in line waiting for a bank teller, you are in a queue of people. The rst in the line is the rst to be served. The next in line is the second to be served (or removed from the queue). Using this understanding of a queue, we will say that items added to a queue are added to the back of the queue (i.e., you go to the back of the line when you add yourself to the line). The word for adding an element to a queue is enqueue. When we remove an item for a queue, we remove it from the front of the queue (i.e., if you are next to be served in the line, you are at the front of the line). The word for removing an item from
a queue is dequeue.
Recall that we used top for the place where we add and remove elements from a Stack. While this word has a natural meaning to us, it should reveal how the Stack ADT is imple-
mented in code. Similarly, we use back and front for the two \ends" of a queue, but these words do not necessarily relate to the actual data structures used to implement a Queue
ADT.
In this assignment, you will write code for a generic Queue ADT, which we will call GQueue. Here is the ADT for a Queue:
Queue
data operations
an ordered collection of items - add an item to the collection
(need not be unique) - remove an item from the collection using FIFO principle
- ask if the collection is empty or not
- ask what the next item removed would be
- ask how many items are in the collection
Your Java class must use generics for the data type of the elements in the queue. Your class must implement the Comparable interface.
Your generic Queue implementation should have the following public methods and constructors (with appropriate return and input argument types):
public boolean enqueue(...)
// purpose: add an item to the back of the queue if possible
--> // preconditions: item added must be same type as specified when this was created
// postconditions: if size of the queue is < capacity of the queue
// adds the item to the queue,
// the size of the queue is incremented by 1,
// returns true
// otherwise (the size of the queue = capacity of the queue)
// return false and do nothing
dequeue()
// purpose: retrieve the item from the front of the queue
// preconditions: the queue must be non-empty
// postconditions: returns the item at the front of the queue
// that item is removed from the queue
// the size of the queue is decremented by 1
isEmpty()
// purpose: asks if the queue is empty or not
// postconditions: returns true if the queue is empty
// returns false if there is 1 or more items in the queue
size()
// purpose: returns the size of the queue
// postconditions: returns the number of items in the queue
peek()
// purpose: ask what item is at the front of the queue
// preconditions: the queue must be non-empty
// postconditions: returns the item at the front of the queue
// (does not remove the item)
// (does not decrement size)
-> isFull()
// purpose: ask if there is room to add an item to the queue
// postconditions: returns true if the queue is full (it has reached its capacity)
// returns false if there is room to add at least one more item
GQueue(int n)
// purpose: create an empty queue with capacity n
// preconditions: none
// postconditions: creates an empty queue with capacity n
// (the queue can store up to n items at any given time)