Lin Ma Lin Ma - 2 months ago 17
Java Question

use a single array to implement three stacks

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

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.

Comments