如何使用单个数组实现三个堆栈

Question

我在一个采访网站上遇到了这个问题.该问题要求在单个阵列中有效地实现三个堆栈,使得在整个阵列空间中没有剩余空间之前没有堆栈溢出.

为了在数组中实现2个堆栈,非常明显:第一个堆栈从LEFT变为RIGHT,第二个堆栈从RIGHT增长到LEFT; 当stackTopIndex交叉时,它会发出溢出信号.

提前感谢您的深刻回答.

Answer 1

您可以使用链接列表实现三个堆栈:

• 你需要一个指向下一个自由元素的指针.另外三个指针返回每个堆栈的最后一个元素(如果堆栈为空,则返回null).
• 当堆栈添加另一个元素时,它必须使用第一个free元素并将空闲指针设置为下一个free元素(否则将引发溢出错误).它自己的指针必须指向新元素,从那里返回到堆栈中的下一个元素.
• 当堆栈中的元素被删除时,它会将其移回自由元素列表中.堆栈的自己的指针将被重定向到堆栈中的下一个元素.

甲链表可以在阵列内来实现.

怎么(空间)效率这个？
通过为每个列表元素(值+指针)使用数组的两个单元格来构建链接列表没有问题.根据规范,你甚至可以将指针和值放到一个数组元素中(例如,数组很长,值和指针只是int).
将此与kgiannakakis的解决方案进行比较 ......在此情况下,您将损失高达50%(仅在最坏的情况下).但我认为我的解决方案有点清洁(也许更多的学术,对面试问题来说应该没有劣势^^).

Answer 2

参见Knuth,计算机程序设计的艺术,第1卷,第2.2.2节.标题为"顺序分配".讨论在单个数组中分配多个队列/堆栈,算法处理溢出等.

Answer 3

第一个堆栈从左向右增长。

第二个堆栈从右向左增长。

第三堆从中间开始。为了简单起见，假设奇数大小的数组。然后第三个堆栈的增长如下：

* * * * * * * * * * *
      5 3 1 2 4

第一和第二堆栈允许以数组大小的一半增长最大值。第三个堆栈可以增长到最多填满整个数组。

最坏的情况是前两个数组之一增长到数组的 50%。那么阵列就有50%的浪费。为了优化效率，必须选择第三个阵列，使之比其他两个阵列增长得更快。