java - 使用 1 个数组实现 3 个堆栈，此代码是否有效？

Question

这是我在一本算法/面试题的书上找到的，别人发了好几篇这个，但我还是有一些疑问，这里是书中的原文和代码:

implement 3 stacks using 1 array:
Approach 2:

在这种方法中，只要数组中有可用空间，任何堆栈都可以增长。 我们按顺序为堆栈分配空间，并将新 block 链接到前一个 block 。这意味着堆栈中的任何新元素都会保留指向该特定堆栈的前一个顶部元素的指针。 在这个实现中，我们面临着未使用空间的问题。例如，如果一个栈删除了它的一些元素，被删除的元素不一定会出现在数组的末尾。因此，在那种情况下，我们将无法使用那些新释放的空间。 为了克服这个缺陷，我们可以维护一个空闲列表，并且整个数组空间将首先交给空闲列表。对于每次插入，我们都会从空闲列表中删除一个条目。在删除的情况下，我们只需将空闲单元格的索引添加到空闲列表。 在此实现中，我们将能够在可变空间利用方面具有灵 active ，但我们需要增加空间复杂性。

1 int stackSize = 300;
2 int indexUsed = 0;
3 int[] stackPointer = {-1,-1,-1};
4 StackNode[] buffer = new StackNode[stackSize * 3];

5 void push(int stackNum, int value) {
6     int lastIndex = stackPointer[stackNum];
7     stackPointer[stackNum] = indexUsed;
8     indexUsed++;
9     buffer[stackPointer[stackNum]]=new StackNode(lastIndex,value);
10 }

11 int pop(int stackNum) {
12    int value = buffer[stackPointer[stackNum]].value;
13    int lastIndex = stackPointer[stackNum];
14    stackPointer[stackNum] = buffer[stackPointer[stackNum]].previous;
15    buffer[lastIndex] = null;
16    indexUsed--;
17    return value;
18 }

19 int peek(int stack) { return buffer[stackPointer[stack]].value; }

20 boolean isEmpty(int stackNum) { return stackPointer[stackNum] == -1; }
21
22 class StackNode {
23    public int previous;
24    public int value;
25    public StackNode(int p, int v){
26       value = v;
27       previous = p;
28    }
29 }

我的问题是:在pop()方法中，设置buffer[lastIndex]为null后(第15行)，然后indexUsed--(第16行)，indexUsed会不会是空的头部？ 让我们调用 Stack Top 节点 第一个堆栈:S1，第二个堆栈:S2，第三个堆栈:S3； 如果发生什么情况: 在我想弹出 s1 之前，我先推了 s1，然后是 s2 和 s3，

index:    10   11   12    13
-------------------------------
| ...   | s1 | s2 | s3 | null |
-------------------------------

indexUsed 现在是 13。 现在，如果我想在第一个堆栈上执行 pop()， 它将变成:

index:     10    11   12    13
----------------------------------
| ...   | null | s2 | s3 | null |
----------------------------------

indexUsed 现在是 13-- ，也就是 12， 那么如果我想将一个新节点推到这个数组上会发生什么， 根据 push() 方法，在第 7 行将 indexUsed 分配给 stackPointer 并用作将索引插入数组，这不会覆盖第 12 个条目中的 s3(stack3 的顶部节点)吗？

added:

以及如何更改它才能使其正常工作？ 乍一看，我会考虑实现一个 boolean[] 来跟踪存储阵列中每个条目的使用情况，但这会耗费时间和空间。

谢谢!

Answer 1

据我所知，你是对的——它没有存储足够的信息来指示内存中的漏洞。

堆栈的一大优点是它可以分配在数组列表之上而不是链表上，从而节省了前一个/下一个指针的内存——这个实现消除了这个优点——很难想象一个应用程序，其中这实际上是一个很好的解决方案。