如何使用一个数组来实现3个堆栈？ [英] How to implement 3 stacks with one array?

问题描述

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

解决方案

空间（不是时间）高效。您可以：

1）定义从阵列端点开始并以相反方向增长的两个堆栈。

2）将第三个堆栈定义为从中间开始，并沿着任何方向发展。 3）重新定义Push操作，以便当操作要覆盖其他堆栈时，在推动之前将整个中间堆栈移向相反方向。

您需要存储前两个堆栈的堆栈顶部，在某些结构中存储第三个堆栈的开头和结尾。

编辑

您可能会看到一个例子。这种转变是用相等的空间划分政策完成的，尽管根据您的问题启发式可以选择其他策略。

编辑

按照@ 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 
  

知道要用于此堆栈的下一个数组元素。尽管这可能会导致更少的转移，但是这三个堆栈的执行并不一致，而不均匀性（您知道）会导致特殊情况，更多的错误和难度。维护代码。

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) Define two stacks beginning at the array endpoints and growing in opposite directions.

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

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.

Edit

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.

Edit

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 |

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.

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屋！