算法(4th ed)(138):基础——背包、队列和栈 5.3.9

阅读数:13 2019 年 11 月 6 日 07:35

算法(4th ed)(138):基础——背包、队列和栈 5.3.9

(链表:队列的实现)

基于链表数据结构实现 Queue API 也很简单,如算法 1.3 所示。它将队列表示为一条从最早插入的元素到最近插入的元素的链表,实例变量 first 指向队列的开头,实例变量last 指向队列的结尾。这样,要将一个元素入列(enqueue()),我们就将它添加到表尾(请见图 1.3.8 中讨论的代码,但是在链表为空时需要将 firstlast 都指向新结点);要将一个元素出列(dequeue()),我们就删除表头的结点(代码和Stackpop() 方法相同,只是当链表为空时需要更新last 的值)。size()isEmpty() 方法的实现和 Stack 相同。和 Stack 一样,Queue 的实现也使用了泛型参数 Item。这里我们省略了支持迭代的代码并将它们留到算法 1.4 中继续讨论。下面所示的是一个开发用例,它和我们在Stack 中使用的用例很相似,它的轨迹如算法 1.3 所示。Queue 的实现使用的数据结构Stack 相同——链表,但它实现了不同的添加和删除元素的算法,这也是用例所看到的后进先出和先进后出的区别所在。和刚才一样,我们用链表达到了最优设计目标:它可以处理任意类型的数据,所需的空间总是和集合的大小成正比,操作所需的时间总是和集合的大小无关。1

1 这里原书应该是因为版面原因没有使用列表,如果版面允许可以使用和 Stack 部分相同的列表显示这三个目标。——译者注

复制代码
public static void main(String[] args)
{ // 创建一个队列并操作字符串入列或出列
Queue<String> q = new Queue<String>();
while (!StdIn.isEmpty())
{
String item = StdIn.readString();
if (!item.equals("-"))
q.enqueue(item);
else if (!q.isEmpty()) StdOut.print(q.dequeue() + " ");
}
StdOut.println("(" + q.size() + " left on queue)");
}
`Queue` 的测试用例
复制代码
% more tobe.txt
to be or not to - be - - that - - - is
% java Queue < tobe.txt
to be or not to be (2 left on queue)

算法 1.3 先进先出队列
算法(4th ed)(138):基础——背包、队列和栈 5.3.9
这份泛型的Queue 实现的基础是链表数据结构。它可以用于创建任意数据类型的队列。要支持迭代,请添加算法 1.4 中为Bag 数据类型给出的加粗部分的代码。

Queue 的开发用例的轨迹如图 1.3.10 所示。

算法(4th ed)(138):基础——背包、队列和栈 5.3.9

图 1.3.10 Queue 的开发用例的轨迹

在结构化存储数据集时,链表是数组的一种重要的替代方式。这种替代方案已经有数十年的历史。事实上,编程语言历史上的一块里程碑就是 McCathy 在 20 世纪 50 年代发明的 LISP 语言,而链表则是这种语言组织程序和数据的主要结构。在练习中你会发现,链表编程也会遇到各种问题,且调试十分困难。在现代编程语言中,安全指针、自动垃圾回收(请见 1.2 节答疑部分)和抽象数据类型的使用使我们能够将链表处理的代码封装在若干个类中,正如本文所述。

评论

发布