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

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

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

(集合类数据类型的实现:定容栈)

作为热身,我们先来看一种表示容量固定的字符串栈的抽象数据类型,如表 1.3.2 所示。它的 API 和 Stack 的 API 有所不同:它只能处理 String 值,它要求用例指定一个容量且不支持迭代。实现一份 API 的第一步就是选择数据的表示方式。对于 FixedCapacityStackOfStrings,我们显然可以选择 String 数组。由此我们可以得到表 1.3.2 中底部的实现,它已经是简单得不能再简单了(每个方法都只有一行)。它的实例变量为一个用于保存栈中的元素的数组a[],和一个用于保存栈中的元素数量的整数N。要删除一个元素,我们将 N1 并返回 a[N]。要添加一个元素,我们将 a[N] 设为新元素并将 N1。这些操作能够保证以下性质:

表 1.3.2 一种表示定容字符串栈的抽象数据类型

APIpublic class FixedCapacityStackOfStrings
           FixedCapacityStackOfStrings(int cap)创建一个容量为 cap 的空栈
    void   push(String item)添加一个字符串
  String   pop()删除最近添加的字符串
 boolean   isEmpty()栈是否为空
     int   size()栈中的字符串数量
测试用例
public static void main(String[] args)
{
FixedCapacityStackOfStrings s;
s = new FixedCapacityStackOfStrings(100);
while (!StdIn.isEmpty())
{
String item = StdIn.readString();
if (!item.equals("-"))
s.push(item);
else if (!s.isEmpty()) StdOut.print(s.pop() + " ");
}
StdOut.println("(" + s.size() + " left on stack)");
}

使用方法
% more tobe.txt
to be or not to - be - - that - - - is
% java FixedCapacityStackOfStrings < tobe.txt
to be not that or be (2 left on stack)

数据类型的实现
public class FixedCapacityStackOfStrings
{
private String[] a; // stack entries
private int N; // size
public FixedCapacityStackOfStrings(int cap)
{ a = new String[cap]; }
public boolean isEmpty() { return N == 0; }
public int size() { return N; }
public void push(String item)
{ a[N++] = item; }
public String pop()
{ return a[--N]; }
}
  • 数组中的元素顺序和它们被插入的顺序相同;
  • N 为 0 时栈为空;
  • 栈的顶部位于 a[N-1](如果栈非空)。

和以前一样,用恒等式的方式思考这些条件是检验实现正常工作的最简单的方式。请你务必完全理解这个实现。做到这一点的最好方法是检验一系列操作中栈内容的轨迹,如表 1.3.3 所示。测试用例会从标准输入读取多个字符串并将它们压入一个栈,当遇到 - 时它会将栈的内容弹出并打印结果。这种实现的主要性能特点是pushpop 操作所需的时间独立于栈的长度。许多应用会因为这种简洁性而选择它。但几个缺点限制了它作为通用工具的潜力,我们要改进的也是这一点。经过一些修改(以及 Java 语言机制的一些帮助),我们就能给出一个适用性更加广泛的实现。这些努力是值得的,因为这个实现是本书中其他许多更强大的抽象数据类型的模板。

表 1.3.3 FixedCapacityStackOfStrings 的测试用例的轨迹

StdIn
(push)
StdOut
(pop)
Na[]
01234
0
to1to
be2tobe
or3tobeor
not4tobeornot
to5tobeornotto
-to4tobeornotto
be5tobeornotbe
-be4tobeornotbe
-not3tobeornotbe
that4tobeorthatbe
-that3tobeorthatbe
-or2tobeorthatbe
-be1tobeorthatbe
is2toisornotto

评论

发布