4.3 堆栈和队列

在这一节中，我们将介绍两种密切相关的数据类型，用于操作任意大的对象集合：栈和队列。堆栈和队列是集合概念的特例。每一个都有四个操作的特点：创建集合、插入一个项目、删除一个项目、测试集合是否为空。堆栈。堆栈是一个基于后进先出（LIFO）策略的集合。按照传统，我们为堆栈的插入方法push()和堆栈的移除操作pop()命名。我们还包括一个测试堆栈是否为空的方法，如下面的 API 所示。栈的API 堆栈的数组实现。用数组来表示堆栈是一个自然的想法。特别是，我们维护一个实例变量n，用来存储堆栈中的项目数量，还有一个数组items[]，用来存储n个项目，最近插入的项目在items[n-1]中，最近插入的项目在items[0]中。这个策略允许我们在最后添加和删除项目，而不移动堆栈中的任何其他项目。字符串堆栈的固定长度数组实现。ArrayStackOfStrings.java为一个字符串堆栈实现了这种方法，其最大容量由构造函数的参数指定。要删除一个项目，我们递减n，然后返回a[n]；要插入一个新项目，我们将a[n]设置为等于新项目，然后递增n。 ArrayStackOfStrings测试客户端的痕迹调整字符串堆栈的大小的数组实现。ResizingArrayStackOfStrings.java是ArrayStackOfStrings.java的一个版本，它可以动态地调整数组items[]的长度，使其足够大以容纳所有的项目，但又不会大到浪费太多的空间。首先，在push()中，我们检查是否有空间容纳新的项目；如果没有，我们创建一个新的数组，长度为旧数组的两倍，并将旧数组中的项目复制到新数组中。同样，在pop()中，我们检查数组是否太大，如果是这样，我们将其长度减半。追踪使用数组加倍的堆栈实现这种翻倍和减半的策略保证了堆栈永远不会溢出，而且永远不会少于四分之一的长度。调整数组大小的通用堆栈的实现。ResizingArrayStack.java使用一个调整大小的数组实现了一个通用堆栈。由于技术上的原因，在分配泛型数组时需要进行浇注。链接列表。一个单链表包括一个节点序列，每个节点都包含对其后续节点的引用（或链接）。按照惯例，最后一个节点的链接是空的，以表示它是列表的终点。通过面向对象编程，实现链接列表并不困难。我们为节点抽象定义了一个具有递归性质的类。

class Node { 
   String item; 
   Node next; 
} 
 Anatomy of a singly linked list

单链表的剖析

一个Node对象有两个实例变量：一个String和一个Node。在这个例子中，String是一个占位符，用来表示我们可能想要用一个链接列表结构的任何数据（我们可以使用任何一组实例变量）；Node类型的实例变量表征了数据结构的链接性质。将一个链表连接起来。例如，为了建立一个包含 "to"、"be "和 "or "项目的链表，我们为每个项目创建一个 Node。

连结一个链接列表

插入。假设你想在一个链表中插入一个新的节点。最简单的地方是在列表的开头。例如，要在一个给定的链接列表的开头插入字符串 not，其第一个节点是 first，我们将 first 保存在一个临时变量 oldFirst 中，为 first 分配一个新的 Node，并将其项目字段分配给 not，其下一个字段分配给 oldFirst。将一个项目插入一个链表中

删除。假设你想从一个列表中删除第一个节点。这个操作更简单：只需给 first 赋值 first.next 即可。

从一个链接列表中删除一个项目

遍历。为了检查链接列表中的每一个项目，我们初始化一个循环索引变量x，它引用链接列表的第一个节点。然后，我们通过访问x.item找到与x相关的项目的值，然后更新x以引用链表中的下一个节点，将x.next的值赋给它，并重复这个过程，直到x为空（这表明我们已经到达链表的末端）。这个过程被称为遍历列表，并在这个代码片段中被简洁地表达出来。

for (Node x = first; x != null; x = x.next) 
    StdOut.println(x.item)

遍历一个单链表用链表实现堆栈。用链表来表示堆栈是一个自然的想法。特别是，我们首先维护一个实例变量，它存储了对最近插入的项目的引用。这个策略允许我们在链接列表的开头添加和删除项目，而不用访问链接列表中任何其他项目的链接。

链接列表中字符串堆栈的实现。LinkedStackOfStrings.java使用一个链接列表来实现字符串的堆栈。这个实现是基于一个嵌套的类Node，就像我们一直在使用的那个。Java允许我们以这种自然的方式在类的实现中定义和使用其他类。我们把嵌套类指定为私有，因为客户不需要知道链表的任何细节。

使用字符串的链接列表实现堆栈的痕迹

通用堆栈的链接列表实现。Stack.java使用一个单链表实现了一个通用堆栈。队列。一个队列支持使用先进先出（FIFO）规则的插入和删除操作。按照惯例，我们将队列的插入操作命名为enqueue，删除操作命名为dequeue，如下面的API所示。

LIFO队列的API

队列的链接列表实现。Queue.java使用一个链表实现了一个字符串的先进先出队列。像Stack一样，我们首先维护一个对队列中最近添加的最小节点的引用。为了提高效率，我们也对队列中最近添加的节点保持一个引用。

插入队列

调整队列中数组的大小实现。ResizingArrayQueue.java使用一个调整大小的数组实现了一个队列。它类似于ResizingArrayStack.java，但更棘手，因为我们需要从数组的两端添加和删除项目。

使用数组实现队列的轨迹

通用性。我们已经开发了堆栈的实现，允许我们建立一个特定类型的堆栈，比如说String。Java中的一种特殊机制被称为泛型，它使我们能够建立由客户代码指定类型的对象集合。

实现一个泛型集合。为了实现一个泛型集合，我们在角括号中指定一个类型参数，如 Item，并在我们的实现中使用该类型参数而不是一个特定的类型。例如，Stack.java是LinkedStackOfStrings.java的通用版本。

使用一个泛型集合。要使用一个泛型集合，客户端必须在创建堆栈时指定类型参数。

Stack stack = new Stack ();

自动排版。我们已经将我们的堆栈设计成通用的，因此它们是任何类型的对象。被称为自动装箱和拆箱的Java语言特性使我们也能用原始类型重复使用通用代码。Java提供了被称为包装类型的内置对象类型，每种原始类型都有一个。布尔型、整数型、双数型、字符型，等等。Java会自动在这些引用类型和相应的原始类型之间进行转换，这样我们就可以写出像下面这样的代码。

Stack<Integer> stack = new Stack<Integer>();
stack.push(17);            
  // autoboxing  (int -> Integer)
int a = stack.pop();       
  // unboxing    (Integer -> int))

迭代。有时，客户端需要访问一个集合的所有项目，一次一个，而不删除它们。为了保持封装性，我们不想向客户端透露队列的内部表示（数组或链表）。为了适应这种设计模式，Java提供了foreach语句。你应该把下面代码片段中的for语句解释为对于集合中的每个字符串s，打印s。

Stack collection = new Stack();
...
for (String s : stack)
    StdOut.println(s)

以这种方式实现一个支持迭代的集合需要实现Java的java.util.Iterator和java.util.Iterable接口。详见教科书。

堆栈和队列的应用。堆栈和队列有许多有用的应用。

算术表达式评估。堆栈的一个重要应用是在解析中。例如，编译器必须解析使用infix符号编写的算术表达式。例如，下面这个infix表达式的值是212。

( 2 + ( ( 3 + 4 ) * ( 5 * 6 ) ) )

Evaluate.java评估了一个完全括号化的算术表达式。

函数调用的抽象性。大多数程序隐含地使用堆栈，因为它们支持一种实现函数调用的自然方式，如下所示：在一个函数的执行过程中的任何一点，将其状态定义为其所有变量的值和一个指向下一条要执行的指令的指针。实现函数调用抽象的自然方法是使用一个堆栈。要调用一个函数，把状态推到堆栈上。要从函数调用中返回，从堆栈中弹出状态，将所有变量恢复到函数调用前的值，并在下一条要执行的指令中恢复执行。

M/M/1队列。最重要的排队模型之一被称为M/M/1队列，它已被证明能准确地模拟许多真实世界的情况。它的特点是有三个特性。

有一个服务器--FIFO队列。队列的到达时间服从指数分布，速率为每分钟λ。非空队列的服务时间服从指数分布，速率为每分钟μ。 MM1Queue.java模拟了一个M/M/1队列，并绘制了一个等待时间的直方图，以标准画法表示。

负载平衡。LoadBalance.java模拟了将n个项目分配给一组m个服务器的过程。对于每个项目，它选择s个服务器的样本，并将项目分配给当前项目最少的服务器。

练习给ArrayStackOfStrings.java添加一个方法isFull()。写一个过滤器Reverse.java，从标准输入中一个一个地读取字符串，并按相反的顺序打印到标准输出。写一个堆栈客户端Parentheses.java，它从标准输入中读取一串小括号、方括号和大括号，并使用堆栈来确定它们是否正确平衡。例如，你的程序应该为[()]{}{()()}打印真，为[(]打印假。）当n为50时，下面的代码片段会打印什么？给出一个高层次的描述，说明当出现正整数n时，该代码片段做了什么。

Stack stack = new Stack();
while (n > 0) {
    stack.push(n % 2);
    n /= 2;
}
while (!stack.isEmpty())
     StdOut.print(stack.pop())。
StdOut.println()

解决方案：打印n的二进制表示（当n为50时，110010）。

下面的代码片段对队列队列做了什么？

Stack stack = new Stack();
while (!queue.isEmpty())
   stack.push(queue.dequeue())
while (!stack.isEmpty())
   queue.enqueue(stack.pop())

解决方案：颠倒队列中的字符串的顺序。

在Stack.java中添加一个方法peek()，返回栈上最近插入的元素（不删除）。在Queue.java和Stack.java中都添加一个方法size()，返回集合中的项目数。

编写一个过滤器InfixToPostfix.java，将一个算术表达式从infix转换为postfix。编写一个EvaluatePostfix.java程序，从标准输入中获取一个后缀表达式，对其进行评估，并打印出数值。(把你在前面练习中的程序的输出连接到这个程序中，可以得到与Evaluate.java相当的行为。)

开发一个数据类型ResizingArrayQueueOfStrings.java，实现一个固定长度数组的队列，使所有操作都需要恒定时间。

修改MM1Queue.java，使程序MD1Queue.java模拟一个服务时间固定（确定性）的队列，速度为μ。验证这个模型的利特尔定律。

开发一个StackOfInts.java类，使用链接列表表示（但没有泛型）来实现一个整数堆栈。编写一个客户端，将你的实现与Stack 的性能进行比较，以确定你的系统中自动装箱和拆箱的性能损失。

链接列表练习

假设x是一个链接列表的节点。下面的代码片段有什么作用？

x.next = x.next.next

解决方案。从列表中删除紧随x的节点。

写一个方法delete()，它接收一个链表中的第一个节点和一个int参数k，并删除链表中的第k个节点，如果它存在的话。解决方案。

我们假设first是对列表中第一个Node的引用


// we assume that first is a reference to the first Node in the list
public void delete(int k) {
    if (k <= 0) throw new RuntimeException("Invalid value of k");

    // degenerate case - empty linked list
    if (first == null) return;

    // special case - removing the first node
    if (k == 1) {
        first = first.next;
        return;
    }

    // general case, make temp point to the (k-1)st node
    Node temp = first;
    for (int i = 2; i < k; i++) {
        temp = temp.next;
        if (temp == null) return;   // list has < k nodes
    }

    if (temp.next == null) return;  // list has < k nodes

    // change temp.next to skip kth node
    temp.next = temp.next.next;
}

假设x是一个链接列表的节点。下面的代码片段会有什么影响？

t.next = x.next
x.next = t

解决方案。在节点x之后立即插入节点t。

为什么下面的代码片段与上一个问题的效果不一样？

x.next = t
t.next = x.next

解决方案。当需要更新t.next时，x.next不再是x后面的原始节点，而是t本身

创意练习

约瑟夫斯问题。在古代的约瑟夫问题中，N个人处于困境中，他们同意采取以下策略来减少人口。他们把自己安排在一个圆圈里（位置从0到n-1编号），然后绕着圆圈前进，每消灭一个人，直到只剩下一个人。传说中，约瑟夫斯想出了坐在哪里才能避免被淘汰。编写一个队列客户端Josephus.java，它接受两个整数的命令行参数m和n，并打印出人们被淘汰的顺序（因此会显示Josephus在圈中的位置）。

拓扑学排序。你必须对服务器上编号为0到n-1的n个作业的顺序进行排序。一些工作必须在其他工作开始之前完成。编写一个TopologicalSorter.java程序，它接受一个命令行参数n和标准输入的有序工作对（i，j）的序列，然后打印出一个整数序列，使得对于输入的每一对（i，j），工作i出现在工作j之前。首先，从输入中，为每个工作建立（1）一个必须跟随它的工作队列和（2）它的indegree（必须在它之前的工作数量）。

然后，建立一个indegree为0的所有节点的队列，并重复删除任何indegree为0的工作，保持所有的数据这个过程有很多应用。例如，你可以用它来模拟你的专业的课程先决条件，这样你就可以找到一个需要学习的课程序列，这样你就可以毕业。为一个堆栈复制构造函数。

为Stack.java的链接列表实现创建一个新的构造函数，使Stack t = new Stack (s)使t引用一个新的、独立的堆栈s的副本，你应该能够从s或t推送和弹出而不影响另一个。

递归解决方案：为一个Node创建一个拷贝构造函数，并使用它来创建新的堆栈。

public Node(Node x) {
    item = x.item。
    if (x.next != null)
        next = new Node(x.next)。
}

public Stack(Stack s) {
    first = new Node(s.first);
}

非递归解决方案（未经测试）。

public Node(Node x, Node next) {
    this.x = x;
    this.next = next;
}

public Stack(Stack s) {
   if (s.first != null) {
      first = new Node(s.first.value, s.first.next) {
      for (Node x = first; x.next != null; x = x.next)
         x.next = new Node(x.next.value, x.next.next);
   }
}

报价开发一个数据类型Quote.java，实现以下API。

报价API 为此，定义一个嵌套类Card，该类持有报价单中的一个词和一个指向报价单中下一个词的链接。

private class Card {
    private String word;
    private Card next;

    public Card(String word) {
        this.word = word;
        this.next = null;
    }
}

循环引用。重复前面的练习，但使用一个循环链接列表。在循环链接列表中，每个节点都指向它的后继者，列表中的最后一个节点指向第一个节点（而不是像标准的空端链接列表那样指向空端）。

解决方案 CircularQuote.java

反转一个链表（迭代）。编写一个非递归函数，将链表中的第一个节点作为参数，并反转该链表，返回结果中的第一个节点。

解决方案。为了达到这个目的，我们保持对链表中三个连续节点的引用，即反向、第一和第二。在每个迭代中，我们从原始链表中提取第一个节点，并将其插入到反转列表的开头。我们保持不变的是，first是原始列表中剩下的第一个节点，second是原始列表中剩下的第二个节点，reverse是产生的反转列表的第一个节点。

反转一个链表

Reverse a linked list
public static Node reverse(Node list) {
    if (first == null || first.next == null) return first;
    Node first   = list;
    Node reverse = null;
    while (first != null) {
        Node second = first.next;
        first.next  = reverse;
        reverse     = first;
        first       = second;
    }
    return reverse;
}

反转一个链接列表（递归）。编写一个递归函数，将一个链接列表中的第一个节点作为参数并反转该列表，返回结果中的第一个节点。

解决方案。假设链接列表有n个元素，我们递归反转最后的n-1个元素，然后将第一个元素附加到最后。

public Node reverse(Node first) {
    if (first == null || first.next == null) return first;
    Node second = first.next;
    Node rest = reverse(second);
    second.next = first;
    first.next  = null;
    return rest;
}

列出文件。一个文件夹是一个文件和文件夹的列表。编写一个Directory.java程序，将一个文件夹的名称作为命令行参数，并打印出该文件夹中包含的所有文件，每个文件夹的内容在该文件夹的名称下递归列出（缩进）。

网络练习写一个递归函数，将一个队列作为输入，并将其重新排列，使其处于相反的顺序。提示：dequeue()第一个元素，递归反转队列，然后enqueue第一个元素。在Stack中添加一个方法Item[] multiPop(int k)，从堆栈中弹出k个元素，并将它们作为一个对象数组返回。

在Queue中添加一个方法Item[] toArray()，将队列中的所有N个元素作为一个长度为N的数组返回。下面的代码片段是做什么的？

IntQueue q = new IntQueue();
q.enqueue(0);
q.enqueue(1);
for (int i = 0; i < 10; i++) {
    int a = q.dequeue();
    int b = q.dequeue();
    q.enqueue(b)。
    q.enqueue(a + b)。
    System.out.println(a)。
}

斐波那契

你会选择什么数据类型来实现文字处理器中的 "撤销 "功能？假设你有一个大小为N的单数组，并想实现两个堆栈，以便在两个堆栈的元素总数为N+1之前不会出现溢出。你将如何进行？假设你在StackList的链表实现中用下面的代码实现了推送。错误是什么？

public void push(Object value) {
   Node second = first;
   Node first = new Node();
   first.value = value。
   first.next = second;
}

解决方案。通过重新声明first，你创建了一个新的局部变量，命名为first，这与名为first的实例变量不同。

使用一个队列的堆栈。展示如何使用一个队列实现一个堆栈。提示：要删除一个项目，要逐个获取队列中的所有元素，并把它们放在最后，除了最后一个，你应该删除并返回。

用一个堆栈列出文件。写一个程序，将一个目录的名称作为命令行参数，并打印出这个目录和任何子目录中包含的所有文件。同时打印出每个文件的文件大小（以字节为单位）。

使用堆栈而不是队列。重复使用递归并将你的程序命名为DirectoryR.java。修改DirectoryR.java，使其打印出每个子目录和它的总大小。一个目录的大小等于它所包含的所有文件或其子目录所包含的文件的总和。

堆栈+最大。创建一个数据结构，有效地支持堆栈操作（pop和push），同时返回最大元素。假设元素是整数或实数，这样你就可以比较它们。提示：使用两个堆栈，一个用来存储所有的元素，第二个堆栈用来存储最大的元素。

标签系统。编写一个程序，从命令行中读入一个二进制字符串，并应用以下(00, 1101)标签系统：如果第一位是0，删除前三位并附加00；如果第一位是1，删除前三位并附加1101。只要字符串至少有3位，就重复上述操作。试着确定以下输入是否会停止或进入无限循环。10010, 100100100100100100. 使用一个队列。

一组整数。创建一个数据类型，代表0到n-1之间的一组整数（没有重复）。

支持

add(i),
exists(i), 
remove(i), 
size(), 
intersect, 
difference, 
symmetricDifference, 
union,
 isSubset,
 isSuperSet,
 isDisjointFrom。

为一本书编制索引。编写一个程序，从标准输入中读入一个文本文件，并编制一个按字母顺序排列的索引，说明哪些词出现在哪一行，如以下输入。忽略大小写和标点符号。

                   与FrequencyCount类似，但对每个词都要保持一个它出现的位置列表。

拷贝构造函数，用于实现堆栈的大小调整阵列。在ArrayStackOfStrings.java中添加一个拷贝构造函数。重新排序链表。给定一个包含2n个节点的单链表x1->x2->...->x_2n，将节点重新排列为x1->x2n->x2->x_2n-1->x3->.... 提示：将链接列表分成两半；将第二个链接列表中的节点顺序颠倒；将两个列表合并在一起。