Implement Three Stacks by Single Array

Implement three stacks by single array.

You can assume the three stacks has the same size and big enough, you don't need to care about how to extend it if one of the stack is full.

Solution:

This question is relatively easy when we cut the single array into three segments and create three stack size counters for each of the segment. When one of the stack is full we can move all elements into an larger array. Note: this is the simplest way to solve this problem.

The sceond way, start one stack at the beginning and one stack at the end. The third stack is operated in the middle of the array. If any stack needs to overwrite value from other stacks, we could shift the third stack to a middle position (where the distances between first and second stack are same).

The third solution, assume we have three stacks A, B, and C, we could store data as A1, B1, C1, B2, C2, A2, etc. We put some meta information (indicates the previous) along with values.

Code:

public class ThreeStacks {

    private final static int NUMSTACK = 3;
    private final int maxSize;
    private int[] size = new int[NUMSTACK];
    private int[] data;

    public ThreeStacks(int size) {
        this.data = new int[size * this.NUMSTACK];
        this.maxSize = size;
        for (int i = 0; i < this.NUMSTACK; i++) {
            this.size[i] = i * maxSize;
        }
    }

    public void push(int stackNum, int value) {
        data[size[stackNum]++] = value;
    }

    public int pop(int stackNum) {
        int num = data[--size[stackNum]];
        return num;
    }

    public int peek(int stackNum) {
        return data[size[stackNum] - 1];
    }

    public boolean isEmpty(int stackNum) {
        return size[stackNum] == stackNum * maxSize;
    }
}