use a single array to implement three stacks

Question

Debugging on some solutions for this problem, and for the following code snippet, I think the logic is wrong in method pop(), since when executing "indexUsed--", spaces are removed continuously, but when deleting elements, it is not necessarily to be continuous.

Please feel free to correct me if I am wrong.

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

You can start one of the stacks from one end of the array. You can start the other stack from the other end of the array. You can put the third stack in the middle. When, one of the side stacks need space, you need to shift the middle stack. However, I have another implementation by help of free list. You can try this implementation also:

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

For more information, visit this: https://github.com/m-vahidalizadeh/foundations/blob/master/src/data_structures/ThreeStacksWithOneArray.java. I hope it helps.

Answer 2

You are right, this approach is not only ridiculously inefficient and overcomplicated, but also incorrect.

Here is the simple test to prove:

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

Produces:

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

Stack data structure is usually implemented as array or single-linked list. Linked list is less efficient, because its elements are scattered across the heap, also its elements have memory overhead (node object with pointers). Array, on the other hand, is faster, but it has fixed size, so it can't be used for all tasks.

Each of these approaches has its pros and cons, but there is absolutely no point in creating mixed approach that has only disadvantages of both approaches (has fixed capacity and memory overhead).

---

If this is a synthetic task with the restriction of using only one array to store elements of all three stacks, then following approach can be used.

Logically split elements of array in pairs. Each pair will represent one node of single-linked list. First element of the pair will hold the value, while second element will be the pointer to the next node.

It's clear that array can hold any number of independent single-linked lists (as long as it has sufficient capacity) and you know the indices of the heads.

The idea is similar to the approach given in description, to hold the pointers to the heads of three lists, but (!) in addition hold the pointer to the list that represent "free memory" and includes all non-occupied elements of the array. Initially this "heap" list will contain all elements of the array. When you push element into one of the stacks, you need to pop element from the heap and use it to create element of the desired stack. When element is popped from the stack, this element is pushed back to heap.