Java/队列之道
本章介绍了两个 ADT：队列和优先级队列。在现实生活中，队列是客户等待某种服务的排队。在大多数情况下，排在最前面的顾客是下一个被服务的顾客。不过也有一些例外。例如，在机场，即将起飞的航班的乘客有时会被从队列中间带走。同样，在超市里，礼貌的顾客可能会让只有几件商品的人先走。
决定谁下一个的规则称为排队规则。最简单的排队规则称为 FIFO，代表 “先进先出”。最一般的排队规则是优先级排队，其中每个顾客都被分配一个优先级，优先级最高的顾客先走，无论他们到达的顺序如何。我之所以说这是最一般的规则是因为优先级可以基于任何东西：航班离开的时间、顾客购买的商品数量或顾客的重要性。当然，并非所有排队规则都是“公平的”，但公平与否见仁见智。
队列 ADT 和优先级队列 ADT 有一组相同的操作，它们的接口也相同。区别在于操作的语义：队列使用 FIFO 策略，而优先级队列（顾名思义）使用优先级排队策略。
与大多数 ADT 一样，有很多方法可以实现队列。由于队列是项目的集合，我们可以使用任何用于存储集合的基本机制，包括数组和列表。我们在它们之间进行选择将部分基于它们的性能——执行我们想要执行的操作所需的时间——以及部分基于实现的难易程度。
ADT!Queue Queue ADT implementation!Queue queue!List implementation
队列 ADT 由以下操作定义
描述
[构造函数：] 创建一个新的空队列。
[插入：] 向队列添加一个新项目。
[移除：] 从队列中移除并返回一个项目。返回的项目是第一个添加的项目。
[空：] 检查队列是否为空。
描述
为了演示队列的实现，我将利用来自列表章节的 LinkedList 类。此外，我将假设我们有一个名为 Customer 的类，它定义了每个客户的所有信息以及我们可以对客户执行的操作。
就我们的实现而言，队列中是什么类型的对象并不重要，因此我们可以使它成为泛型的。以下是实现的代码：
逐字 public class Queue
public LinkedList list;
public Queue ()
list = new List ();
public boolean empty ()
return list.empty ();
public void insert (Object obj)
list.addLast (obj);
public Object remove ()
return list.removeFirst ();
逐字
队列对象包含一个实例变量，它就是实现它的列表。对于其他每个方法，我们只需要调用 LinkedList 类中的一个方法。
veneer performance hazard performance analysis
这样的实现称为饰面。在现实生活中，饰面是指家具制作中使用的薄层优质木材，用来隐藏下面的低品质木材。计算机科学家使用这个比喻来描述隐藏实现细节并提供更简单或更标准接口的一小段代码。
这个例子展示了饰面的好处之一，即它易于实现，以及使用饰面的危险之一，即性能风险！
通常，当我们调用一个方法时，我们不会关心它的实现细节。但是，我们可能想了解一个“细节”——方法的性能特征。作为列表中项目数量的函数，它需要多长时间才能运行？
首先让我们看一下 removeFirst。
逐字
public Object removeFirst ()
Object result = head;
if (head != null)
head = head.next;
return result;
逐字
这里没有循环或函数调用，这表明此方法的运行时间每次都是相同的。这样的方法称为恒定时间操作。实际上，当列表为空时，该方法可能稍微快一些，因为它跳过了条件语句的主体，但这种差异并不显著。
constant time
addLast 的性能则大不相同。
逐字
public void addLast (Object obj)
// special case: empty list
if (head == null)
head = new Node (obj, null);
return;
Node last;
for (last = head; last.next != null; last = last.next)
// traverse the list to find the last node
last.next = new Node (obj, null);
逐字
第一个条件语句处理向空列表添加新节点的特殊情况。在这种情况下，同样，运行时间也不依赖于列表的长度。但是，在一般情况下，我们必须遍历列表以找到最后一个元素，以便可以使其引用新节点。
这种遍历所需的时间与列表的长度成正比。由于运行时间是长度的线性函数，我们说这种方法是线性时间。与恒定时间相比，这非常糟糕。
linear time
queue!linked implementation linked queue
我们希望有一个队列 ADT 的实现，它可以在恒定时间内执行所有操作。实现这一点的一种方法是实现链表队列，它类似于链表，因为它是用一个或多个链接的 Node 对象组成的。区别在于队列维护对第一个节点和最后一个节点的引用，如图所示。
figure=figs/queue1.eps,width=4in
以下是链表队列实现的代码：
逐字 public class Queue
public Node first, last;
public Queue ()
first = null;
last = null;
public boolean empty ()
return first == null;
逐字
到目前为止，它很简单。在空队列中，first 和 last 都是 null。要检查列表是否为空，我们只需要检查其中一个。
插入稍微复杂一些，因为我们必须处理几个特殊情况。
逐字
public void insert (Object obj)
Node node = new Node (obj, null);
if (last != null)
last.next = node;
last = node;
if (first == null)
first = last;
逐字
第一个条件语句检查 last 是否引用一个节点；如果引用了，则我们必须使它引用新的节点。
第二个条件语句处理列表最初为空的特殊情况。在这种情况下，first 和 last 都引用新的节点。
移除也处理了几个特殊情况。
逐字
public Object remove ()
Node result = first;
if (first != null)
first = first.next;
if (first == null)
last = null;
return result;
逐字
第一个条件语句检查队列中是否还有节点。如果有，我们必须将下一个节点复制到 first。第二个条件语句处理列表现在为空的特殊情况，在这种情况下，我们必须将 last 设置为 null。
作为练习，绘制一些图表，显示这两种操作在正常情况下和特殊情况下的情况，并说服自己它们是正确的。
显然，这个实现比饰面实现更加复杂，而且更难以证明它是正确的。优点是实现了我们的目标：插入和移除都是恒定时间。
queue!circular buffer implementation circular buffer buffer!circular
队列的另一种常见实现是循环缓冲区。“缓冲区”是临时存储位置的通用名称，尽管它通常是指数组，在本例中就是这样。为什么要说缓冲区是“循环的”将在下面解释。
循环缓冲区的实现类似于栈的数组实现，如数组栈部分。队列项目存储在数组中，我们使用索引来跟踪我们在数组中的位置。在栈的实现中，有一个索引指向下一个可用空间。在队列的实现中，有两个索引：first 指向数组中包含队列中第一个客户的空间，next 指向下一个可用空间。
下图显示了一个包含两个项目（用点表示）的队列。
figure=figs/queue2.eps,width=4in
有两种方法可以理解 first 和 last 变量。从字面上讲，它们是整数，它们的值显示在右侧的方框中。然而，从抽象的角度来说，它们是数组的索引，因此它们通常被绘制成指向数组中位置的箭头。箭头表示很方便，但请记住，索引不是引用，它们只是整数。
以下是一个不完整的队列数组实现：
逐字 public class Queue
public Object[] array; public int first, next;
public Queue ()
array = new Object[128];
first = 0;
next = 0;
public boolean empty ()
return first == next;
逐字
实例变量和构造函数很简单，尽管我们仍然面临着必须为数组选择一个任意大小的问题。稍后，我们将解决这个问题，就像我们在栈中所做的那样，如果数组满了，我们将调整数组的大小。
空实现有点出乎意料。你可能认为 first == 0 表示空队列，但这忽略了队列的头部并不一定位于数组的开头这一事实。相反，我们知道队列为空，如果 head 等于 next，在这种情况下，没有剩余的项目。一旦我们看到 insert 和 remove 的实现，这种情况就更有意义了。
逐字
public void insert (Object item)
array[next] = item;
next++;
public Object remove ()
Object result = array[first];
first++;
return result;
逐字
insert 看起来非常像数组栈部分中的 push；它将新项目放入下一个可用空间，然后增加索引。
remove 类似。它从队列中取出第一个项目，然后增加 first，使其指向队列的新头部。下图显示了移除所有项目后队列的样子。
figure=figs/queue3.eps,width=4in
next 始终指向一个可用空间。如果 first 追上 next 并指向同一个空间，那么 first 就指向一个“空”位置，并且队列为空。我将“空”放在引号中，因为 first 指向的位置实际上可能包含一个值（我们不做任何操作来确保空位置包含 null）；另一方面，由于我们知道队列为空，因此我们永远不会读取这个位置，因此我们可以从抽象的角度认为它为空。
作为练习，修复 remove，使其在队列为空时返回 null。
此实现的下一个问题是它最终会耗尽空间。当我们添加一个项目时，我们递增 next，当我们移除一个项目时，我们递增 first，但我们从未递减任何一个。当我们到达数组末尾时会发生什么？
下图显示了我们在添加四个项目后队列的状态。
figure=figs/queue4.eps,width=4in
数组现在已满。没有“下一个可用空间”，所以 next 无处可指。一种可能性是我们可能调整数组大小，就像我们在堆栈实现中所做的那样。但那样的话，无论队列中实际有多少项目，数组都会不断变大。更好的解决方案是环绕回数组的开头并重用那里的空间。这种“环绕”是这种实现被称为循环缓冲区的原因。
一种环绕索引的方法是在每次递增索引时添加一个特殊情况。
逐字
next++;
if (next == array.length) next = 0;
逐字
一个更巧妙的替代方案是使用模运算符。
逐字
next = (next + 1)
逐字
无论哪种方式，我们都还有一个问题需要解决。我们如何知道队列是否真的已满，这意味着我们无法插入另一个项目？下图显示了队列“已满”时的样子。
figure=figs/queue5.eps,width=4in
数组中仍然有一个空位，但队列已满，因为如果我们插入另一个项目，那么我们必须递增 next 使其等于 first，在这种情况下，它看起来像是队列为空！
为了避免这种情况，我们牺牲了数组中的一个空间。那么我们如何判断队列是否已满呢？
逐字
if ((next + 1)
逐字
如果数组已满该怎么办？在这种情况下，调整数组大小可能是唯一的选择。
作为练习，将本节中的所有代码整理在一起，编写一个使用循环缓冲区的队列实现，该循环缓冲区在必要时调整自身大小。
优先队列
[edit | edit source]priority queue!ADT ADT!Priority Queue
优先队列 ADT 与队列 ADT 具有相同的接口，但语义不同。接口是
描述
[构造函数：] 创建一个新的空队列。
[插入：] 向队列添加一个新项目。
[remove:] 从队列中移除并返回一个项目。返回的项目是优先级最高的项目。
[空：] 检查队列是否为空。
描述
语义上的差异在于，从队列中移除的项目不一定是第一个添加的项目。相反，它是队列中优先级最高的任何项目。优先级是什么以及它们如何相互比较，由优先队列实现未指定。它取决于队列中项目的类型。
例如，如果队列中的项目有名称，我们可能会按字母顺序选择它们。如果它们是保龄球分数，我们可能会从最高到最低进行选择，但如果它们是高尔夫分数，我们将从最低到最高进行选择。
generic data structure!generic
所以我们面临着一个新问题。我们想要一个优先队列实现，它是通用的——它应该适用于任何类型的对象——但同时，实现优先队列的代码需要有能力比较它包含的对象。
我们已经看到了使用 Objects 实现泛型数据结构的一种方法，但这并不能解决这个问题，因为除非我们知道它们的类型，否则没有办法比较 Objects。
答案在于 Java 的一项新功能，称为抽象类。
抽象类
[edit | edit source]abstract class class!abstract Comparable abstract class!Comparable
抽象类是一组类。抽象类定义指定了类必须满足的要求才能成为成员。
抽象类通常以“able”结尾，以指示抽象类所需的基本功能。例如，任何提供名为 draw 的方法的类都可以是名为 Drawable 的抽象类的成员。任何包含名为 start 的方法的类都可以是名为 Runnable 的抽象类的成员。
从 Java 2 开始，Java 提供了一个内置的抽象类，我们可以在优先队列的实现中使用它。它被称为 Comparable，它的含义正如它所说。任何属于 Comparable 抽象类的类都必须提供一个名为 compareTo 的方法，该方法比较两个对象并返回一个值，指示一个对象是否大于或小于另一个对象，或者它们是否相同。
许多内置的 Java 类都是 Comparable 抽象类的成员，包括数字包装类，如 Integer 和 Double。
在下一节中，我将展示如何编写一个操作抽象类的 ADT。然后，我们将看到如何编写一个属于现有抽象类的新的（具体）类。然后，我们将看到如何编写一个新的抽象类。
优先队列的数组实现
[edit | edit source]implementation!Priority Queue priority queue!array implementation
在优先队列的实现中，每次我们指定队列中项目的类型时，我们都指定抽象类 Comparable。例如，实例变量是 Comparables 数组和一个整数。
verbatim public class PriorityQueue
private Comparable[] array; private int index;
逐字
像往常一样，index 是数组中下一个可用位置的索引。实例变量被声明为 private，以便其他类无法直接访问它们。
构造函数和 empty 与我们之前看到的类似。我任意选择了数组的初始大小。
逐字
public PriorityQueue ()
array = new Comparable [16];
index = 0;
public boolean empty ()
return index == 0;
逐字
insert 与 push 类似。
逐字
public void insert (Comparable item)
if (index == array.length)
resize ();
array[index] = item;
index++;
逐字
我省略了 resize 的实现。类中唯一实质性的方法是 remove，它必须遍历数组以找到并删除最大的项目。
逐字
public Comparable remove ()
if (index == 0) return null;
int maxIndex = 0;
// find the index of the item with the highest priority
for (int i=1; i<index; i++)
if (array[i].compareTo (array[maxIndex]) > 0)
maxIndex = i;
Comparable result = array[maxIndex];
// move the last item into the empty slot
index--;
array[maxIndex] = array[index];
return result;
逐字
当我们遍历数组时，maxIndex 会跟踪我们迄今为止看到的最大元素的索引。什么是“最大”由 compareTo 决定。在本例中，compareTo 方法由 Integer 类提供，它按预期执行——更大的（更正的）数字获胜。
优先队列客户端
[edit | edit source]client abstract class class!abstract
优先队列的实现完全是用 Comparable 对象编写的，但没有 Comparable 对象！试试创建它吧。
逐字
Comparable comp = new Comparable (); // ERROR
逐字
你会收到一个编译时消息，内容类似于“java.lang.Comparable 是一个接口。它不能被实例化。”在 Java 中，抽象类被称为接口。我之前一直避免使用这个词，因为它还有其他意思，但现在你必须知道了。
interface
为什么抽象类不能被实例化？因为抽象类只指定要求（你必须有一个 compareTo 方法）；它不提供实现。
要创建一个 Comparable 对象，你必须创建一个属于 Comparable 集合的其中一个对象，例如 Integer。然后你可以在任何需要 Comparable 的地方使用该对象。
逐字
PriorityQueue pq = new PriorityQueue ();
Integer item = new Integer (17);
pq.insert (item);
逐字
此代码创建一个新的空优先队列和一个新的 Integer 对象。然后它将 Integer 插入队列。insert 期望一个 Comparable 作为参数，因此它很乐意接受一个 Integer。如果我们尝试传递一个 Rectangle（不属于 Comparable），我们会收到一条类似于“方法不兼容的类型。需要显式转换才能将 java.awt.Rectangle 转换为 java.lang.Comparable。”的编译时消息。
这是编译器告诉我们，如果我们想进行这种转换，我们必须显式地进行转换。我们可能会尝试按照它的建议去做。
verbatim Rectangle rect = new Rectangle (); pq.insert ((Comparable) rect); verbatim
但在这种情况下，我们会收到一个运行时错误，即 ClassCastException。当 Rectangle 尝试作为 Comparable 传递时，运行时系统会检查它是否满足要求，并拒绝它。所以这就是我们按照编译器建议所得到的。
ClassCastException exception!ClassCastException
要从队列中取出项目，我们必须反转该过程。
逐字
while (!pq.empty ())
item = (Integer) pq.remove ();
System.out.println (item);
逐字
此循环从队列中移除所有项目并打印它们。它假设队列中的项目是 Integer。如果不是，我们会收到一个 ClassCastException。
Golfer 类
[edit | edit source]Golfer class!Golfer abstract class!implementing Comparable
最后，让我们看看如何创建一个属于 Comparable 的新类。作为具有“最高”优先级的非同寻常定义的示例，我们将使用高尔夫球手：
verbatim public class Golfer implements Comparable
String name; int score;
public Golfer (String name, int score)
this.name = name;
this.score = score;
逐字
类定义和构造函数基本相同；不同之处在于我们必须声明 Golfer 实现 Comparable。在本例中，关键字 implements 意味着 Golfer 实现 Comparable 指定的接口。
如果我们尝试在此时编译 Golfer.java，我们会收到类似于“类 Golfer 必须声明为抽象类。它没有定义接口 java.lang.Comparable 中的 int compareTo(java.lang.Object)。”的消息。换句话说，要成为 Comparable，Golfer 必须提供一个名为 compareTo 的方法。所以让我们写一个吧。
逐字
public int compareTo (Object obj)
Golfer that = (Golfer) obj;
int a = this.score;
int b = that.score;
// for golfers, low is good!
if (a < b) return 1;
if (a > b) return -1;
return 0;
逐字
这里有两个地方有点令人惊讶。首先，参数是 Object。这是因为通常情况下，调用者不知道要比较的对象是什么类型。例如，在 PriorityQueue.java 中，当我们调用 compareTo 时，我们传递一个 Comparable 作为参数。我们不必知道它是一个 Integer 还是一个 Golfer，或者其他什么东西。
在 compareTo 内部，我们必须将参数从 Object 转换为 Golfer。像往常一样，当我们进行这种转换时存在风险：如果我们转换为错误的类型，我们会得到一个异常。
最后，我们可以创建一些高尔夫球手。
逐字
Golfer tiger = new Golfer ("Tiger Woods", 61);
Golfer phil = new Golfer ("Phil Mickelson", 72);
Golfer hal = new Golfer ("Hal Sutton", 69);
逐字
并将它们放入队列中。
逐字
pq.insert (tiger);
pq.insert (phil);
pq.insert (hal);
逐字
当我们把它们拉出来的时候。
逐字
while (!pq.empty ())
golfer = (Golfer) pq.remove ();
System.out.println (golfer);
逐字
它们以降序排列（对于高尔夫球手）。
逐字
Tiger Woods 61
Hal Sutton 69
Phil Mickelson 72
逐字
当我们从 Integers 切换到 Golfers 时，我们完全不需要在 PriorityQueue.java 中进行任何更改。因此，我们成功地维护了 PriorityQueue 和使用它的类之间的屏障，允许我们无需修改地重用代码。此外，我们能够让客户端代码控制 compareTo 的定义，从而使 PriorityQueue 的这种实现更加通用。
queue queueing discipline FIFO priority queue veneer constant time linear time performance hazard linked queue circular buffer abstract class interface
描述
[队列:] 一组有序的对象，等待某种服务。
[排队策略:] 决定队列中哪个成员下一个被移除的规则。
[FIFO:] ``先进先出，一种排队策略，其中 最先到达的成员最先被移除。
[优先队列:] 一种排队策略，其中每个成员都有一个由外部因素决定的优先级。优先级最高的成员最先被移除。
[优先队列:] 一种 ADT，定义了可以在优先队列上执行的操作。
[装饰:] 一个类定义，它使用方法定义来实现一个 ADT，这些方法定义是对其他方法的调用，有时带有简单的转换。装饰不执行任何重要工作，但它改进或标准化了客户端看到的接口。
[性能风险:] 与装饰相关的风险，即某些方法的实现方式可能效率低下，而客户端无法察觉。
[常数时间:] 一种操作，其运行时间不依赖于数据结构的大小。
[线性时间:] 一种操作，其运行时间是数据结构大小的线性函数。
[链表队列:] 使用链表和对第一个和最后一个节点的引用来实现队列。
[循环缓冲区:] 使用数组和第一个元素的索引以及下一个可用空间的索引来实现队列。
[抽象类:] 一组类。抽象类规范列出了类必须满足的要求才能包含在该组中。
[接口:] Java 中对抽象类的称呼。不要与该词语更广泛的含义混淆。