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

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

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

(链表:栈的实现)

有了这些预备知识,给出我们的Stack API 的实现就很简单了,如 94 页的算法 1.2 所示。它将栈保存为一条链表,栈的顶部即为表头,实例变量 first 指向栈顶。这样,当使用 push() 压入一个元素时,我们会按照 1.3.3.3 节所讨论的代码将该元素添加在表头;当使用pop() 删除一个元素时,我们会按照 1.3.3.4 节讨论的代码将该元素从表头删除。要实现 size() 方法,我们用实例变量 N 保存元素的个数,在压入元素时将 N 加 1,在弹出元素时将 N 减 1。要实现 isEmpty() 方法,只需检查 first 是否为 null(或者可以检查 N 是否为 0)。该实现使用了泛型的 Item——你可以认为类名后的 <Item> 表示的是实现中所出现的所有 Item 都会替换为用例所提供的任意数据类型的名称(请见 1.3.2.2 节)。我们暂时省略了关于迭代的代码并将它们留到算法 1.4 中继续讨论。图 1.3.9 显示了我们所常用的测试用例的轨迹(测试用例代码放在了图后面)。链表的使用达到了我们的最优设计目标:

  • 它可以处理任意类型的数据;
  • 所需的空间总是和集合的大小成正比;
  • 操作所需的时间总是和集合的大小无关。

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

图 1.3.9 stack 的开发用例的轨迹

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

Stack 的测试用例

这份实现是我们对许多算法的实现的原型。它定义了链表数据结构并实现了供用例使用的方法 push()pop(),仅用了少量代码就取得了所期望的效果。算法和数据结构是相辅相成的。在本例中,算法的实现代码很简单,但数据结构的性质却并不简单,我们用了好几页纸来说明这些性质。这种数据结构的定义和算法的实现的相互作用很常见,也是本书中我们对抽象数据类型的实现重点。

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

复制代码
% more tobe.txt
to be or not to - be - - that - - - is
% java Stack < tobe.txt
to be not that or be (2 left on stack)

评论

发布