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

阅读数:27 2019 年 11 月 6 日 07:41

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

(答疑)

 并不是所有编程语言都支持泛型,甚至 Java 的早期版本也不支持。有其他替代方案吗?

 如正文所述,一种替代方法是为每种类型的数据都实现一个不同的集合数据类型。另一种方法是构造一个 Object 对象的栈,并在用例中使用 pop() 时将得到的对象转换为所需的数据类型。这种方式的问题在于类型不匹配错误只能在运行时发现。而在泛型中,如果你的代码将错误类型的对象压入栈中,比如这样:

复制代码
Stack<Apple> stack = new Stack<Apple>();
Apple a = new Apple();
...
Orange b = new Orange();
...
stack.push(a);
...
stack.push(b); // 编译时错误

会得到一个编译时错误:

复制代码
push(Apple) in Stack<Apple> cannot be applied to (Orange)

能够在编译时发现错误足以说服我们使用泛型。

 为什么 Java 不允许泛型数组?

 专家们仍然在争论这一点。你可能也需要成为专家才能理解它!对于初学者,请先了解共变数组(covariant array)和类型擦除(type erasure)。

 如何才能创建一个字符串栈的数组?

 使用类型转换,比如:

复制代码
Stack<String>[] a = (Stack<String>[]) new Stack[N];

警告:这段类型转换的用例代码和 1.3.2.2 节所示的有所不同。你可能会以为需要使用Object 而非 Stack。在使用泛型时,Java 会在编译时检查类型的安全性,但会在运行时抛弃所有这些信息。因此在运行时语句右侧就变成了Stack<Object>[] 或者只剩下了 Stack[],因此我们必须将它们转化为 Stack<String>[]

 在栈为空时调用 pop() 会发生什么?

 这取决于实现。对于我们在算法 1.2 中给出的实现,你会得到一个 NullPointerException 异常。对于我们在本书的网站上给出的实现,我们会抛出一个运行时异常以帮助用户定位错误。一般来说,在应用广泛的代码中这类检查越多越好。

 既然有了链表,为什么还要学习如何调整数组的大小?

 我们还将会学习若干抽象数据类型的示例实现,它们需要使用数组来实现一些链表难以实现的操作。ResizingArrayStack 是控制它们的内存使用的样板。

 为什么将 Node 声明为嵌套类?为什么使用 private

 将 Node 声明为私有的嵌套类之后,我们可以将Node 的方法和实例变量的访问范围限制在包含它的类中。私有嵌套类的一个特点是只有包含它的类能够直接访问它的实例变量,因此无需将它的实例变量声明为public 或是 private。专业背景较强的读者注意:非静态的嵌套类也被称为内部类,因此从技术上来说我们的Node 类也是内部类,尽管非泛型的类也可以是静态的。

 当我输入 javac Stack.java 编译算法 1.2 和其他程序时,我发现了 Stack.class 和 Stack$Node.class 两个文件。第二个文件是做什么用的?

 第二个文件是为内部类 Node 创建的。Java 的命名规则会使用 $ 分隔外部类和内部类。

 Java 标准库中有栈和队列吗?

 有,也没有。Java 有一个内置的库,叫做 java.util.Stack,但你需要栈的时候请不要使用它。它新增了几个一般不属于栈的方法,例如获取第 i 个元素。它还允许从栈底添加元素(而非栈顶),所以它可以被当做队列使用!尽管拥有这些额外的操作看起来可能很有用,但它们其实是累赘。我们使用某种数据类型不仅仅是为了获得我们能够想象的各种操作,也是为了准确地指定我们所需要的操作。这么做的主要好处在于系统能够防止我们执行一些意外的操作。java.util.Stack 的 API 是宽接口的一个典型例子,我们通常会极力避免出现这种情况。

 是否允许用例向栈或队列中添加空(null)元素?

 在 Java 中实现集合类数据类型时这个问题是很常见的。我们的实现(以及 Java 的栈和队列库)允许插入 null 值。

 如果用例在迭代中调用 push() 或者 pop()Stack 的迭代器应该怎么办?

 作为一个快速出错的迭代器,它应该立即抛出一个java.util.ConcurrentModificationException 异常。请见练习 1.3.50。

 我们能够用 foreach 循环访问数组吗?

 可以(尽管数组没有实现 Iterable 接口)。以下代码将会打印所有命令行参数:

复制代码
public static void main(String[] args)
{ for (String s : args) StdOut.println(s); }

 我们能够用 foreach 循环访问字符串吗?

 不行,String 没有实现 Iterable 接口。

 为什么不实现一个单独的 Collection 数据类型并实现添加元素、删除最近插入的元素、删除最早插入的元素、删除随机元素、迭代、返回集合元素数量和其他我们可能需要的方法?这样我们就能在一个类中实现所有这些方法并可以应用于各种用例。

 再次强调一遍,这又是一个宽接口的例子。Java 在java.util.ArrayListjava.util.LinkedList 类中实现了类似的设计。避免使用它们的一个原因是这样无法保证高效实现所有这些方法。在本书中,我们总是以 API 作为设计高效算法和数据结构的起点,而设计只含有几个操作的接口显然比设计含有许多操作的接口更简单。我们坚持窄接口的另一个原因是它们能够限制用例的行为,这将使用例代码更加易懂。如果一段用例代码使用 Stack<String>,而另一段用例代码使用 Queue<Transaction>,我们就可以知道后进先出的访问顺序对于前者很重要,而先进先出的访问顺序对于后者很重要。

评论

发布