Algorithm (Design, Heap)

1. First we note that the problem could be essentially formulated abstractly as: given an infinite list of bounded stacks, find the right most nonempty bounded stack and left most stack yet to reach the bound efficiently and perform push and pop operations on them.
2. This suggests that we could maintain following states:
   1. stacks: the lists of stacks that fits the specification given by the problem. The list could implemented by std::vector.
   2. nonempty: a sorted_set that contains all stacks (represented by indices) in stacks that is not empty, i.e. $$\texttt{nonempty}=\{i\in\{0,…,\texttt{size(stacks})-1\}:\texttt{size(stacks[i])}>0\}.$$
   3. available: a sorted_set that contains all stacks (represented by indices) in stacks whose size is below capacity, i.e. $$\texttt{available}=\{i\in\{0,…,\texttt{size(stacks)}-1\}:0<\texttt{size(stacks[i])}<\texttt{capacity}\}.$$
   4. last_touched: the last stack (represented by index) in stacks on which we made modifications (either push or pop)
   5. size: the current size of stacks. We could live without it. But it makes some operations easier.
3. After each modification, we need to ensure the variables defined in the state are updated to fit the invariant. Most of the work is focused on adjusting nonempty and available:
   1. Once a stack $s$ in stack reaches the capacity, its index should be deleted from available
   2. Once a stack $s$ in stack becomes available after pop, we should insert it into available and selectively insert it into nonempty depending on the situation.
   3. We also need to ensure the size of stack is large enough when pushing elements. A helper function named ensure_capacity was used for this purpose. For details, see the actual code.
4. The sorted_set data structure could be implemented using either std::set or std::priority_queue with approximately same complexity. However, if latter is used, the deletion operation has to be lazy, which is sometimes tricky. We provide both implementations.

Code (Cpp17)

class DinnerPlates {
 private:
  std::vector<std::stack<int>> stacks_;
  std::set<int, std::greater<int>> nonempty_;
  std::set<int, std::less<int>> available_;
  std::optional<int> last_touched_;
  std::size_t size_;
  const int capacity_;

 private:
  std::optional<int> left_most_available() {
    if (std::empty(available_))
      return {};
    else
      return *std::begin(available_);
  }

  std::optional<int> right_most_nonempty() {
    if (std::empty(nonempty_))
      return {};
    else
      return *std::begin(nonempty_);
  }

  void ensure_state_invariant() {
    if (not last_touched_)
      return;
    else if (std::size(stacks_[*last_touched_]) >= capacity_) {
      nonempty_.emplace(*last_touched_);
      available_.erase(*last_touched_);
    }
    else if (std::size(stacks_[*last_touched_]) < capacity_) {
      available_.emplace(*last_touched_);
      if (std::size(stacks_[*last_touched_]) > 0)
        nonempty_.emplace(*last_touched_);
      else
        nonempty_.erase(*last_touched_);
    }
  };

  void ensure_capacity(std::size_t growth_factor = 10) {
    if (not left_most_available()) {
      const auto N = std::size(stacks_);
      for (int i = 0; i < growth_factor; ++i) {
        stacks_.emplace_back(std::stack<int>{});
        available_.emplace(N + i);
        ++size_;
      }
    }
  };

 public:
  DinnerPlates(int capacity) : stacks_{},
                               nonempty_{},
                               available_{},
                               last_touched_{},
                               capacity_{capacity},
                               size_(0) {
    ensure_capacity();
  };
  void push(int val) {
    ensure_capacity();
    const auto insertion_point = left_most_available();
    if (insertion_point.has_value()) {
      stacks_[*insertion_point].emplace(val);
      last_touched_ = insertion_point;
      ensure_state_invariant();
    }
  }

  int pop() {
    const auto deletion_point = right_most_nonempty();
    if (deletion_point) {
      const auto result = stacks_[*deletion_point].top();
      stacks_[*deletion_point].pop();
      last_touched_ = deletion_point;
      ensure_state_invariant();
      return result;
    }
    else
      return -1;
  }

  int popAtStack(int index) {
    if (index < size_ and not std::empty(stacks_[index])) {
      const auto result = stacks_[index].top();
      stacks_[index].pop();
      last_touched_ = index;
      ensure_state_invariant();
      return result;
    }
    else
      return -1;
  }
};

namespace lazy_priority_queue_version {

class DinnerPlates {
 private:
  std::vector<std::stack<int>> stacks_;
  std::priority_queue<int, std::vector<int>, std::greater<int>> available_;
  std::priority_queue<int, std::vector<int>, std::less<int>> nonempty_;
  std::optional<int> last_touched_;
  std::size_t size_;
  int capacity_;

 private:
  std::optional<int> left_most_available() {
    while (not empty(available_) and std::size(stacks_[available_.top()]) >= capacity_)
      available_.pop();
    if (std::empty(available_))
      return {};
    else
      return available_.top();
  }

  std::optional<int> right_most_nonempty() {
    while (not empty(nonempty_) and std::size(stacks_[nonempty_.top()]) == 0)
      nonempty_.pop();
    if (std::empty(nonempty_))
      return {};
    else
      return nonempty_.top();
  }

  void ensure_state_invariant() {
    if (not last_touched_)
      return;
    else if (std::size(stacks_[*last_touched_]) >= capacity_) {
      nonempty_.emplace(*last_touched_);
    }
    else if (std::size(stacks_[*last_touched_]) < capacity_) {
      available_.emplace(*last_touched_);
      if (std::size(stacks_[*last_touched_]) > 0)
        nonempty_.emplace(*last_touched_);
    }
  };

  void ensure_capacity() {
    if (not left_most_available()) {
      const auto N = std::size(stacks_);
      for (int i = 0; i < 10; ++i) {
        stacks_.emplace_back(std::stack<int>{});
        available_.emplace(N + i);
        ++size_;
      }
    }
  };

 public:
  DinnerPlates(int capacity) : stacks_{},
                               nonempty_{},
                               available_{},
                               last_touched_{},
                               capacity_{capacity},
                               size_(0) {
    ensure_capacity();
  };
  void push(int val) {
    ensure_capacity();
    const auto insertion_point = left_most_available();
    if (insertion_point.has_value()) {
      stacks_[*insertion_point].emplace(val);
      last_touched_ = insertion_point;
      ensure_state_invariant();
    }
  }

  int pop() {
    const auto deletion_point = right_most_nonempty();
    if (deletion_point) {
      const auto result = stacks_[*deletion_point].top();
      stacks_[*deletion_point].pop();
      last_touched_ = deletion_point;
      ensure_state_invariant();
      return result;
    }
    else
      return -1;
  }

  int popAtStack(int index) {
    if (index < size_ and not std::empty(stacks_[index])) {
      const auto result = stacks_[index].top();
      stacks_[index].pop();
      last_touched_ = index;
      ensure_state_invariant();
      return result;
    }
    else
      return -1;
  }
};
}  // end of namespace lazy_priority_queue_version