12. 队列¶
12.1. 队列术语与实现¶
与栈类似， 队列 是一种类列表结构，它对其元素提供受限访问。队列元素只能在末尾插入（称为 队列 操作），并从前端移除（称为 队列 操作）。队列的操作就像在电影院售票处排队一样。如果没人作弊，那么新来的人排在队尾。队头的人是下一个将要被服务的人。因此，队列按到达顺序释放其元素。在英国，人们排队被称为"queue"，排队等待服务被称为"queuing up"。会计师早在计算机出现之前就已经使用了队列。他们称队列为"FIFO"列表，这代表"First-In, First-Out"。这里有一个队列 ADT 的示例。本节介绍两种队列实现：基于数组的队列和链表队列。
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();
}
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();
}
12.1.1. 基于数组的队列¶
基于数组的队列实现起来有些棘手。
12.1.2. 环形队列¶
如果值 front 是固定的，那么需要 \(n+1\) 个不同的值 rear 来区分 \(n+1\) 个状态。然而，除非我们为比如说空队列发明一个特例，否则 \(n\) 个可能的值 rear 不足以区分这些状态。这是 鸽巢原理 的一个例子。鸽巢原理指出，给定 \(n\) 个鸽巢和 \(n+1\) 只鸽子，当所有鸽子都进入鸽巢时，我们可以确信至少有一个鸽巢包含多于一只鸽子。以类似的方式，我们可以确信 \(n+1\) 个状态中的两个无法通过 \(n\) 个 front 和 rear 的相对值来区分。我们必须寻求其他方法来区分满队列和空队列。
一个显而易见的解决方案是显式记录队列中元素的数量，或者至少维护一个布尔变量来指示队列是否为空。另一种解决方案是将数组大小设为 \(n+1\) ，并仅允许存储 \(n\) 个元素。采用哪种解决方案纯粹取决于实现者的偏好。我们这里的选择是使用大小为 \(n+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; }
}
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;
}
}
12.1.3. 基于数组的队列实现¶
在此实现中，队列的前端被定义为指向数组中编号较低的位置（在循环数组中为逆时针方向），而后端被定义为指向编号较高的位置。因此， enqueue 增加后端指针（模 maxSize ）， dequeue 增加前端指针。所有成员函数的实现都很直接。
