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 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 question

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

👉 Link here to the repo to solve the problem

👌 Tips

You will need to keep track of the size of each substack. When one stack is full, you may need to create a new stack.

Popping an element at a specific substack will mean that some stacks aren't at full capacity. Is this an issue? There's no right answer, but you should think about how to handle this.

👊 Solution 1

In this solution I maintain a fixed size of stacks passed down when the class gets instantiated, whilst keeping a list of stacks.

Every time I push into the setOfStacks I keep track of how many I've inserted, if it equals the same number as the size of stacks I create a new stack at the start of the list.

Whenever I pop from the stack I verify if the stack is empty, if it is I remove that stack from the list.

public class SetOfStacks <T> {
    int sizeOfStack;
    int inserted = 0;
    ArrayList<Stack<T>> list = new ArrayList<>();

    public SetOfStacks(int sizeOfStack) {
        this.sizeOfStack = sizeOfStack;
        list.add(new Stack<T>());
    }

    public void push(T t) {
        list.get(0).push(t);
        inserted++;
        if (inserted == sizeOfStack) {
            list.add(0, new Stack<T>());
            inserted = 0;
        }
    }

    public T pop() {
        Stack<T> current = list.get(0);
        T value = current.pop();
        inserted--;
        if (current.isEmpty()) {
            list.remove(0);
        }

        return value;
    }
}

👊 Solution 2 - follow up

The follow-up question would be fairly simple due to the way we implemented the first one - using a list with stacks.

we could simply pop from the stack at the given index, if the stack becomes empty we simply remove it from the list.

public T popAt(int index) {
    Stack<T> current = list.get(index);
    T value = current.pop();
    if (current.isEmpty()) {
        list.remove(index);
    }
    return value;
}

---

Question borrowed from “Cracking the coding interview”