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

本文介绍了如何使用单个数组实现三个堆栈的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述 我在访问网站遇到这个问题。该问题要求在单个阵列中有效地实现三个堆栈，使得在整个数组空间中没有剩余空间之前，不会堆栈溢出。

为了在数组中实现2个堆栈，这是非常明显的：第一个堆栈从LEFT增加到RIGHT，第二个堆栈从RIGHT增长到LEFT;当stackTopIndex跨越时，它发出一个溢出信号。

提前感谢您的深刻答复。

解决方案

您可以使用 链接列表 ：

• 您需要一个指向下一个自由元素另外三个指针返回每个堆栈的最后一个元素（如果堆栈为空，则返回null）。
• 当堆栈获取另一个元素时，必须使用第一个空闲元素并设置指向下一个空闲元素的空闲指针（或溢出错误将被提升）。它的自己的指针必须指向新的元素，从那里返回到堆栈中的下一个元素。
• 当堆栈获取元素被移除时，它将把它移回到免费的列表中元素。堆栈中的自己的指针将被重定向到堆栈中的下一个元素。

链接列表可以在一个数组中实现。

如何（空间）效率是这样的？ 使用两个单元格构建链表是没有问题的每个列表元素的数组（值+指针）。根据规范，您甚至可以将指针和值转换为一个数组元素（例如，数组长，值和指针只是int）。 将此与kgiannakakis ...您最多失去50％（仅限于在最坏的情况下）。但我认为我的解决方案有点清洁（也许更多的是学术，这对于采访问题来说应该是不利的^^）。

I came across this problem in an interview website. The problem asks for efficiently implement three stacks in a single array, such that no stack overflows until there is no space left in the entire array space.

For implementing 2 stacks in an array, it's pretty obvious: 1st stack grows from LEFT to RIGHT, and 2nd stack grows from RIGHT to LEFT; and when the stackTopIndex crosses, it signals an overflow.

Thanks in advance for your insightful answer.

解决方案

You can implement three stacks with a linked list:

• You need a pointer pointing to the next free element. Three more pointers return the last element of each stack (or null, if the stack is empty).
• When a stack gets another element added, it has to use the first free element and set the free pointer to the next free element (or an overflow error will be raised). Its own pointer has to point to the new element, from there back to the next element in the stack.
• When a stack gets an element removed it will hand it back into the list of free elements. The own pointer of the stack will be redirected to the next element in the stack.

A linked list can be implemented within an array.

How (space) efficent is this? It is no problem to build a linked list by using two cells of an array for each list element (value + pointer). Depending on the specification you could even get pointer and value into one array element (e.g. the array is long, value and pointer are only int). Compare this to the solution of kgiannakakis ... where you lose up to 50% (only in the worst case). But I think that my solution is a bit cleaner (and maybe more academic, which should be no disadvantage for an interview question ^^).