Coding Exercises Day 27 (Problem #21)

Problem:

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

class ThreeStacks {
  private static final String STACK_ID_ERROR_MSG = "Stack Id must be 0, 1, or 2";
  
  int[] stackSize = new int[3];

  T[] dataArray;

  public ThreeStacks(int initialSize) {
    dataArray = new T[initialSize];
  }

  public push(int stackId, T element) throws IllegalArgumentException {
    if (stackId < 0 || stackId > 2) throw IllegalArgumentException(STACK_ID_ERROR_MSG);

    // if data array is too small, triple it and copy over contents
    if (dataArray.length < (stackSize[stackId] + 1) * 3) {
      increaseDataArray();
    }    

    for (int i = stackSize[stackId]; i > 0; i--) {
      int index = i * 3 + stackId;
      dataArray[index] = dataArray[index - 3];      
    }

    stackSize[stackId]++;
    dataArray[stackId] = element;
  }

  public pop(int stackId) {
    if (stackId < 0 || stackId > 2) throw IllegalArgumentException(STACK_ID_ERROR_MSG);

    if (stackSize[stackId] == 0) return null;

    T rval = dataArray[stackId];

    int index = stackId;

    for (int i = 0; i < stackSize[stackId]; i++) {
      dataArray[index] = dataArray[index + 3];      
    }    

    stackSize[stackId]--;

    return rval;
  }

  private increaseDataArray() {
    T[] biggerDataArray = new T[dataArray.length * 3];

    for (int i = 0; i < dataArray.length; i++) {
      biggerDataArray[i] = dataArray[i];
    }
  }
}