有时,我会遇到以下面试问题:如何用一个数组实现3个堆栈?当然,任何静态分配都不是解决方案。
空间(而非时间)高效。你可以:
1) 定义两个堆栈,从数组端点开始并沿相反方向增长。
2) 将第三个堆栈定义为从中间开始并向您想要的任何方向增长。
3)重新定义Push操作,这样当操作要覆盖其他堆栈时,在Pushing之前将整个中间堆栈向相反方向移动。
您需要以某种结构存储前两个堆栈的堆栈顶部以及第三个堆栈的开头和结尾。
Edit
上面你可能会看到一个例子。尽管可以根据您的问题启发选择其他策略,但转移是通过等空间分区策略完成的。
Edit
根据@ruslik的建议,middle堆栈可以使用后续推送的交替序列来实现。生成的堆栈结构将类似于:
|元素 6 |元素 4 |元素 2 |元素 0 |元素 1 |元素 3 |元素 5 |
在这种情况下,您需要在中间堆栈上存储 n 个元素并使用以下函数:
f[n_] := 1/4 ( (-1)^n (-1 + 2 n) + 1) + BS3
了解要用于此堆栈的下一个数组元素。
虽然这可能会导致更少的转移,但三个堆栈的实现并不同质,并且不同质(你知道)会导致特殊情况、更多错误和维护代码的困难。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)