Stack of plates

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

Solution

1. push(), to the last stack, if last full, create new stack. So, in a way, rather than stack overflow exception, return boolean if the stack is full.
2. pop(), pop from the last stack, if last is empty, then delete stack
3. popAt(int index), pop from “index”th stack, will ignore empty spaces to save time.

Code in java
(credits)

import java.util.ArrayList;
 
public class SetOfStacks{
    private int threshold;
    private ArrayList<MyStack> setOfStacks =new  ArrayList<>();
     
    SetOfStacks(int threshold) {
        this.threshold = threshold;       
    }
    //get the last stack
    public MyStack getLastStack(){
        int size = setOfStacks.size();
        if(size <= 0) return null;
        else return setOfStacks.get(size - 1);
    }
     
    //get the nth stack
    public MyStack getNthStack(int n){
        int size = setOfStacks.size();
        if(size <= 0) return null;
        else return setOfStacks.get(n - 1);
    }
     
    //push value
    public void push(int value){
        MyStack lastStack = this.getLastStack();
         
        if(lastStack == null){
            lastStack = new MyStack(threshold);
            lastStack.push(value);
            setOfStacks.add(lastStack);
        }else {
            if( !lastStack.isAtCapacity())
                lastStack.push(value);
            else {
                MyStack newLastStack = new MyStack(threshold);
                newLastStack.push(value);
                setOfStacks.add(newLastStack);
            }
        }   
    }
    // the pop
    public int pop(){
        MyStack lastStack = this.getLastStack();
        int v = lastStack.pop();
        if(lastStack.size() == 0) setOfStacks.remove(setOfStacks.size() -  1);
        return v;
    }
     
     
    //pop the nth stack
    public int pop(int nth){
         MyStack nthStack = this.getNthStack(nth);
         int v = nthStack.pop();
         if(nthStack.size() == 0) setOfStacks.remove(setOfStacks.size() -  1);
         return v;  
         
    }
     
    public String toString(){
        String s = "";
        for(int i = 0; i < setOfStacks.size(); i++){
            MyStack stack = setOfStacks.get(i);
            s = "||" + stack.toString() +  s;
        }         
        return s;
    }
     
     
    public static void main(String[] args){
        SetOfStacks stacks = new SetOfStacks(3);
        stacks.push(1);
        stacks.push(2);
        stacks.push(3);
        stacks.push(4);
        stacks.push(5);
        stacks.push(6);
        stacks.push(7);
        System.out.println("the stack is: " + stacks);
        stacks.pop(1);
        System.out.println("pop 1st: " + stacks);
        stacks.pop(2);
        System.out.println("pop 2nd stack: " + stacks);
        stacks.pop(1);
        System.out.println("pop 1st stack: " + stacks);
        stacks.pop(2);
        System.out.println("pop 2nd stack: " + stacks);
         
         
    }
}
 
//MyStack goes with size(), isAtCapacity()
//implemented from a array
 
class MyStack {
     
    private int top = -1;  
    private int[] buffer;
    private int capacity;
     
     
    MyStack(int capacity){
        this.capacity = capacity;
        buffer = new int[capacity];
    }
     
    public void push(int v){
        buffer[++top] = v;
    }
     
    public int pop(){
         
        return buffer[top--];
    }
    // if the stack is at capacity
    public Boolean isAtCapacity(){
        return capacity == top + 1;
    }
    //return the size of the stack
    public int size(){
        return top+1;
    }
     
    public String toString(){
        String s = "";
        int index = top;
        while(index >= 0){
            s += "[" + buffer[index--] + "]"+ " -> ";
        }
        return s;
         
    } 
}

TextBook notes:
What about the follow up question? This is a bit trickier to implement, but essentially we should imagine a “rollover” system. If we pop an element from stack 1, we need to remove the bottom of stack 2 and push it onto stack 1. We then need to rollover from stack 3 to stack 2, stack 4 to stack 3, etc.
NOTE: You could make an argument that, rather than “rolling over,” we should be OK with some stacks not being at full capacity. This would improve the time complexity (by a fair amount, with a large number of elements), but it might get us into tricky situations later on if someone assumes that all stacks (other than the last) operate at full capacity. There’s no “right answer” here; discuss this trade-off with your interviewer!