Coding Exercises Day 25b (Problem #20)

Problem:

Imagine a (literal) stack of plates.If the stack gets too high, it might topple.Therefore, in real life, we would likely start a new stack when the previous stack exceeds some threshold.Implement a data structure SetOfStacks that mimics this.SetOfStacks should be composed of several stacks, and should create a new stack once the previous one exceeds capacity.SetOfStacks.push() and SetOfStacks.pop() should behave identically to a single stack (that is, pop() should return the same values as it would if there were just a single stack).

Follow up:

Implement a function popAt(int index) which performs a pop operation on a specific sub-stack.

class SetOfStacks {
  int threshold;
  int size;

  List<Stack<Node>> stackList = new ArrayList<Stack<Node>>();

  public SetOfStacks(int threshold) {
    this.threshold = threshold;
  }

  public void push(Node node) {
    size++;
    if ((threshold * stackList.size()) < size) {
      stackList.add(0, new Stack<Node>);
    }
    stackList.get(0).push(node);
  }

  public Node pop() {
    if (0 == size) return null;

    size--;

    Stack topStack = stackList.get(0);

    Node rval = topStack.pop();

    if (topStack.empty()) {
      stackList.remove(0);
    }

    return rval; 
  }  

  public Node popAt(int index) {
    Stack<Node> stack = stackList.get(index);
    Node rval = stack.pop();

    Stack temp = new Stack();

    // Rebalance stacks
    for (int i = index - 1; i <= 0; i--) {
      Stack<Node> previousStack = stackList.get(i);
      
      while(!previousStack.empty()) {
        temp.push(previousStack.pop());
      }

      // Fill the empty slot with an element from the previous stack.
      stackList.get(i + 1).push(temp.pop());
      
      while (!temp.empty()) {
        previousStack.push(temp.pop());
      }
    }

    if (stack.empty()) {
      stackList.remove(index);
    }

    return rval;
  }
}