Algorithm (Design)

1. We keep track of three states:

   1. max_freq The maximum frequency currently encountered.
   2. data: A hashmap between frequency and numbers that possesses that frequency, stored in a stack.
   3. freq: A hashmap which tracks the frequencies of all numbers currently inside data.

2. When pushing a number $x$ into the FreqStack, we

   1. Increase the counter for $x$ in freq
   2. Update max_freq

3. When poping a number out of FreqStack, we

   1. Retrieve the top element of data[max_freq] and save it into a temp variable, which we denote as $T$.
   2. Update max_freq accordingly.
   3. Return $T$.

Code (Cpp17)

class FreqStack {
 private:
  int max_freq_;
  std::unordered_map<int, std::deque<int>> data_;
  std::unordered_map<int, int> freq_;

 public:
  FreqStack() :max_freq_{INT_MIN}, data_{}, freq_{} {}

  void push(int x) {
    data_[++freq_[x]].emplace_back(x);
    max_freq_ = std::max(max_freq_, freq_[x]);
  }

  int pop() {
    const auto res = data_[max_freq_].back();
    --freq_[res];
    if (size((data_[max_freq_].pop_back(), data_[max_freq_])) == 0)
      --max_freq_;
    return res;
  }
};