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

我在一个面试网站上遇到了这个问题。该问题要求在单个数组中有效地实现三个堆栈，以便在整个数组空间中没有剩余空间之前堆栈不会溢出。

对于在数组中实现 2 个堆栈，这是非常明显的：第一个堆栈从左到右增长，第二个堆栈从右到左增长；当 stackTopIndex 交叉时，表示溢出。

预先感谢您富有洞察力的回答。

您可以使用以下命令实现三个堆栈链表:

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

A 链表可以在数组中实现。

这（空间）效率如何？
对于每个列表元素（值+指针）使用数组的两个单元来构建链表是没有问题的。根据规范，您甚至可以将指针和值放入一个数组元素中（例如，数组很长，值和指针只是 int）。
将其与以下解决方案进行比较克吉安纳卡基斯...您损失高达 50%（仅在最坏的情况下）。但我认为我的解决方案更干净一些（也许更干净）academic，这对于面试问题来说应该不是什么缺点^^)。