C++で最大スタックを実装する方法：push・top・max・pop・popmax操作をサポートするデータ構造

問題概要

最大スタックとは、通常のスタック操作に加えて「現在の最大値の取得」や「最大値の削除」を効率よく行えるデータ構造です。ここでは、以下の操作をすべてサポートする最大スタックをC++で実装します。

• MaxStk()：最大スタックの新しいインスタンスを構築する
• push(val)：値 val をスタックに挿入する
• top()：スタックの最上位にある要素を取得する
• max()：スタック内の最大要素を取得する
• pop()：最上位の要素を取り除き、その値を返す
• popmax()：最大要素を取り除き、その値を返す

たとえば、MaxStk() でスタックを生成した後、5、15、10 の順に push し、続いて top()、max()、popmax()、max()、pop()、top() をこの順に呼び出すとします。このときスタックの初期状態は [5, 15, 10] であり、各呼び出しの出力は 10、15、15、10、10、5 となります。

アルゴリズム

この問題は、比較関数に greater を指定した std::set を2本用意することでエレガントに解けます。1つは挿入順序を管理する stk、もう1つは値の大小を管理する aux です。具体的な手順は以下のとおりです。

• 通し番号 pos_index を 0 で初期化する。
• pair<int, int> を保持する set 型の stk と aux を宣言する（どちらも降順ソート）。
• コンストラクタでは特別な処理は行わない。
• push(val)：
  • stk に (pos_index, val) を挿入する。
  • aux に (val, pos_index) を挿入する。
  • pos_index を 1 増やす。
• top()：
  • stk が空ならば -1 を返す。
  • stk の先頭要素の2番目の値（＝最後に挿入された値）を返す。
• max()：
  • aux が空ならば -1 を返す。
  • aux の先頭要素の1番目の値（＝現在の最大値）を返す。
• pop()：
  • stk が空ならば -1 を返す。
  • id ← stk の先頭要素の1番目の値、ret ← 2番目の値とする。
  • stk の先頭要素を削除する。
  • aux から (ret, id) を削除する。
  • ret を返す。
• popmax()：
  • aux が空ならば -1 を返す。
  • ret ← aux の先頭要素の1番目の値、id ← 2番目の値とする。
  • aux の先頭要素を削除する。
  • stk から (id, ret) を削除する。
  • ret を返す。

この手法のポイント

set の各要素を (番号, 値) のペアとして扱っている点が重要です。同じ値が複数回 push されても、通し番号 pos_index によって各要素を一意に識別できるため、重複値が存在しても正しく削除できます。さらに、比較関数に greater を指定しているため、begin() は常に「最大の要素」（stk では最後に挿入された要素）を指します。その結果、すべての操作を O(log n) の計算量で実行できます。

C++ 実装例

#include <bits/stdc++.h>
using namespace std;
class MaxStk {
    int pos_index = 0;
    set<pair<int, int>, greater<>> stk, aux;
    public:
    MaxStk() {}
    void push(int val) {
        stk.emplace(pos_index, val);
        aux.emplace(val, pos_index);
        pos_index++;
    }
    int top() {
        if (stk.empty())
            return -1;
        return stk.begin()->second;
    }
    int max() {
        if (aux.empty())
            return -1;
        return aux.begin()->first;
    }
    int pop() {
        if (stk.empty())
            return -1;
        int id = stk.begin()->first, ret = stk.begin()->second;
        stk.erase(stk.begin());
        aux.erase({ret, id});
        return ret;
    }
    int popmax() {
        if (aux.empty())
            return -1;
        int ret = aux.begin()->first, id = aux.begin()->second;
        aux.erase(aux.begin());
        stk.erase({id, ret});
        return ret;
    }
};
int main(){
    MaxStk max_stk;
    max_stk.push(5);
    max_stk.push(15);
    max_stk.push(10);
    cout << max_stk.top() << endl;
    cout << max_stk.max() << endl;
    cout << max_stk.popmax() << endl;
    cout << max_stk.max() << endl;
    cout << max_stk.pop() << endl;
    cout << max_stk.top() << endl;
}

入力例

max_stk.push(5)
max_stk.push(15)
max_stk.push(10)
max_stk.top()
max_stk.max()
max_stk.popmax()
max_stk.max()
max_stk.pop()
max_stk.top()

出力例

10
15
15
10
10
5

実行の流れを確認してみましょう。push を3回行った時点でスタックは [5, 15, 10] になっています。最初の top() は最上位の 10 を返し、max() は最大値 15 を返します。popmax() で 15 が取り除かれた後の max() は 10 となり、続く pop() も 10 を返します。最後に、スタックに残った 5 が top() によって返されます。