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]
class StackOfPlates:
def __init__(self, cap: int):
self.cap = cap
self.stk = []
def push(self, val: int) -> None:
if self.cap == 0:
return
if not self.stk or len(self.stk[-1]) >= self.cap:
self.stk.append([])
self.stk[-1].append(val)
def pop(self) -> int:
return self.popAt(len(self.stk) - 1)
def popAt(self, index: int) -> int:
ans = -1
if 0 <= index < len(self.stk):
ans = self.stk[index].pop()
if not self.stk[index]:
self.stk.pop(index)
return ans
# Your StackOfPlates object will be instantiated and called as such:
# obj = StackOfPlates(cap)
# obj.push(val)
# param_2 = obj.pop()
# param_3 = obj.popAt(index)class StackOfPlates {
private List<Deque<Integer>> stk = new ArrayList<>();
private int cap;
public StackOfPlates(int cap) {
this.cap = cap;
}
public void push(int val) {
if (cap == 0) {
return;
}
if (stk.isEmpty() || stk.get(stk.size() - 1).size() >= cap) {
stk.add(new ArrayDeque<>());
}
stk.get(stk.size() - 1).push(val);
}
public int pop() {
return popAt(stk.size() - 1);
}
public int popAt(int index) {
int ans = -1;
if (index >= 0 && index < stk.size()) {
ans = stk.get(index).pop();
if (stk.get(index).isEmpty()) {
stk.remove(index);
}
}
return ans;
}
}
/**
* Your StackOfPlates object will be instantiated and called as such:
* StackOfPlates obj = new StackOfPlates(cap);
* obj.push(val);
* int param_2 = obj.pop();
* int param_3 = obj.popAt(index);
*/class StackOfPlates {
public:
StackOfPlates(int cap) {
this->cap = cap;
}
void push(int val) {
if (!cap) return;
if (stk.empty() || stk[stk.size() - 1].size() >= cap) stk.emplace_back(stack<int>());
stk[stk.size() - 1].push(val);
}
int pop() {
return popAt(stk.size() - 1);
}
int popAt(int index) {
int ans = -1;
if (index >= 0 && index < stk.size()) {
ans = stk[index].top();
stk[index].pop();
if (stk[index].empty()) {
stk.erase(stk.begin() + index);
}
}
return ans;
}
private:
vector<stack<int>> stk;
int cap;
};
/**
* Your StackOfPlates object will be instantiated and called as such:
* StackOfPlates* obj = new StackOfPlates(cap);
* obj->push(val);
* int param_2 = obj->pop();
* int param_3 = obj->popAt(index);
*/type StackOfPlates struct {
stk [][]int
cap int
}
func Constructor(cap int) StackOfPlates {
return StackOfPlates{[][]int{}, cap}
}
func (this *StackOfPlates) Push(val int) {
if this.cap == 0 {
return
}
if len(this.stk) == 0 || len(this.stk[len(this.stk)-1]) >= this.cap {
this.stk = append(this.stk, []int{})
}
this.stk[len(this.stk)-1] = append(this.stk[len(this.stk)-1], val)
}
func (this *StackOfPlates) Pop() int {
return this.PopAt(len(this.stk) - 1)
}
func (this *StackOfPlates) PopAt(index int) int {
ans := -1
if index >= 0 && index < len(this.stk) {
t := this.stk[index]
ans = t[len(t)-1]
this.stk[index] = this.stk[index][:len(t)-1]
if len(this.stk[index]) == 0 {
this.stk = append(this.stk[:index], this.stk[index+1:]...)
}
}
return ans
}
/**
* Your StackOfPlates object will be instantiated and called as such:
* obj := Constructor(cap);
* obj.Push(val);
* param_2 := obj.Pop();
* param_3 := obj.PopAt(index);
*/class StackOfPlates {
private cap: number;
private stacks: number[][];
constructor(cap: number) {
this.cap = cap;
this.stacks = [];
}
push(val: number): void {
if (this.cap === 0) {
return;
}
const n = this.stacks.length;
const stack = this.stacks[n - 1];
if (stack == null || stack.length === this.cap) {
this.stacks.push([val]);
} else {
stack.push(val);
}
}
pop(): number {
const n = this.stacks.length;
if (n === 0) {
return -1;
}
const stack = this.stacks[n - 1];
const res = stack.pop();
if (stack.length === 0) {
this.stacks.pop();
}
return res;
}
popAt(index: number): number {
if (index >= this.stacks.length) {
return -1;
}
const stack = this.stacks[index];
const res = stack.pop();
if (stack.length === 0) {
this.stacks.splice(index, 1);
}
return res;
}
}
/**
* Your StackOfPlates object will be instantiated and called as such:
* var obj = new StackOfPlates(cap)
* obj.push(val)
* var param_2 = obj.pop()
* var param_3 = obj.popAt(index)
*/