Queues
We know Queues well from IC211. If a Stack is a LIFO (Last-In First-Out), then a Queue is a FIFO (First-In First-Out). In other words, things come out in exactly the same order they went in.
Think about a line for the checkout counter at the grocery store (after all, "queue" is British for "line"). People can only join the line at the end, and only leave the line at the front. In between, they never switch order.
The methods a Queue must have are:
- enqueue(e) - Add an element to the back of the Queue
- dequeue() - Remove and return the front element of the Queue
- head() - Return, but do not remove, the front element of the Queue
Implementation
Implementation with a Linked List is fairly straightforward. Enqueue is just an add-to-back, which is O(1) if we have a pointer to the last link in the Linked List. Dequeue is just a remove-from-front, which, again, is O(1). head is Dequeue but easier, so it is also O(1).
Implementation with an array requires a bit more bookkeeping. Every time we dequeue, we don't want to shift everything down so that the first element remains at the front of the array, that would be expensive and silly. So, we keep two indices: front, and back. Front points at the first element of the queue, and back points at the index just behind the last one. Both front and back can wrap around the end of the array, back to the beginning of the array if appropriate. If the array fills up, we double the size of the array, as with the stack. So, enqueue is an AMORTIZED O(1), just like push. dequeue and head are also trivially O(1).
Rather than a front and back, you can also keep a front and size. My implementation of a Queue for the Project is below, implemented in this way.
/**
* Implements a Queue, using an array.
*/
public class Queue {
/** The array of tokens */
private Token[] a;
/** The index of the first element of the Queue */
private int front;
/** The number of elements in the Queue*/
private int size;
/**
* Initializes the array to size one, and sets front and size to 0
*/
public Queue() {
a = new Token[1];
front = 0;
size = 0;
}
@Override
public String toString() {
String s = "";
for (int i = 0; i < size; i++)
s+=a[(front+i)%a.length] + " ";
return s;
}
/**
* Returns the number of elements in the Queue.
*/
public int size() {
return size;
}
/**
* Places the Token in the back of the Queue.
* @param t The Token to the enqueued
*/
public void enqueue(Token t) {
//If the array is full, build a new array that is twice as big, and move
//everything over into it
if (size == a.length) {
Token[] a2 = new Token[a.length*2];
for (int i = 0; i < size; i++)
a2[i] = a[(front+i)%a.length];
front = 0;
a = a2;
}
// (front+size)%a.length is the index of the back of the queue
a[(front+size)%a.length]=t;
size++;
}
/**
* Return the first element of the Queue, and remove it from the Queue
* @throws QueueEmptyException if the Queue has no element to return.
*/
public Token dequeue() {
if (size == 0)
throw new QueueEmptyException();
size--;
Token t = a[front];
front = (front + 1)%a.length;
return t;
}
/**
* Return the first element of the Queue, but does not remove it from the
* Queue
* @throws QueueEmptyException if the Queue has no element to return.
*/
public Token head() {
if (size == 0)
throw new QueueEmptyException();
return a[front];
}
}