什么是修改加维克算法？

Question

Garwick算法是一种处理堆栈溢出的算法。我知道原始算法是什么以及它是如何工作的。然而，修改了Garwick的算法，我对它有一个非常模糊的描述，“甚至堆栈向左增长，而奇堆栈向右”。

从我的讲义中修改后的算法的说明如下，它也很模糊。

谁能帮助提供更多的细节关于这个改进算法，或者提供一些参考？谢谢！

Answer 1

如果您需要将2个堆栈放在一个数组中，那么您可以在数组的起始处放置一个堆栈，随着元素的推进而向上增长，最后一个堆栈向下增长。

这样你就不需要担心重新分配空闲空间时，其中一个填满了，因为它们都使用相同的自由空间，你可以自由地推到要么堆栈，直到整个阵列充分。

您引用的修改的Garwick算法将此想法扩展到2个以上的堆栈。使用Garwick原始算法，阵列被分成N个区段，每个区段有一个堆栈，所有堆栈都在同一个方向上生长。在修改后的版本中，阵列被分成N/2个分段，每个分段都有一个堆栈，一个从段开始向上增长，另一个从结尾向下增长。

在修改后的算法中，当一个分段填满时，自由空间在分段（堆栈对）之间重新分配，与原始算法在单个堆栈间重新分配空间的方式相同。