logo标签列表

如何使用单个数组实现三个栈

language-agnosticdata-structures
16

我在一个面试网站上遇到了这个问题。该问题要求在单个数组中高效实现三个栈，使得在整个数组空间没有空间时，没有栈会溢出。

对于在数组中实现2个栈，很显然：第1个栈从左到右增长，第2个栈从右到左增长；当栈顶索引相遇时，它表示溢出。

提前感谢你的有见地的回答。

1
啊，这是一个非常经典的问题，可以追溯到70年代（或者更早）。我在哪里第一次看到过呢？Knuth？Sedgewick？Standish？嗯...我记得Knuth特别提到了一个技巧/启发式方法来优先考虑增长速度更快的堆栈（在你的情况下是3个堆栈），但是我现在无法立即回想起来 :) - Dimitris Andreou
啊，找到了，我会将其作为下面的答案添加。 - Dimitris Andreou
在单个数组中进行3个堆栈的应用是什么？是否真正有必要？ - Dineshkumar
1
@Dineshkumar 引用局部性。如果我们采用三个单独的堆栈，它们的内存将被分配在不同的位置，因此它们可能不会同时存在于物理内存（RAM）中。而且，我们可能会出现页面缺失..需要将新的堆栈从磁盘带到RAM中。然而，在将3个堆栈作为一个数组实现的情况下，很可能所有堆栈都在单个页面上，并且所有堆栈都在RAM中，即使只有一个堆栈经常使用，其他堆栈很少使用。 - superuser
17个回答
15
你可以使用链表实现三个栈：
  • 你需要一个指针指向下一个空闲元素。另外三个指针返回每个栈的最后一个元素（如果栈为空，则返回null）。
  • 当一个栈添加另一个元素时，它必须使用第一个空闲元素，并将空闲指针设置为下一个空闲元素（否则将引发溢出错误）。它自己的指针必须指向新元素，从那里回到堆栈中的下一个元素。
  • 当一个栈删除一个元素时，它将把它交还到空闲元素列表中。该栈的自己指针将被重定向到堆栈中的下一个元素。

可以在数组内部实现链表。

这有多高效？
使用数组的两个单元格构建链表没有问题，每个链表元素（值+指针）都需要两个。根据规范，甚至可以将指针和值放入一个数组元素中（例如，数组很长，值和指针仅为int）。
与kgiannakakis的解决方案相比，您最多会失去50％的空间（仅在最坏情况下）。但我认为我的解决方案更加简洁（也许更加学术，这对面试题来说应该没有不利之处^^）。

你可以将栈指向“null”索引，并拥有指向链接的空闲元素序列中第一个空闲元素的指针。每次推入栈时，您都会从空闲元素序列中获取该元素，并将其下一个指针更改为旧的栈顶。当元素从栈中弹出时，它返回到自由序列的头部。而kgiannakakis浪费了高达50％，而您的变体始终花费50％的指针。 - ony
1
@tanascius 为什么要“双向”链接？栈总是以相同的方向遍历... - Dr. belisarius
@belisarius：你说得对。这个想法是使用第四个指针来指向一个空闲元素列表。我更新了我的回答...^^谢谢 - tanascius
你如何找到下一个可用元素？如果这3个栈随意推入或弹出元素，则空闲元素的空间也将是随机的。 - Jack
@Jack：所有的免费元素都在一个链表中。只要这个链表不为空，就会有一个指针指向下一个空闲元素。 - tanascius
显示剩余3条评论
10

请参阅《计算机程序设计艺术》卷1第2.2.2节“顺序分配”。该节讨论如何在单个数组中分配多个队列/堆栈，并给出了处理溢出等情况的算法。

2
嘿，谁给 Knuth 的参考资料点了踩，不要害羞，露出你自己 :) - Dimitris Andreou
1
顺便说一下，已经给出的最佳答案已经包含在Knuth对这个问题的更全面的处理中。只是这么说。 - Dimitris Andreou
21
也许那个人不是在踩降低 Knuth 的评分，而是在评价一篇没有太大用处的回答，因为如果你没有这本书在家里的话（如果是这样，你可能一开始就对这个问题没兴趣），这篇回答对你来说基本上是无用的。 - Pascal Cuoq
4
图书馆怎么样？我记不得上一次住在没有收藏 Knuth 书籍的图书馆里了。 - Dimitris Andreou
1
你好，你介意发一下关于那部分的内容吗？至少它的想法。 - daisy
@PascalCuoq（多年之后）：这并不完全正确，考虑到有多少人拥有那些书却从未阅读过它们... - RemcoGerlich
3
我们可以使用长的位数组来表示第i个数组单元格属于哪个栈。我们可以通过模3取值（00-空，01-A，10-B，11-C）来获取值。对于大小为N的数组，它将需要N/2位或N/4字节的额外内存。
例如，对于1024个长整型元素（4096字节），只需使用256字节或6％即可。
这个位数组映射可以放置在相同的数组中，在开头或结尾，只需将给定数组的大小缩小6％！
我非常喜欢这个想法；我认为这是最优化的内存空间利用。就速度而言，缺点是任何堆栈上的push()或pop()操作不再是O(1)，但在最坏情况下可能是O(N)。尽管如此，非常好！ - Ciaran
@Ciaran，我非常确定对于深度为N的堆栈，它将需要N log₃ / log₂ ≈ N ⋅ 1.585额外的位。也就是说，对于大小为1位的元素，此位图将具有+158%的开销，对于范围为0..2的元素，它将具有+100%的开销，对于字节长的元素，它将具有+20%的开销。要使元素的大小不超过+6％，其大小至少应为27位或范围约为0 .. 89 540 788。 - ony
@Vitamon，这与https://dev59.com/UnA75IYBdhLWcg3w3NLf#3075233有何不同？（除了奇怪的计算） - ony
2

第一个栈从左到右增长。

第二个栈从右到左增长。

第三个栈从中间开始。为了简单起见，假设数组大小为奇数。那么第三个栈的增长方式如下：

* * * * * * * * * * *
      5 3 1 2 4

第一和第二个栈允许在数组的一半大小时最大化增长。第三个栈可以在最大情况下填满整个数组。

最坏的情况是当第一个或第二个数组以数组的50%增长时。那么就会浪费50%的数组空间。为了优化效率，必须选择第三个数组比其他两个更快地增长。

1
但这并不符合要求。在第三个堆栈中放入一个元素，然后只放置第一个堆栈的元素...你的解决方案如何处理？ - tanascius
但是假设第一个栈有1个条目，第二个栈有4个条目。你把第三个栈的第四个条目放在哪里？ - Chowlett
1
你们两个都是对的。我的解决方案可能会浪费高达50%的资源。我很想看看是否有人能提供更好的解决方案。 - kgiannakakis
我想在我的初始帖子中提到这种方法。但是由于作者指出，在最坏的情况下可能会浪费50%的空间。 - user369070
2
这是一个有趣的难题，我没有一个真正的答案，但稍微从另一个角度思考一下...... 可能取决于堆栈中每个元素的组成。 如果它是三个真/假标志的堆栈，则可以使用整数元素的前三位。 也就是说，第0位是第一个堆栈的值，第1位是第二个堆栈的值，第2位是第三个堆栈的值。 然后每个堆栈可以独立增长，直到该堆栈的整个数组都被填满。 这甚至更好，因为其他堆栈在第一个堆栈已满时仍然可以继续增长。 我知道这有点作弊，实际上并没有回答问题，但对于非常特定的情况确实有效，并且没有浪费堆栈中的任何条目。 我很感兴趣地观察是否有人能提出适用于更通用元素的正确答案。
你将会有一些按位大小分割的元素浪费，而不是任意大小的元素浪费。这是将数组分为三个部分的变体，但在这种情况下使用交错。 - ony
非常正确和敏锐的发现，因此回到智囊团。正如达米安所说，这取决于是否应该使用所有数组位置来存储值。如果是这样，那么双向链表方法（从面试的角度来看可能是正确的答案）就不能使用。在这种情况下，kgiannakakis的回答可能还可以，但很明显会浪费高达50%的空间。我们仍在等待一个明确定义的答案，该答案使用每个元素来存储值并且不浪费任何空间。达米恩的答案可以做到这一点，但当从中间栈的一端移动到另一端时，维护栈的顺序将会很困难。 - giles123
2

将数组分成任意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%的空间。

我无法完全掌握你的想法。 你的意思是，当第一个堆栈（标记为'aaa'）被从左到右填满时，您会从右到左在第二个堆栈空间（标记为'bbb'）中插入元素。 对于第二个堆栈，您将使用第三个堆栈的空间（标记为'ccc'）; 而对于第三个堆栈，您将使用第一个堆栈的空间。我相信这样做会造成1/3的空间浪费。 - user369070
当"aaa"从左到右完全填充时，同时从右到左开始填充"bbb"和"ccc"(奇数元素放在一个堆栈中，偶数元素放在另一个堆栈中)，直到遇到其中一个堆栈的顶部。即，对于"aaa"的堆栈长度是(n + (n- max(top("bbb"), top("ccc"))))。当你尝试向"aaa"堆栈添加另一个元素时，如果"bbb"或"ccc"的数组已经完全填满，则会出现问题。因此，如果所有堆栈以相同的速度增长，或者一个堆栈的增长速度是2倍，或者两个堆栈的增长速度为0倍，那么就不会浪费任何空间。如果有一个堆栈的增长速度是2倍，而另一个堆栈是0倍，则会浪费(1/3)/2的空间。 - ony
1

  1. 使用键值对创建HashMap，例如 < "B1" , 0 >, <"E1" , n/3 >

  2. 对于每个Push（value），添加一个条件来检查Bx的位置是否在Ex之前或者是否有其他“By”在中间。--我们称之为条件（2）

  3. 考虑到上述条件， 如果上述（2）为真//如果B1和E1按顺序排列 { 如果（S1.Push（）），那么E1 ++； 否则//溢出条件， {从E2或E3的末尾开始推送（哪个有空间），并将E1更新为E2--或E3--; } }

    如果上述（2）为假 { 如果（S1.Push（）），那么E1--； 否则//溢出条件， {从E2或E3的末尾开始推送（哪个有空间），并将E1更新为E2--或E3--; } }

1
假设您只有整数索引。如果使用FILO（先进后出）进行处理，不引用单个元素，仅使用数组作为数据。使用其6个空间作为堆栈引用应该有所帮助：
[头-1，尾-1，头-2，尾-2，头-3，尾-3，数据，数据，...，数据]
您只能简单地使用4个空间，因为头-1 = 0且last-3 =数组长度。如果使用FIFO（先进先出），则需要重新索引。
注：我正在努力改善我的英语。
1

一个相当愚蠢但有效的解决方案可能是:

  • 将第一个堆栈元素存储在i*3的位置:0,3,6,...
  • 将第二个堆栈元素存储在i*3+1的位置:1,4,7,...
  • 将第三个堆栈元素存储在i*3+2的位置。

这种解决方案的问题是，使用的内存始终是最深的堆栈大小的三倍，即使数组中有可用位置，也可能会溢出。

1

假设所有数组位置都应用于存储值——我猜这取决于您对效率的定义。

如果您使用两个堆栈解决方案，将第三个堆栈放在中间某个位置，并跟踪其底部和顶部，则大多数操作将继续保持高效，但每当发生冲突时，需要进行昂贵的移动操作（将第三个堆栈移向剩余的空闲空间，移动到自由空间的一半）。

编码和理解肯定会很快。我们的效率目标是什么？

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接