如何实现3堆栈与一个阵列？ [英] How to implement 3 stacks with one array?

问题描述

有时候，我遇到下面的面试问题：如何实现3堆栈与一个阵列？当然，任何静态分配是没有办法了。

Sometimes, I come across the following interview question: How to implement 3 stacks with one array ? Of course, any static allocation is not a solution.

推荐答案

空间（没有时间）有效。你可以：

Space (not time) efficient. You could:

1）定义两个堆栈开始在阵列端点和在相反方向上增长。

1) Define two stacks beginning at the array endpoints and growing in opposite directions.

2）定义的第三个栈开始在中，任何你想要的方向成长。

2) Define the third stack as starting in the middle and growing in any direction you want.

3）重新定义推运，这样，当操作是要覆盖其他栈，则推前向相反的方向移动整个中间栈。

3) Redefine the Push op, so that when the operation is going to overwrite other stack, you shift the whole middle stack in the opposite direction before Pushing.

您需要存储用于第一两个堆栈的栈顶第三层叠的，并开始和结束在一些结构

You need to store the stack top for the first two stacks, and the beginning and end of the third stack in some structure.

修改

在上面，你可以看到一个例子。移位是完成与平等的空间分割的政策，虽然其他的策略可能会根据您的问题启发来选择。

Above you may see an example. The shifting is done with an equal space partitioning policy, although other strategies could be chosen depending upon your problem heuristics.

修改

继@ ruslik的建议，在中堆栈可以用后续推的交替序列来实现。由此产生的堆叠结构是这样的：

Following @ruslik's suggestion, the middle stack could be implemented using an alternating sequence for subsequent pushes. The resulting stack structure will be something like:

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

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

在这种情况下，你需要存储的元素个数n对中堆栈和使用功能：

In this case, you'll need to store the number n of elements on the middle stack and use the function:

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

要知道使用这个堆栈中的下一个数组元素。

to know the next array element to use for this stack.

虽然可能这将导致更少的转移，实行不均质三个栈和不均匀性（你知道）导致特殊情况下，更多的错误和困难，以保持code。

Although probably this will lead to less shifting, the implementation is not homogeneous for the three stacks, and inhomogeneity (you know) leads to special cases, more bugs and difficulties to maintain code.

这篇关于如何实现3堆栈与一个阵列？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！