如何用一个数组实现 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) 重新定义 Push 操作，这样当操作要覆盖其他堆栈时，在 Pushing 之前将整个中间堆栈向相反方向移动.

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 的建议，middle 堆栈可以使用交替序列来实现后续推送.生成的堆栈结构将类似于:

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:

|元素 6 |元素 4 |元素 2 |元素 0 |元素 1 |元素 3 |元素 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.

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

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