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

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

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

(集合类数据类型的实现:调整数组大小)

选择用数组表示栈内容意味着用例必须预先估计栈的最大容量。在 Java 中,数组一旦创建,其大小是无法改变的,因此栈使用的空间只能是这个最大容量的一部分。选择大容量的用例在栈为空或几乎为空时会浪费大量的内存。例如,一个交易系统可能会涉及数十亿笔交易和数千个交易的集合。即使这种系统一般都会限制每笔交易只能出现在一个集合中,但用例必须保证所有集合都有能力保存所有的交易。另一方面,如果集合变得比数组更大那么用例有可能溢出。为此,push() 方法需要在代码中检测栈是否已满,我们的 API 中也应该含有一个 isFull() 方法来允许用例检测栈是否已满。我们在此省略了它的实现代码,因为我们希望用例从处理栈已满的问题中解脱出来,如我们的原始 Stack API 所示。因此,我们修改了数组的实现,动态调整数组a[] 的大小,使得它既足以保存所有元素,又不至于浪费过多的空间。实际上,完成这些目标非常简单。首先,实现一个方法将栈移动到另一个大小不同的数组中:

复制代码
private void resize(int max)
{ // 将大小为 N < = max 的栈移动到一个新的大小为 max 的数组中
Item[] temp = (Item[]) new Object[max];
for (int i = 0; i < N; i++)
temp[i] = a[i];
a = temp;
}

现在,在push() 中,检查数组是否太小。具体来说,我们会通过检查栈大小 N 和数组大小 a.length 是否相等来检查数组是否能够容纳新的元素。如果没有多余的空间,我们会将数组的长度加倍。然后就可以和从前一样用 a[N++] = item 插入新元素了:

复制代码
public void push(Item item)
{ // 将元素压入栈顶
if (N == a.length) resize(2*a.length);
a[N++] = item;
}

类似,在 pop() 中,首先删除栈顶的元素,然后如果数组太大我们就将它的长度减半。只要稍加思考,你就明白正确的检测条件是栈大小是否小于数组的四分之一。在数组长度被减半之后,它的状态约为半满,在下次需要改变数组大小之前仍然能够进行多次 push()pop() 操作。

复制代码
public Item pop()
{ // 从栈顶删除元素
Item item = a[--N];
a[N] = null; // 避免对象游离(请见下节)
if (N > 0 && N == a.length/4) resize(a.length/2);
return item;
}

在这个实现中,栈永远不会溢出,使用率也永远不会低于四分之一(除非栈为空,那种情况下数组的大小为 1)。我们会在 1.4 节中详细分析这种实现方法的性能特点。

push()pop() 操作中数组大小调整的轨迹见表 1.3.5。

表 1.3.5 一系列 push()pop() 操作中数组大小调整的轨迹

push()pop()Na.lengtha[]
01234567
01null
to11to
be22tobe
or34tobeornull
not44tobeornot
to58tobeornottonullnullnull
-to48tobeornotnullnullnullnull
be58tobeornotbenullnullnull
-be48tobeornotnullnullnullnull
-not38tobeornullnullnullnullnull
that48tobeorthatnullnullnullnull
-that38tobeornullnullnullnullnull
-or24tobenullnull
-be12tonull
is22tois

评论

发布