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

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

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(){}
}
``````