调试这个问题的一些解决方案,对于下面的代码片段,我认为方法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;
}
}
最佳答案
你是对的,这种方法不仅效率低得离谱且过于复杂,而且不正确。
这里是一个简单的测试来证明:
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
元素并使用它来创建所需堆栈的元素。当元素从堆栈中弹出
时,该元素被推
回堆。
关于java - 使用单个数组实现三个堆栈,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33110047/