Describe how you could use a single array to implement three stacks

I'm preparing for an interview so I'm trying to solve some problems to stretch my mind. Here is one:


Describe how you could use a single array to implement three stacks.

And here is my implementation:

```
class StackUnderflowError extends RuntimeException {
public StackUnderflowError(String msg) {
super(msg);
}
}

class ThreeStacks{

private T[] array;
private int firstIndex = 0;
private int secondIndex = 1;
private int thirdIndex = 2;

public ThreeStacks(Class classT, int capacity) {
array = (T[])Array.newInstance(classT, capacity);
}

void push(T data, int stack){ //enum to select the stack
switch(stack)
{
case 1: pushOne(data);
break;
case 2: pushTwo(data);
break;
case 3: pushThree(data);
break;
default: throw new IllegalArgumentException("stack");
}
}

T pop(int stack){
switch(stack){
case 1: return popOne();
case 2: return popTwo();
case 3: return popThree();
default: throw new IllegalArgumentException("stack");
}
}

private void pushOne(T data) {
if (firstIndex > array.length - 1) {
throw new StackOverflowError("firstStack");
} else{
array[firstIndex] = data;
firstIndex += 3;
}
}

private void pushTwo(T data) {
if (secondIndex > array.length - 1) {
throw new StackOverflowError("secondStack");
} else{
array[secondIndex] = data;
secondIndex += 3;
}
}

private void pushThree(T data) {
if (thirdIndex > array.length - 1) {
throw new StackOverflowError("thirdStack");
} else{
array[thirdIndex] = data;
thirdIndex += 3;
}
}

private T popOne() {
firstIndex -= 3;
if(firstIndex < 0){
throw new StackUnderflowError("fristStack");
}
return array[firstIndex];
}

private T popTwo() {
secondIndex -= 3;
if(secondIndex < 0){
throw new StackUnderflowError("fristStack");
}
return arr

Solution that I found

In this approach, any stack can grow as long as there is any free space in the array.
We sequentially allocate space to the stacks and we link new blocks to the previous block. This means any new element in a stack keeps a pointer to the previous top element of that particular stack.

In this implementation, we face a problem of unused space. For example, if a stack deletes some of its elements, the deleted elements may not necessarily appear at the end of the array. So, in that case, we would not be able to use those newly freed spaces.
To overcome this deficiency, we can maintain a free list and the whole array space would be given initially to the free list. For every insertion, we would delete an entry from the free list. In case of deletion, we would simply add the index of the free cell to the free list.

In this implementation we would be able to have flexibility in terms of variable space utilization but we would need to increase the space complexity.

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

StackExchange Code Review Q#12663, answer score: 3