## Algorithm

Problem Name: 1172. Dinner Plate Stacks

You have an infinite number of stacks arranged in a row and numbered (left to right) from `0`, each of the stacks has the same maximum capacity.

Implement the `DinnerPlates` class:

• `DinnerPlates(int capacity)` Initializes the object with the maximum capacity of the stacks `capacity`.
• `void push(int val)` Pushes the given integer `val` into the leftmost stack with a size less than `capacity`.
• `int pop()` Returns the value at the top of the rightmost non-empty stack and removes it from that stack, and returns `-1` if all the stacks are empty.
• `int popAtStack(int index)` Returns the value at the top of the stack with the given index `index` and removes it from that stack or returns `-1` if the stack with that given index is empty.

Example 1:

```Input
["DinnerPlates", "push", "push", "push", "push", "push", "popAtStack", "push", "push", "popAtStack", "popAtStack", "pop", "pop", "pop", "pop", "pop"]
[, , , , , , , , , , , [], [], [], [], []]
Output
[null, null, null, null, null, null, 2, null, null, 20, 21, 5, 4, 3, 1, -1]

Explanation:
DinnerPlates D = DinnerPlates(2);  // Initialize with capacity = 2
D.push(1);
D.push(2);
D.push(3);
D.push(4);
D.push(5);         // The stacks are now:  2  4
1  3  5
﹈ ﹈ ﹈
D.popAtStack(0);   // Returns 2.  The stacks are now:     4
1  3  5
﹈ ﹈ ﹈
D.push(20);        // The stacks are now: 20  4
1  3  5
﹈ ﹈ ﹈
D.push(21);        // The stacks are now: 20  4 21
1  3  5
﹈ ﹈ ﹈
D.popAtStack(0);   // Returns 20.  The stacks are now:     4 21
1  3  5
﹈ ﹈ ﹈
D.popAtStack(2);   // Returns 21.  The stacks are now:     4
1  3  5
﹈ ﹈ ﹈
D.pop()            // Returns 5.  The stacks are now:      4
1  3
﹈ ﹈
D.pop()            // Returns 4.  The stacks are now:   1  3
﹈ ﹈
D.pop()            // Returns 3.  The stacks are now:   1
﹈
D.pop()            // Returns 1.  There are no stacks.
D.pop()            // Returns -1.  There are still no stacks.
```

Constraints:

• `1 <= capacity <= 2 * 104`
• `1 <= val <= 2 * 104`
• `0 <= index <= 105`
• At most `2 * 105` calls will be made to `push`, `pop`, and `popAtStack`.

## Code Examples

### #1 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const DinnerPlates = function (capacity) {
this.pushIndex = 0
this.popIndex = 0
this.capacity = capacity
this.stacks = [[]]
}

DinnerPlates.prototype.push = function (val) {
while (
this.pushIndex < this.stacks.length &&
this.stacks[this.pushIndex].length === this.capacity
) {
this.pushIndex++
}
if (this.stacks.length === this.pushIndex) {
this.stacks[this.pushIndex] = [val]
} else {
this.stacks[this.pushIndex].push(val)
}
if (this.popIndex < this.pushIndex) {
this.popIndex = this.pushIndex
}
}

DinnerPlates.prototype.pop = function () {
while (this.stacks[this.popIndex].length === 0) {
if (this.popIndex > 0) {
this.popIndex--
} else {
return -1
}
}
const valueAtIndex = this.stacks[this.popIndex].pop()
if (this.pushIndex > this.popIndex) {
this.pushIndex = this.popIndex
}
return valueAtIndex
}

DinnerPlates.prototype.popAtStack = function (index) {
if (index >= this.stacks.length) return -1
if (index < this.pushIndex) this.pushIndex = index
return this.stacks[index].length > 0 ? this.stacks[index].pop() : -1
}
``````
Copy The Code &

Input

cmd
["DinnerPlates", "push", "push", "push", "push", "push", "popAtStack", "push", "push", "popAtStack", "popAtStack", "pop", "pop", "pop", "pop", "pop"] [, , , , , , , , , , , [], [], [], [], []]

Output

cmd
[null, null, null, null, null, null, 2, null, null, 20, 21, 5, 4, 3, 1, -1]

### #2 Code Example with Python Programming

```Code - Python Programming```

``````
class DinnerPlates:

def __init__(self, capacity: int):
self.c = capacity
self.stacks = []
self.l = [] # pushable
self.r = [] # poppable

def push(self, val: int) -> None:
if not self.l:
# if the rightmost is empty, clear it from self.r
while self.r and not self.stacks[-self.r]:
heapq.heappop(self.r)
i = 0 if not self.r else -self.r + 1
self.stacks.append([val])
heapq.heappush(self.r, -i)
if len(self.stacks[i]) < self.c:
heapq.heappush(self.l, i)
else:
i = self.l
# new poppable
if not self.stacks[i]:
heapq.heappush(self.r, -i)
self.stacks[i].append(val)
if len(self.stacks[i]) == self.c:
heapq.heappop(self.l)

def pop(self) -> int:
while self.r and not self.stacks[-self.r]:
heapq.heappop(self.r)
return self.popAtStack(-self.r) if self.r else -1

def popAtStack(self, index: int) -> int:
if index < len(self.stacks) and self.stacks[index]:
ret = self.stacks[index].pop()
if len(self.stacks[index]) == self.c - 1:
heapq.heappush(self.l, index)
return ret
return -1

``````
Copy The Code &

Input

cmd
["DinnerPlates", "push", "push", "push", "push", "push", "popAtStack", "push", "push", "popAtStack", "popAtStack", "pop", "pop", "pop", "pop", "pop"] [, , , , , , , , , , , [], [], [], [], []]

Output

cmd
[null, null, null, null, null, null, 2, null, null, 20, 21, 5, 4, 3, 1, -1]