Question

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

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