C++で周波数スタック（FreqStack）を実装する方法

この記事では、C++を使って「周波数スタック（FrequencyStack）」と呼ばれる特殊なスタックを構築する方法を解説します。周波数スタックは、以下の2つの操作をサポートするデータ構造です。

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

例えば、7, 9, 7, 9, 6, 7 の順で要素を追加し、その後 pop() を4回呼び出すと、出力はそれぞれ 7, 9, 7, 6 となります。

アルゴリズムの考え方

この問題を効率的に解くために、以下の手順で実装を進めます。

• 各要素の出現回数を記録するマップ cnt を定義します。
• 頻度ごとに要素をグループ化して保持するマップ sts を定義します（キー：頻度、値：その頻度の要素を格納したスタック）。
• 現在の最大頻度を追跡する変数 maxFreq を用意し、初期値は 0 とします。

append(x) の処理手順

1. cnt[x] を1増やします。
2. maxFreq を maxFreq と cnt[x] の大きい方で更新します。
3. x を sts[cnt[x]]（x の新しい頻度に対応するスタック）にプッシュします。

pop() の処理手順

1. maxKey := maxFreq とします。
2. sts[maxKey] のトップ要素を x として取得します。
3. sts[maxKey] からその要素を削除（ポップ）します。
4. もし sts[maxKey] が空になった場合は、sts から maxKey を削除し、maxFreq を1減らします。
5. cnt[x] を1減らします。
6. x を返します。

このアプローチにより、append と 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 append(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.append(7);
    ob.append(9);
    ob.append(7);
    ob.append(9);
    ob.append(6);
    ob.append(7);
    cout << (ob.pop()) << endl;
    cout << (ob.pop()) << endl;
    cout << (ob.pop()) << endl;
    cout << (ob.pop()) << endl;
}

入力

ob.append(7);
ob.append(9);
ob.append(7);
ob.append(9);
ob.append(6);
ob.append(7);
cout << (ob.pop()) << endl;
cout << (ob.pop()) << endl;
cout << (ob.pop()) << endl;
cout << (ob.pop()) << endl;

出力

7
9
7
6

動作の解説

上記の例では、要素 7 が3回、9 が2回、6 が1回追加されています。

• 1回目の pop()：最大頻度は3（要素 7）なので、7 が返されます。
• 2回目の pop()：最大頻度は2（要素 7 と 9）ですが、9 の方がスタックのトップに近いため、9 が返されます。
• 3回目の pop()：同様に頻度2の要素の中でトップに近いのは 7 なので、7 が返されます。
• 4回目の pop()：残りの要素の中で最も頻度が高いのは 9（頻度1）なので、9…ではなく、この時点でのスタック状態に応じて 6 が返されます。

このように、頻度ごとのスタックを管理することで、「最も頻度が高く、かつ最新に近い要素」を常に効率よく取り出せるデータ構造が実現できます。ハッシュマップとスタックを組み合わせたこの手法は、LeetCode の「Maximum Frequency Stack」などの問題でも応用される重要なパターンです。