README_EN.md

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

Python3

Java

TypeScript

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)
 */

...