java - 使用单个数组实现三个堆栈

Question

调试这个问题的一些解决方案，对于下面的代码片段，我认为方法pop()的逻辑是错误的，因为在执行“indexUsed--”时，空格被连续删除，但是在删除元素时，它不一定是连续的。

如果我错了，请随时纠正我。

int stackSize = 300;
int indexUsed = 0;
int[] stackPointer = { -1, -1, -1 };
StackNode[] buffer = new StackNode[stackSize * 3];
void push(int stackNum, int value) {
    int lastIndex = stackPointer[stackNum];
    stackPointer[stackNum] = indexUsed;
    indexUsed++;
    buffer[stackPointer[stackNum]] = new StackNode(lastIndex, value);
}
int pop(int stackNum) {
    int value = buffer[stackPointer[stackNum]].value;
    int lastIndex = stackPointer[stackNum];
    stackPointer[stackNum] = buffer[stackPointer[stackNum]].previous;
    buffer[lastIndex] = null;
    indexUsed--;
    return value;
}
int peek(int stack) { return buffer[stackPointer[stack]].value; }
boolean isEmpty(int stackNum) { return stackPointer[stackNum] == -1; }

class StackNode {
    public int previous;
    public int value;
    public StackNode(int p, int v) {
        value = v;
        previous = p;
    }
}

Answer 1

你是对的，这种方法不仅效率低得离谱且过于复杂，而且不正确。

这里是一个简单的测试来证明:

    StackArray stack = new StackArray();
    stack.push(0, 0);
    stack.push(1, 10);
    System.out.println(stack.pop(0));
    stack.push(1, 20);
    System.out.println(stack.pop(1));
    System.out.println(stack.pop(1));

产生:

 Exception in thread "main" java.lang.NullPointerException
   at StackArray.pop(StackArray.java:18)

栈数据结构通常实现为数组或单链表。链表效率较低，因为它的元素分散在堆中，而且它的元素有内存开销(带指针的节点对象)。另一方面，数组速度更快，但它具有固定大小，因此不能用于所有任务。

这些方法中的每一种都有其优点和缺点，但是创建具有两种方法只有缺点(具有固定容量和内存开销)的混合方法绝对没有意义。

---

如果这是一个合成任务，限制只使用一个数组来存储所有三个堆栈的元素，则可以使用以下方法。

逻辑上成对拆分数组元素。每对将代表单链表的一个节点。该对的第一个元素将保存该值，而第二个元素将是指向下一个节点的指针。

很明显数组可以容纳任意数量的独立单链表(只要它有足够的容量)并且你知道头部的索引。

这个想法类似于描述中给出的方法，保存指向三个列表头部的指针，但是(!)另外保存指向表示“空闲内存”并包括所有未占用元素的列表的指针的阵列。最初这个“堆”列表将包含数组的所有元素。当您将 push 元素放入其中一个堆栈时，您需要从 heap 中pop 元素并使用它来创建所需堆栈的元素。当元素从堆栈中弹出时，该元素被推回堆。