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

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

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

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

本节开头已经提过,集合类数据类型的基本操作之一就是,能够使用 Java 的 foreach 语句通过迭代遍历并处理集合中的每个元素。这种方式的代码既清晰又简洁,且不依赖于集合数据类型的具体实现。在讨论迭代的实现之前,我们先看一段能够打印出一个字符串集合中的所有元素的用例代码:

复制代码
Stack<String> collection = new Stack<String>();
...
for (String s : collection)
StdOut.println(s);
...

这里,foreach 语句只是 while 语句的一种简写方式(就好像 for 语句一样)。它本质上和以下 while 语句是等价的:

复制代码
Iterator<String> i = collection.iterator();
while (i.hasNext())
{
String s = i.next();
StdOut.println(s);
}

这段代码展示了一些在任意可迭代的集合数据类型中我们都需要实现的东西:

  • 集合数据类型必须实现一个 iterator() 方法并返回一个 Iterator 对象;
  • Iterator 类必须包含两个方法:hasNext()(返回一个布尔值)和next()(返回集合中的一个泛型元素)。

在 Java 中,我们使用接口机制来指定一个类所必须实现的方法(请见 1.2.5.4 节)。对于可迭代的集合数据类型,Java 已经为我们定义了所需的接口。要使一个类可迭代,第一步就是在它的声明中加入 implements Iterable<Item>,对应的接口(即 java.lang.Iterable)为:

复制代码
public interface Iterable<Item>
{
Iterator<Item> iterator();
}

然后在类中添加一个方法 iterator() 并返回一个迭代器 Iterator<Item>。迭代器都是泛型的,因此我们可以使用参数类型 Item 来帮助用例遍历它们指定的任意类型的对象。对于一直使用的数组表示法,我们需要逆序迭代遍历这个数组,因此我们将迭代器命名为 ReverseArrayIterator,并添加了以下方法:

复制代码
public Iterator<Item> iterator()
{ return new ReverseArrayIterator(); }

迭代器是什么?它是一个实现了 hasNext()next() 方法的类的对象,由以下接口所定义(即 java.util.Iterator):

复制代码
public interface Iterator<Item>
{
boolean hasNext();
Item next();
void remove();
}

尽管接口指定了一个remove() 方法,但在本书中remove() 方法总为空,因为我们希望避免在迭代中穿插能够修改数据结构的操作。对于 ReverseArrayIterator,这些方法都只需要一行代码,它们实现在栈类的一个嵌套类中:

复制代码
private class ReverseArrayIterator implements Iterator<Item>
{
private int i = N;
public boolean hasNext() { return i > 0; }
public Item next() { return a[--i]; }
public void remove() { }
}

请注意,嵌套类可以访问包含它的类的实例变量,在这里就是a[]N(这也是我们使用嵌套类实现迭代器的主要原因)。从技术角度来说,为了和 Iterator 的结构保持一致,我们应该在两种情况下抛出异常:如果用例调用了 remove() 则抛出UnsupportedOperationException,如果用例在调用next()i 为 0 则抛出NoSuchElementException。因为我们只会在foreach 语法中使用迭代器,这些情况都不会出现,所以我们省略了这部分代码。还剩下一个非常重要的细节,我们需要在程序的开头加上下面这条语句:

复制代码
import java.util.Iterator;

因为(某些历史原因)Iterator 不在 java.lang 中(尽管 Iterable java.lang 的一部分)。现在,使用 foreach 处理该类的用例能够得到的行为和使用普通的 for 循环访问数组一样,但它无须知道数据的表示方法是数组(即实现细节)。对于我们在本书中学习的和 Java 库中所包含的所有类似于集合的基础数据类型的实现,这一点非常重要。例如,我们无需改变任何用例代码就可以随意切换不同的表示方法。更重要的是,从用例的角度来来说,无需知晓类的实现细节用例也能使用迭代。

算法 1.1 是 Stack API 的一种能够动态改变数组大小的实现。用例能够创建任意类型数据的栈,并支持用例用 foreach 语句按照后进先出的顺序迭代访问所有栈元素。这个实现的基础是 Java 的语言特性,包括 IterableIterator,但我们没有必要深究这些特性的细节,因为代码本身并不复杂,并且可以用做其他集合数据类型的实现的模板。

例如,我们在实现 Queue 的 API 时,可以使用两个实例变量作为索引,一个变量 head 指向队列的开头,一个变量 tail 指向队列的结尾,如表 1.3.6 所示。在删除一个元素时,使用 head 访问它并将 head 加 1;在插入一个元素时,使用 tail 保存它并将 tail 加 1。如果某个索引在增加之后越过了数组的边界则将它重置为 0。实现检查队列是否为空、是否充满并需要调整数组大小的细节是一项有趣而又实用的编程练习(请见练习 1.3.14)。

表 1.3.6 ResizingArrayQueue 的测试用例的轨迹

StdIn
(入列)
StdOut
(出列)
Nheadtaila[]
01234567
505tobeornotto
-to415tobeornotto
be516tobeornottobe
-be426tobeornottobe
-or336tobeornottobe

在算法的学习中,算法 1.1 十分重要,因为它几乎(但还没有)达到了任意集合类数据类型的实现的最佳性能:

  • 每项操作的用时都与集合大小无关;
  • 空间需求总是不超过集合大小乘以一个常数。

ResizingArrayStack 的缺点在于某些 push()pop() 操作会调整数组的大小:这项操作的耗时和栈大小成正比。下面,我们将学习一种克服该缺陷的方法,使用一种完全不同的方式来组织数据。

算法 1.1 下压(LIFO)栈(能够动态调整数组大小的实现)

复制代码
import java.util.Iterator;
public class ResizingArrayStack<Item> implements Iterable<Item>
{
private Item[] a = (Item[]) new Object[1]; // 栈元素
private int N = 0; // 元素数量
public boolean isEmpty() { return N == 0; }
public int size() { return N; }
private void resize(int max)
{ // 将栈移动到一个大小为 max 的新数组
Item[] temp = (Item[]) new Object[max];
for (int i = 0; i < N; i++)
temp[i] = a[i];
a = temp;
}
public void push(Item item)
{ // 将元素添加到栈顶
if (N == a.length) resize(2*a.length);
a[N++] = item;
}
public Item pop()
{ // 从栈顶删除元素
Item item = a[--N];
a[N] = null; // 避免对象游离(请见 1.3.2.4 节)
if (N > 0 && N == a.length/4) resize(a.length/2);
return item;
}
public Iterator<Item> iterator()
{ return new ReverseArrayIterator(); }
private class ReverseArrayIterator implements Iterator<Item>
{ // 支持后进先出的迭代
private int i = N;
public boolean hasNext() { return i > 0; }
public Item next() { return a[--i]; }
public void remove() { }
}
}

这份泛型的可迭代的 Stack API 的实现是所有集合类抽象数据类型实现的模板。它将所有元素保存在数组中,并动态调整数组的大小以保持数组大小和栈大小之比小于一个常数。

评论

发布