我在一个面试网站上遇到了这个问题。该问题要求在单个数组中高效实现三个栈,使得在整个数组空间没有空间时,没有栈会溢出。
对于在数组中实现2个栈,很显然:第1个栈从左到右增长,第2个栈从右到左增长;当栈顶索引相遇时,它表示溢出。
提前感谢你的有见地的回答。
我在一个面试网站上遇到了这个问题。该问题要求在单个数组中高效实现三个栈,使得在整个数组空间没有空间时,没有栈会溢出。
对于在数组中实现2个栈,很显然:第1个栈从左到右增长,第2个栈从右到左增长;当栈顶索引相遇时,它表示溢出。
提前感谢你的有见地的回答。
可以在数组内部实现链表。
这有多高效?
使用数组的两个单元格构建链表没有问题,每个链表元素(值+指针)都需要两个。根据规范,甚至可以将指针和值放入一个数组元素中(例如,数组很长,值和指针仅为int)。
与kgiannakakis的解决方案相比,您最多会失去50%的空间(仅在最坏情况下)。但我认为我的解决方案更加简洁(也许更加学术,这对面试题来说应该没有不利之处^^)。
请参阅《计算机程序设计艺术》卷1第2.2.2节“顺序分配”。该节讨论如何在单个数组中分配多个队列/堆栈,并给出了处理溢出等情况的算法。
N
的堆栈,它将需要N log₃ / log₂ ≈ N ⋅ 1.585
额外的位。也就是说,对于大小为1
位的元素,此位图将具有+158%
的开销,对于范围为0..2
的元素,它将具有+100%
的开销,对于字节长的元素,它将具有+20%
的开销。要使元素的大小不超过+6%
,其大小至少应为27
位或范围约为0 .. 89 540 788
。 - ony第一个栈从左到右增长。
第二个栈从右到左增长。
第三个栈从中间开始。为了简单起见,假设数组大小为奇数。那么第三个栈的增长方式如下:
* * * * * * * * * * *
5 3 1 2 4
第一和第二个栈允许在数组的一半大小时最大化增长。第三个栈可以在最大情况下填满整个数组。
最坏的情况是当第一个或第二个数组以数组的50%增长时。那么就会浪费50%的数组空间。为了优化效率,必须选择第三个数组比其他两个更快地增长。
将数组分成任意3部分(无论是顺序分割还是交错分割)。如果一个堆栈增长超过数组的1/3,您就开始从其余两个堆栈的末尾填充。
aaa bbb ccc 1 2 3 145 2 3 145 2 6 3 145 2 6 3 7 145 286 3 7 145 286 397
最坏情况是两个堆栈增长到1/3边界,然后您会浪费30%的空间。
使用键值对创建HashMap,例如 < "B1" , 0 >, <"E1" , n/3 >
对于每个Push(value),添加一个条件来检查Bx的位置是否在Ex之前或者是否有其他“By”在中间。--我们称之为条件(2)
考虑到上述条件, 如果上述(2)为真//如果B1和E1按顺序排列 { 如果(S1.Push()),那么E1 ++; 否则//溢出条件, {从E2或E3的末尾开始推送(哪个有空间),并将E1更新为E2--或E3--; } }
如果上述(2)为假 { 如果(S1.Push()),那么E1--; 否则//溢出条件, {从E2或E3的末尾开始推送(哪个有空间),并将E1更新为E2--或E3--; } }
一个相当愚蠢但有效的解决方案可能是:
这种解决方案的问题是,使用的内存始终是最深的堆栈大小的三倍,即使数组中有可用位置,也可能会溢出。
假设所有数组位置都应用于存储值——我猜这取决于您对效率的定义。
如果您使用两个堆栈解决方案,将第三个堆栈放在中间某个位置,并跟踪其底部和顶部,则大多数操作将继续保持高效,但每当发生冲突时,需要进行昂贵的移动操作(将第三个堆栈移向剩余的空闲空间,移动到自由空间的一半)。
编码和理解肯定会很快。我们的效率目标是什么?