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

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

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

(集合类数据类型的实现:泛型)

FixedCapacityStackOfStrings 的第一个缺点是它只能处理 String 对象。如果需要一个 double 值的栈,你就需要用类似的代码实现另一个类,也就是把所有的 String 都替换为 double。这还算简单,但如果我们需要 Transaction 类型的栈或者 Date 类型的队列等,情况就很棘手了。如 1.3.1.1 节的讨论所示,Java 的参数类型(泛型)就是专门用来解决这个问题的,而且我们也看过了几个用例的代码(请见 1.3.1.4 节、1.3.1.5 节、1.3.1.6 节和 1.3.1.7 节)。但如何才能实现一个泛型的栈呢?表 1.3.4 中的代码展示了实现的细节。它实现了一个 FixedCapacityStack 类,该类和 FixedCapacityStackOfStrings 类的区别仅在于加粗部分的代码——我们把所有的 String 都替换为 Item(一个地方除外,会在稍后讨论)并用下面这行代码声明了该类:

复制代码
public class FixedCapacityStack<Item>

Item 是一个类型参数,用于表示用例将会使用的某种具体类型的象征性的占位符。可以将 FixedCapacityStack<Item> 理解为某种元素的栈,这正是我们想要的。在实现 FixedCapacityStack 时,我们并不知道 Item 的实际类型,但用例只要能在创建栈时提供具体的数据类型,它就能用栈处理任意数据类型。实际的类型必须是引用类型,但用例可以依靠自动装箱将原始数据类型转换为相应的封装类型。Java 会使用类型参数 Item 来检查类型不匹配的错误——尽管具体的数据类型还不知道,赋予 Item 类型变量的值也必须是 Item 类型的,等等。在这里有一个细节非常重要:我们希望用以下代码在 FixedCapacityStack 的构造函数的实现中创建一个泛型的数组:

复制代码
a = new Item[cap];

由于某些历史和技术原因(不在本书讲解范围之内),创建泛型数组在 Java 中是不允许的。我们需要使用类型转换:

复制代码
a = (Item[]) new Object[cap];

这段代码才能够达到我们所期望的效果(但 Java 编译器会给出一条警告,不过可以忽略它),我们在本书中会一直使用这种方式(Java 系统库中类似抽象数据类型的实现中也使用了相同的方式)。

表 1.3.4 一种表示泛型定容栈的抽象数据类型

APIpublic class FixedCapacityStack<Item>
              FixedCapacityStack(int cap)创建一个容量为 cap 的空栈
       void   push(Item item)添加一个元素
       Item   pop()删除最近添加的元素
    boolean   isEmpty()栈是否为空
        int   size()栈中的元素数量
测试用例
public static void main(String[] args)
{
FixedCapacityStack<String> s;
s = new FixedCapacityStack<String>(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 FixedCapacityStack < tobe.txt
to be not that or be (2 left on stack)

数据类型的实现
public class FixedCapacityStack<Item>
{
private Item[] a; // stack entries
private int N; // size
public FixedCapacityStack(int cap)
{ a = (Item[]) new Object[cap]; }
public boolean isEmpty() { return N == 0; }
public int size() { return N; }
public void push(Item item)
{ a[N++] = item; }
public Item pop()
{ return a[--N]; }
}

评论

发布