怎么在同一个数组里面实现３个stack，并且最有效率？
How to implement 3 stacks in a single array as efficiently as possible ??
阅微客栈 » 头脑风暴
微软面试题－怎么在同一个数组里面实现３个stack？
(7 posts)-
发布于 1 年 之前 #
-
3个变量分别当作三个stack的sp,初始化为a a+1 a+2(a[]就是这个数组），push就加3，pop就减3.
发布于 1 年 之前 # -
你这样的确很有效率，但3个stack互相独立。空间有可能都浪费。
如果有一个stack很长，另2个很短，怎么让他们的空间共享呢？
发布于 1 年 之前 # -
szuxjq
Memberahua的方法最坏情况会浪费2/3的空间。假如这样，两个stack分别在两端向中间生长，第三个在array中间位置交替向两边生长。这个方法最坏情况会浪费1/2的空间。大家有什么好的方法？
发布于 1 年 之前 # -
szuxjq
Member参照内存管理策略，首先把array分为若干块，一块大小为k，块的两端用做链接。第一个stack在0位置出分配一块空间，stack在快空间内可以简单快速操作；第二个stack在k+1处分配一个，第三个在2k+1处分配一个。最后在3k+1处做个记号，表示记号右边的空间都没有分配。如果哪个stack用完空间了就申请一个，把新空间和旧空间连接起来。这样子最多浪费2k大小的空间，如果k大小得当，那么操作速度和空间浪费都能有效控制。
发布于 1 年 之前 # -
wgrmmtmr
Member楼上好想法！
发布于 1 年 之前 # -
lele
Member这样的内存分配策略不完整，随着栈的生长和消退，还应有内存回收。
除三个栈的内存链外还有空闲块的链。维护一个常数为空闲链的开始
块号。当栈消退时将新的空闲的块插到链的 最后发布于 8 月 之前 #
回复
你必须 登录 后发帖。