9.1. Queues¶
9.1.1. Queue Terminology and Implementation¶
Like the stack, the queue is a list-like structure that provides restricted access to its elements. Queue elements may only be inserted at the back (called an enqueue operation) and removed from the front (called a dequeue operation). Queues operate like standing in line at a movie theater ticket counter. If nobody cheats, then newcomers go to the back of the line. The person at the front of the line is the next to be served. Thus, queues release their elements in order of arrival. In Britain, a line of people is called a “queue”, and getting into line to wait for service is called “queuing up”. Accountants have used queues since long before the existence of computers. They call a queue a “FIFO” list, which stands for “First-In, First-Out”. Here is a sample queue ADT. This section presents two implementations for queues: the array-based queue and the linked queue.
public interface Queue<E> { // Queue class ADT
// Reinitialize queue
public void clear();
// Put element on rear
public boolean enqueue(E it);
// Remove and return element from front
public E dequeue();
// Return front element
public E frontValue();
// Return queue size
public int length();
//Tell if the queue is empty or not
public boolean isEmpty();
}
public interface Queue { // Queue class ADT
// Reinitialize queue
public void clear();
// Put element on rear
public boolean enqueue(Object it);
// Remove and return element from front
public Object dequeue();
// Return front element
public Object frontValue();
// Return queue size
public int length();
// Return true if the queue is empty
public boolean isEmpty();
}
9.1.1.1. Array-Based Queues¶
The array-based queue is somewhat tricky to implement effectively. A simple conversion of the array-based list implementation is not efficient.
9.1.1.2. The Circular Queue¶
If the value of front is fixed, then \(n+1\) different
values for rear are needed to distinguish among the \(n+1\)
states.
However, there are only \(n\) possible values for rear unless
we invent a special case for, say, empty queues.
This is an example of the Pigeonhole Principle.
The Pigeonhole Principle states that, given \(n\) pigeonholes
and \(n+1\) pigeons, when all of the pigeons go into the holes we
can be sure that at least one hole contains more than one pigeon.
In similar manner, we can be sure that two of the \(n+1\) states
are indistinguishable by the \(n\) relative values of front
and rear.
We must seek some other way to distinguish full from empty queues.
One obvious solution is to keep an explicit count of the number of elements in the queue, or at least a Boolean variable that indicates whether the queue is empty or not. Another solution is to make the array be of size \(n+1\), and only allow \(n\) elements to be stored. Which of these solutions to adopt is purely a matter of the implementor’s taste in such affairs. Our choice here is to use an array of size \(n+1\).
Here is an array-based queue implementation.
class AQueue<E> implements Queue<E> {
private E queueArray[]; // Array holding queue elements
private static final int DEFAULT_SIZE = 10;
private int maxSize; // Maximum size of queue
private int front; // Index of front element
private int rear; // Index of rear element
// Constructors
@SuppressWarnings("unchecked") // Generic array allocation
AQueue(int size) {
maxSize = size+1; // One extra space is allocated
rear = 0; front = 1;
queueArray = (E[])new Object[maxSize]; // Create queueArray
}
AQueue() {
this(DEFAULT_SIZE);
}
// Reinitialize
public void clear() {
rear = 0; front = 1;
}
// Put "it" in queue
public boolean enqueue(E it) {
if (((rear+2) % maxSize) == front) {
return false; // Full
}
rear = (rear+1) % maxSize; // Circular increment
queueArray[rear] = it;
return true;
}
// Remove and return front value
public E dequeue() {
if(length() == 0) {
return null;
}
E it = queueArray[front];
front = (front+1) % maxSize; // Circular increment
return it;
}
// Return front value
public E frontValue() {
if (length() == 0) {
return null;
}
return queueArray[front];
}
// Return queue size
public int length() {
return ((rear+maxSize) - front + 1) % maxSize;
}
//Tell if the queue is empty or not
public boolean isEmpty() {
return front - rear == 1;
}
}
class AQueue implements Queue {
private Object queueArray[]; // Array holding queue elements
private static final int DEFAULT_SIZE = 10;
private int maxSize; // Maximum size of queue
private int front; // Index of front element
private int rear; // Index of rear element
// Constructors
AQueue(int size) {
maxSize = size + 1; // One extra space is allocated
rear = 0; front = 1;
queueArray = new Object[maxSize]; // Create queueArray
}
AQueue() { this(DEFAULT_SIZE); }
// Reinitialize
public void clear() { rear = 0; front = 1; }
// Put "it" in queue
public boolean enqueue(Object it) {
if (((rear+2) % maxSize) == front) return false; // Full
rear = (rear+1) % maxSize; // Circular increment
queueArray[rear] = it;
return true;
}
// Remove and return front value
public Object dequeue() {
if(length() == 0) return null;
Object it = queueArray[front];
front = (front+1) % maxSize; // Circular increment
return it;
}
// Return front value
public Object frontValue() {
if (length() == 0) return null;
return queueArray[front];
}
// Return queue size
public int length() { return ((rear+maxSize) - front + 1) % maxSize; }
// Check if the queue is empty
public boolean isEmpty() { return front - rear == 1; }
}
9.1.1.3. Array-based Queue Implementation¶
In this implementation, the front of the queue is defined to be toward
the lower numbered positions in the array (in the counter-clockwise
direction in the circular array), and the rear is
defined to be toward the higher-numbered positions.
Thus, enqueue increments the rear pointer (modulus maxSize),
and dequeue increments the front pointer.
Implementation of all member functions is straightforward.
