03.03. Stack of Plates

Description

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.

You should delete the sub-stack when it becomes empty. pop, popAt should return -1 when there's no element to pop.

Example1:


 Input:

["StackOfPlates", "push", "push", "popAt", "pop", "pop"]

[[1], [1], [2], [1], [], []]

 Output:

[null, null, null, 2, 1, -1]

 Explanation:

Example2:


 Input:

["StackOfPlates", "push", "push", "push", "popAt", "popAt", "popAt"]

[[2], [1], [2], [3], [0], [0], [0]]

 Output:

[null, null, null, null, 2, 1, 3]

Solutions

Solution 1: Simulation

We can use a list of stacks $stk$ to simulate this process, initially $stk$ is empty.

When the push method is called, if $cap$ is 0, return directly. Otherwise, if $stk$ is empty or the length of the last stack in $stk$ is greater than or equal to $cap$, then create a new stack. Then add the element $val$ to the last stack in $stk$. The time complexity is $O(1)$.
When the pop method is called, return the result of popAt(|stk| - 1). The time complexity is $O(1)$.
When the popAt method is called, if $index$ is not in the range $[0, |stk|)$, return -1. Otherwise, return the top element of $stk[index]$ and pop it out. If $stk[index]$ is empty after popping, remove it from $stk$. The time complexity is $O(1)$.

The space complexity is $O(n)$, where $n$ is the number of elements.