The Dinner Plate Stacks problem asks you to design a data structure that simulates a stack of dinner plates. Each stack has a fixed capacity. When a stack is full, you start a new stack. You must support the following operations:
push(val): Push the given value onto the leftmost stack that is not full. If all stacks are full, create a new stack.pop(): Remove and return the value from the top of the rightmost non-empty stack. If all stacks are empty, return -1.popAtStack(index): Remove and return the value from the top of the stack at the given index. If the stack is empty, return -1.
You are given the capacity of each stack. The number of stacks is dynamic and grows as needed. You must efficiently support all operations, even as stacks become empty or full.
Key constraints:
capacity plates.At first glance, this problem seems similar to managing multiple stacks, but with the added twist of fixed capacity and dynamic growth. A brute-force approach would involve keeping a list of stacks and searching linearly for the appropriate stack to push or pop. However, this would be inefficient, especially for large numbers of stacks and frequent operations.
To optimize, we need to quickly find:
push).pop).popAtStack).The main challenge is efficiently tracking which stacks are available for pushing and which stacks still contain plates for popping, especially as stacks become empty or full after operations.
To efficiently manage the stacks and their capacities, we use the following strategy:
-1.
By combining a list of stacks, a min-heap for available stacks, and a pointer for the rightmost non-empty stack, we can achieve efficient push and pop operations.
Suppose capacity = 2. We perform the following operations:
push(1)
push(2)
push(3)
push(4)
push(5)
popAtStack(0)
push(20)
push(21)
popAtStack(0)
popAtStack(2)
pop()
pop()
pop()
pop()
pop()
Step-by-step:
push(1): Stack 0: [1]push(2): Stack 0: [1,2] (full)push(3): Stack 1: [3]push(4): Stack 1: [3,4] (full)push(5): Stack 2: [5]popAtStack(0): Pops 2 from Stack 0: [1]push(20): Stack 0 has space, so: [1,20]push(21): Stack 2: [5,21] (full)popAtStack(0): Pops 20: [1]popAtStack(2): Pops 21: [5]pop(): Pops 5 from Stack 2 (now empty)pop(): Pops 4 from Stack 1: [3]pop(): Pops 3 from Stack 1 (now empty)pop(): Pops 1 from Stack 0 (now empty)pop(): All stacks empty, returns -1Brute-force approach:
The Dinner Plate Stacks problem is a great exercise in dynamic data structure design. By combining an array of stacks, a min-heap for tracking available positions, and a pointer for the rightmost non-empty stack, we can efficiently support all required operations. The key insights are to avoid scanning the stacks linearly and to use auxiliary data structures for fast lookups and updates. This approach ensures that even as the stacks grow and shrink, all operations remain efficient and the solution remains elegant.
import heapq
class DinnerPlates:
def __init__(self, capacity: int):
self.capacity = capacity
self.stacks = []
self.available = [] # min-heap for available stacks (not full)
self.rightmost = -1 # index of rightmost non-empty stack
def push(self, val: int) -> None:
# Clean up heap from stale indices
while self.available and self.available[0] < len(self.stacks) and len(self.stacks[self.available[0]]) == self.capacity:
heapq.heappop(self.available)
# Find leftmost available stack
if self.available:
idx = heapq.heappop(self.available)
self.stacks[idx].append(val)
if len(self.stacks[idx]) < self.capacity:
heapq.heappush(self.available, idx)
self.rightmost = max(self.rightmost, idx)
else:
self.stacks.append([val])
idx = len(self.stacks) - 1
if self.capacity > 1:
heapq.heappush(self.available, idx)
self.rightmost = idx
def pop(self) -> int:
while self.rightmost >= 0 and (self.rightmost >= len(self.stacks) or not self.stacks[self.rightmost]):
self.rightmost -= 1
if self.rightmost == -1:
return -1
val = self.stacks[self.rightmost].pop()
if len(self.stacks[self.rightmost]) == self.capacity - 1:
heapq.heappush(self.available, self.rightmost)
if not self.stacks[self.rightmost]:
while self.rightmost >= 0 and not self.stacks[self.rightmost]:
self.rightmost -= 1
return val
def popAtStack(self, index: int) -> int:
if 0 <= index < len(self.stacks) and self.stacks[index]:
val = self.stacks[index].pop()
if len(self.stacks[index]) == self.capacity - 1:
heapq.heappush(self.available, index)
if index == self.rightmost and not self.stacks[index]:
while self.rightmost >= 0 and not self.stacks[self.rightmost]:
self.rightmost -= 1
return val
return -1
#include <vector>
#include <queue>
using namespace std;
class DinnerPlates {
int cap;
vector<vector<int>> stacks;
priority_queue<int, vector<int>, greater<int>> available;
int rightmost = -1;
public:
DinnerPlates(int capacity) : cap(capacity) {}
void push(int val) {
while (!available.empty() && available.top() < stacks.size() && stacks[available.top()].size() == cap)
available.pop();
int idx;
if (!available.empty()) {
idx = available.top(); available.pop();
stacks[idx].push_back(val);
if (stacks[idx].size() < cap) available.push(idx);
rightmost = max(rightmost, idx);
} else {
stacks.push_back({val});
idx = stacks.size() - 1;
if (cap > 1) available.push(idx);
rightmost = idx;
}
}
int pop() {
while (rightmost >= 0 && (rightmost >= stacks.size() || stacks[rightmost].empty()))
rightmost--;
if (rightmost == -1) return -1;
int val = stacks[rightmost].back();
stacks[rightmost].pop_back();
if (stacks[rightmost].size() == cap - 1)
available.push(rightmost);
if (stacks[rightmost].empty()) {
while (rightmost >= 0 && stacks[rightmost].empty())
rightmost--;
}
return val;
}
int popAtStack(int index) {
if (index >= 0 && index < stacks.size() && !stacks[index].empty()) {
int val = stacks[index].back();
stacks[index].pop_back();
if (stacks[index].size() == cap - 1)
available.push(index);
if (index == rightmost && stacks[index].empty()) {
while (rightmost >= 0 && stacks[rightmost].empty())
rightmost--;
}
return val;
}
return -1;
}
};
import java.util.*;
class DinnerPlates {
private int capacity;
private List<Deque<Integer>> stacks;
private PriorityQueue<Integer> available;
private int rightmost;
public DinnerPlates(int capacity) {
this.capacity = capacity;
this.stacks = new ArrayList<>();
this.available = new PriorityQueue<>();
this.rightmost = -1;
}
public void push(int val) {
while (!available.isEmpty() && available.peek() < stacks.size() && stacks.get(available.peek()).size() == capacity)
available.poll();
int idx;
if (!available.isEmpty()) {
idx = available.poll();
stacks.get(idx).addLast(val);
if (stacks.get(idx).size() < capacity)
available.offer(idx);
rightmost = Math.max(rightmost, idx);
} else {
Deque<Integer> newStack = new ArrayDeque<>();
newStack.addLast(val);
stacks.add(newStack);
idx = stacks.size() - 1;
if (capacity > 1)
available.offer(idx);
rightmost = idx;
}
}
public int pop() {
while (rightmost >= 0 && (rightmost >= stacks.size() || stacks.get(rightmost).isEmpty()))
rightmost--;
if (rightmost == -1)
return -1;
int val = stacks.get(rightmost).removeLast();
if (stacks.get(rightmost).size() == capacity - 1)
available.offer(rightmost);
if (stacks.get(rightmost).isEmpty()) {
while (rightmost >= 0 && stacks.get(rightmost).isEmpty())
rightmost--;
}
return val;
}
public int popAtStack(int index) {
if (index >= 0 && index < stacks.size() && !stacks.get(index).isEmpty()) {
int val = stacks.get(index).removeLast();
if (stacks.get(index).size() == capacity - 1)
available.offer(index);
if (index == rightmost && stacks.get(index).isEmpty()) {
while (rightmost >= 0 && stacks.get(rightmost).isEmpty())
rightmost--;
}
return val;
}
return -1;
}
}
class MinHeap {
constructor() {
this.heap = [];
}
push(val) {
this.heap.push(val);
this._bubbleUp(this.heap.length - 1);
}
pop() {
if (this.heap.length === 0) return undefined;
const top = this.heap[0];
const end = this.heap.pop();
if (this.heap.length) {
this.heap[0] = end;
this._sinkDown(0);
}
return top;
}
peek() {
return this.heap[0];
}
_bubbleUp(idx) {
const el = this.heap[idx];
while (idx > 0) {
const parentIdx = Math.floor((idx - 1) / 2);
if (this.heap[parentIdx] <= el) break;
this.heap[idx] = this.heap[parentIdx];
idx = parentIdx;
}
this.heap[idx] = el;
}
_sinkDown(idx) {
const length = this.heap.length;
const el = this.heap[idx];
while (true) {
let left = 2 * idx + 1;
let right = 2 * idx + 2;
let swap = null;
if (left < length && this.heap[left] < el) swap = left;
if (right < length && this.heap[right] < (swap === null ? el : this.heap[left])) swap = right;
if (swap === null) break;
this.heap[idx] = this.heap[swap];
idx = swap;
}
this.heap[idx] = el;
}
size() {
return this.heap.length;
}
}
class DinnerPlates {
constructor(capacity) {
this.capacity = capacity;
this.stacks = [];
this.available = new MinHeap();
this.rightmost = -1;
}
push(val) {
while (this.available.size() && this.available.peek() < this.stacks.length && this.stacks[this.available.peek()].length === this.capacity)
this.available.pop();
let idx;
if (this.available.size()) {
idx = this.available.pop();
this.stacks[idx].push(val);
if (this.stacks[idx].length < this.capacity)
this.available.push(idx);
this.rightmost = Math.max(this.rightmost, idx);
} else {
this.stacks.push([val]);
idx = this.stacks.length - 1;
if (this.capacity > 1)
this.available.push(idx);
this.rightmost = idx;
}
}
pop() {
while (this.rightmost >= 0 && (this.rightmost >= this.stacks.length || this.stacks[this.rightmost].length === 0))
this.rightmost--;
if (this.rightmost === -1)
return -1;
let val = this.stacks[this.rightmost].pop();
if (this.stacks[this.rightmost].length === this.capacity - 1)
this.available.push(this.rightmost);
if (this.stacks[this.rightmost].length === 0) {
while (this.rightmost >= 0 && this.stacks[this.rightmost].length === 0)
this.rightmost--;
}
return val;
}
popAtStack(index) {
if (index >= 0 && index < this.stacks.length && this.stacks[index].length) {
let val = this.stacks[index].pop();
if (this.stacks[index].length === this.capacity - 1)
this.available.push(index);
if (index === this.rightmost && this.stacks[index].length === 0) {
while (this.rightmost >= 0 && this.stacks[this.rightmost].length === 0)
this.rightmost--;
}
return val;
}
return -1;
}
}