C++で最大頻度スタック（FreqStack）を実装する方法

この記事では、整数を管理する特殊なスタック「FreqStack」をC++で実装する方法を解説します。FreqStackは、以下の2つの操作をサポートするデータ構造です。

• push(x)：整数xをスタックにプッシュします。
• pop()：スタック内で最も出現頻度の高い要素を取り除き、その値を返します。同じ頻度の要素が複数存在する場合は、スタックのトップに最も近い（最後に追加された）要素が取り除かれます。

例えば、7、9、7、9、6、7の順に要素をプッシュした後、pop()を4回呼び出すと、出力は7、9、7、6となります。

アルゴリズムの考え方

この問題は、ハッシュマップとスタックを組み合わせることで効率的に解くことができます。必要なデータ構造は次の通りです。

• 各要素の出現回数を記録するマップcnt
• 頻度ごとに要素をグループ化するマップsts（キー：頻度、値：その頻度を持つ要素のスタック）
• 現在の最大頻度を保持する変数maxFreq（初期値は0）

push(x) の処理手順

• cnt[x]を1増やします。
• maxFreqをmax(maxFreq, cnt[x])で更新します。
• xをsts[cnt[x]]に挿入します。

pop() の処理手順

• maxKeyをmaxFreqとします。
• xをsts[maxKey]のトップ要素として取得します。
• sts[maxKey]からその要素を削除します。
• sts[maxKey]のサイズが0になった場合は、stsからmaxKeyを削除し、maxFreqを1減らします。
• cnt[x]を1減らします。
• xを返します。

仕組みのポイント

この実装の鍵は、「同じ頻度の要素を1つのスタックにまとめる」という点です。pushのたびに、要素はその新しい頻度に対応するスタックへ積まれていくため、pop時にはmaxFreqに対応するスタックのトップを見るだけで、「最も頻度が高く、かつ最も新しく追加された要素」を即座に取得できます。その結果、push・popどちらの操作も計算量O(1)で実行可能です。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
class FreqStack {
   public:
   unordered_map <int ,int > cnt;
   unordered_map <int, stack <int> >sts;
   int maxFreq = 0;
   FreqStack() {
      maxFreq = 0;
      cnt.clear();
      sts.clear();
   }
   void push(int x) {
      cnt[x]++;
      maxFreq = max(maxFreq, cnt[x]);
      sts[cnt[x]].push(x);
   }
   int pop() {
      int maxKey = maxFreq;
      int x = sts[maxKey].top();
      sts[maxKey].pop();
      if(sts[maxKey].size() == 0){
         sts.erase(maxKey);
         maxFreq--;
      }
      cnt[x]--;
      return x;
   }
};
main(){
   FreqStack ob;
   ob.push(7);
   ob.push(9);
   ob.push(7);
   ob.push(9);
   ob.push(6);
   ob.push(7);
   cout << (ob.pop()) << endl;
   cout << (ob.pop()) << endl;
   cout << (ob.pop()) << endl;
   cout << (ob.pop()) << endl;
}

入力

push(7)、push(9)、push(7)、push(9)、push(6)、push(7) を順に実行し、その後pop()を4回呼び出します。

出力

7
9
7
6