使用单个数组实现三个栈

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;
    }
}

- Lin Ma

---

你能说出出了什么问题吗？我测试了你的代码，看起来没问题。 - Johnny Willer

我不明白这个想法：使用“缓存区(buffer)”怎么比只使用三个无关联的链表更好呢？ - greybeard

@LinMa，正确的行为是三个堆栈必须完全分离，对吗？请展示一些你认为可能会出现错误行为的情况。 - Johnny Willer

@LinMa，你说的“continuous”是什么意思？ - Johnny Willer

@LinMa 这个实现是正确的，我会给你发一篇答案，但是我有点困惑你到底想知道什么。关于执行 "indexUsed--" 时连续删除空格的问题，我不明白减少 indexUsed 有什么问题，这个数字是必要的，用来指向缓冲区的顶部。 - Johnny Willer

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元素并使用它来创建所需堆栈的元素。当从堆栈中pop元素时，该元素会被push回堆。

- Aivean

---

@LinMa 如果您有三个栈，那么将它们表示为三个独立的栈是很合理的。Java有标准接口Deque（http://docs.oracle.com/javase/7/docs/api/java/util/Deque.html）代表堆栈。从其实现中选择 ArrayDeque 或 LinkedList。如果事先知道堆栈大小，则首选前者。 - Aivean

谢谢Aivean，我完全理解了。这个问题有点棘手，因为只允许使用一个数组。你有什么想法如何为3个栈使用一个数组？ :) - Lin Ma

@LinMa 我认为你需要创建一个单独的问题，并提供所有必要的细节和任务限制。因为现在Deque[]是答案（只有一个栈数组）。 - Aivean

@LinMa 我更新了我的答案，提供了可能的解决方案（如果这不是一个真实世界的问题，而只是一个人工谜题）。 - Aivean

@LinMa，不完全正确。您对问题的原始描述是准确的。修复方法是创建另一个“堆栈”（类似于堆栈0..2），用于存储缓冲区中空闲元素的索引。您需要弹出该堆栈以获取indexUsed的类比（只是它不会连续）。此外，在从“常规堆栈”中删除元素时，您需要释放它们的索引（将它们放回“空闲索引”堆栈中）。 - Aivean

Answer 2

您可以从数组的一端开始其中一个堆栈。您可以从另一端开始另一个堆栈。您可以将第三个堆栈放在中间。当其中一个侧面的堆栈需要空间时，您需要移动中间的堆栈。但是，我还有另一种通过自由列表帮助实现的方法。您也可以尝试这种实现：

    public class ThreeStacksWithOneArray {

    //This is the stack node class
    class StackNode {
        //This is the value of the node
        int value;
        //This is showing the previous node
        int prev;
        //This is the constructor of the class
        StackNode(int value, int prev) {
            this.value = value;
            this.prev = prev;
        }
    }

    //This keeps the stack nodes
    private StackNode[] stackNodes = null;
    private static int CAPACITY = 10;
    //This keeps the top of free list
    private int freeListTop = 0;
    //This is the variable for the size
    private int size = 0;
    //These are the pointers to the three stacks
    private int[] stackPointers = { -1, -1, -1 };

    //This is the constructor of the main class
    ThreeStacksWithOneArray() {
        //Initialize the stack nodes
        stackNodes = new StackNode[CAPACITY];
        //initialize the free list
        initFreeList();
    }

    //Initialize the free list
    private void initFreeList() {
        for (int i = 0; i < CAPACITY; i++) {
            //The value of each node is 0 and it points to the next node
            stackNodes[i] = new StackNode(0, i + 1);
        }
    }

    //This is the push procedure
    public void push(int stackNum, int value) throws Exception {
        //Print the push information
        System.out.println("Push to stack "+stackNum+" value "+value);
        int freeIndex;
        int currentStackTop = stackPointers[stackNum - 1];
        //Find the free node
        freeIndex = getFreeNodeIndex();
        //Make a new node in the free index
        StackNode n = stackNodes[freeIndex];
        //Setting the previous node
        n.prev = currentStackTop;
        //Setting the value
        n.value = value;
        stackPointers[stackNum - 1] = freeIndex;
    }

    //This is the pop method
    public StackNode pop(int stackNum) throws Exception {
        //From which stack you want to pop. -1, since it starts from 0
        int currentStackTop = stackPointers[stackNum - 1];
        //This checks for stack underflow
        if (currentStackTop == -1) {
            throw new Exception("UNDERFLOW");
        }
        //Get the node as a temp node
        StackNode temp = stackNodes[currentStackTop];
        //Remove the node from stack
        stackPointers[stackNum - 1] = temp.prev;
        //Put this node as free node
        freeStackNode(currentStackTop);
        //Print the pop information
        System.out.println("Pop from stack "+stackNum+" value: "+temp.value);
        //Return the value
        return temp;
    }

    //Get a free node index
    private int getFreeNodeIndex() throws Exception {
        int temp = freeListTop;
        //Overflow
        if (size >= CAPACITY)
            throw new Exception("OVERFLOW");
        freeListTop = stackNodes[temp].prev;
        size++;
        //return the free node index
        return temp;
    }

    //Make one index free after a pop
    private void freeStackNode(int index) {
        stackNodes[index].prev = freeListTop;
        //Put the index in free list
        freeListTop = index;
        //Decrease the size by one
        size--;
    }

    public static void main(String args[]) {
        // Test Driver
        ThreeStacksWithOneArray mulStack = new ThreeStacksWithOneArray();
        try {
            //Adding to those three stacks
            mulStack.push(1, 11);
            mulStack.push(1, 12);
            mulStack.push(1, 13);
            mulStack.push(1, 14);
            mulStack.push(2, 21);
            mulStack.push(2, 22);
            mulStack.push(3, 31);
            mulStack.push(3, 32);
            //Popping from those three stacks
            mulStack.pop(1);
            mulStack.pop(2);
            mulStack.pop(3);

        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

更多信息请访问：https://github.com/m-vahidalizadeh/foundations/blob/master/src/data_structures/ThreeStacksWithOneArray.java。希望对您有所帮助。

- Mohammad

---

谢谢，Mohammad。我喜欢你的实现方式，因为它可以使用一个数组模拟任意数量的堆栈。点赞。我的困惑是，你提到“你可以从数组的一端开始一个堆栈，从另一端开始另一个堆栈，将第三个堆栈放在中间。当一个侧面的堆栈需要空间时，你需要移动中间的堆栈”，但在你的实现中，我没有看到你从一端开始一个堆栈，从另一端开始另一个堆栈，然后从中间开始第三个堆栈？ - Lin Ma

（续）我有没有读错什么？请随意纠正我。 - Lin Ma

是的，对于试图理解这个问题的人来说，这是最简单的可视化方式。但是，我们在这里使用的实现是通过自由列表帮助完成的。然而，为了避免任何误解，我将编辑响应。 - Mohammad

亲爱的林马，我更新了代码。希望这有所帮助。如果代码仍需要更多的注释，请告诉我。 - Mohammad

不客气。是的，我正在使用自定义对象数组，我有这个实现，因为它非常灵活。 - Mohammad