Stack of Plates

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 ome 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.

FOLLOW UP

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

Solution

class SetOfStacks{
    ArrayList<Stack> stacks = new ArrayList<Stack>();
    public int capacity;

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

    public Stack getLastStack(){
        if (stacks.size() == 0){
            return null;
        }
        return stacks.get(stacks.size() - 1);
    }

    public void push(int v){
        Stack last = getLastStack();
        if (last != null && !last.isFull()){
            last.push(v);
        }
        else {
            Stack stack = new Stack(capacity);
            stack.push(v);
            stacks.add(stack);
        }
    }

    public int pop(){
        Stack last = getLastStack();
        if (last == null) throw new EmptyStackException();
        int v = last.pop();
        if (last.size == 0) stacks.remove(stacks.size() - 1);
        return v;
    }

    public boolean isEmpty(){
        Stack last = getLastStack();
        return last == null || last.isEmpty();
    }

    public int popAt(int index){
        return leftShift(index, true);
    }

    public int leftShift(int index, boolean removeTop){
        Stack stack  = stacks.get(index);
        int removed_item;
        if (removeTop) removed_item = stack.pop();
        else removed_item = stack.removeBottom();
        if (stack.isEmpty()){
            stacks.remove(index);
        }
        else if (stacks.size() > index + 1){
            int v = leftShift(index + 1, false);
            stack.push(v);
        }
        return removed_item;
    }
}

class Stack{
    private int capacity;
    public Node top, bottom;
    public int size = 0;

    public Stack(int capacity){
        this.capacity = capacity;
    }

    public boolean isFull(){
        return capacity == size;
    }

    public void join(Node above, Node below){
        if (below != null) below.above = above;
        if (above != null) above.below = below;
    }

    public boolean push(int v){}

    public int pop(){}

    public boolean isEmpty(){}

    public int removeBottom(){}
}