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

EN

您可以使用实现三个堆栈：

• 你需要一个指向下一个自由元素的指针。另外三个指针返回每个堆栈的最后一个元素(如果堆栈是空的，则返回null )。
• 当堆栈添加另一个元素时，它必须使用第一个空闲元素并将空闲指针设置为下一个空闲元素(否则将引发溢出错误)。它自己的指针必须指向新的元素，从那里回到堆栈中的下一个元素。
• 当堆栈移除一个元素时，它会把它交回空闲元素的列表中。堆栈的自身指针将重定向到堆栈中的下一个元素。

链表可以在数组中实现。

这(空间)效率如何？

通过为每个列表元素(值+指针)使用数组的两个单元来构建链表是没有问题的。根据规范的不同，你甚至可以将指针和值放入一个数组元素中(例如，数组很长，而值和指针只是整型的)。

将其与kgiannakakis的解决方案进行比较...损失高达50% (仅在最坏的情况下)。但我认为我的解决方案更清晰一些(也许更学术，这对于面试问题^^应该没有什么坏处)。

请参阅Knuth, The Art of Computer Programming, Volume 1，第2.2.2节。标题为“顺序分配”。讨论在单个数组中分配多个队列/堆栈，以及处理溢出的算法等。

我们可以使用长位数组来表示第i个数组单元属于哪个堆栈。我们可以取模3的值(00 -空，01 - A，10 - B，11 - C)。对于N大小的数组，需要N/2位或N/4字节的额外内存。

例如，对于1024个长整型元素(4096字节)，只需要256个字节或6%。

这个位数组映射可以放在相同的数组中，在开始或结束时，只需将给定数组的大小缩小6%！