algorithm - 如何用一个数组实现 3 个堆栈？

Question

有时，我会遇到以下面试问题:如何用一个数组实现 3 个堆栈？当然，任何静态分配都不是解决方案。

Answer 1

节省空间(而非时间)。你可以:

1) 定义两个堆栈，从阵列端点开始并沿相反方向增长。

2) 将第三个堆栈定义为从中间开始并向您想要的任何方向增长。

3)重新定义Push op，这样当操作要覆盖其他栈时，你在Pushing之前将整个中间栈向相反的方向移动。

您需要将前两个堆栈的堆栈顶部以及第三个堆栈的开始和结束存储在某种结构中。

编辑

上面你可能会看到一个例子。尽管可以根据您的问题启发式方法选择其他策略，但转移是通过等空间分区策略完成的。

编辑

按照@ruslik 的建议，中间 堆栈可以使用交替顺序进行后续推送来实现。生成的堆栈结构将类似于:

| Elem 6 | Elem 4 | Elem 2 | Elem 0 | Elem 1 | Elem 3 | Elem 5 |

在这种情况下，您需要将 n 个元素存储在中间堆栈上并使用函数:

f[n_] := 1/4 ( (-1)^n (-1 + 2 n) + 1) + BS3  

知道要用于此堆栈的下一个数组元素。

虽然这可能会导致更少的转移，但三个堆栈的实现并不同质，不同质性(你知道)会导致特殊情况、更多错误和维护代码的困难。