C++で補助スタックを使わずにO(1)でスタックの最大値を取得する方法

スタックに格納されている要素の中から最大値をO(1)の時間で取得できるスタックを実装したいと考えます。ただし、ここには重要な制約があります。補助スタックなどの追加データ構造を使用してはならず、追加スペースはO(1)でなければなりません。

アルゴリズムのポイント

この問題は、ユーザー定義のスタッククラスに現在の最大値を保持する変数を持たせ、push時に数式を使って値を「エンコード」することで解決できます。各操作は次のように処理します。

• push操作：挿入する要素xが現在の最大値より大きい場合は「2 * x − max」をスタックにプッシュし、最大値をxに更新します。そうでなければ、xをそのままプッシュします。
• peek操作：スタックのトップ要素が最大値より大きければ、それはエンコードされた値なので最大値を返します。そうでなければトップ要素をそのまま返します。
• pop操作：トップ要素が最大値より大きい場合は、実際に削除される値は最大値なので、それを出力し「2 * max − トップ要素」を計算して以前の最大値を復元します。そうでなければトップ要素をそのまま出力します。

なぜこの手法が機能するのか

新しい最大値xをプッシュする際にスタックへ格納されるのは「2 * x − 旧max」という値です。この値は必ずxよりも大きくなるため、「トップ要素 ＞ 現在の最大値」という条件でエンコード済みの要素を判別できます。pop時には「2 * max − top ＝ 旧max」という計算により、一つ前の最大値が正確に復元されます。

C++による実装例

#include <iostream>
#include <stack>
using namespace std;
class CustomStack {
    stack<int> stk;
    int stack_max;
    public:
    void getMax() {
        if (stk.empty())
            cout << "Stack is empty"<<endl;
        else
            cout << "Maximum Element in the stack is: "<< stack_max <<endl;
    }
    void peek() {
        if (stk.empty()) {
            cout << "Stack is empty ";
            return;
        }
        int top = stk.top(); // Top element.
        cout << "Top Most Element is: "<<endl;
        (top > stack_max) ? cout << stack_max : cout << top;
    }
    void pop() {
        if (stk.empty()) {
            cout << "Stack is empty"<<endl;
            return;
        }
        cout << "Top Most Element Removed: ";
        int top = stk.top();
        stk.pop();
        if (top > stack_max) {
            cout << stack_max <<endl;
            stack_max = 2 * stack_max - top;
        } else
            cout << top <<endl;
    }
    void push(int element) {
        if (stk.empty()) {
            stack_max = element;
            stk.push(element);
            cout << "Element Inserted: " << element <<endl;
            return;
        }
        if (element > stack_max) {
            stk.push(2 * element - stack_max);
            stack_max = element;
        } else
        stk.push(element);
        cout << "Element Inserted: " << element <<endl;
    }
};
int main() {
    CustomStack stk;
    stk.push(4);
    stk.push(6);
    stk.getMax();
    stk.push(8);
    stk.push(20);
    stk.getMax();
    stk.pop();
    stk.getMax();
    stk.pop();
    stk.peek();
}

実行結果

Element Inserted: 4
Element Inserted: 6
Maximum Element in the stack is: 6
Element Inserted: 8
Element Inserted: 20
Maximum Element in the stack is: 20
Top Most Element Removed: 20
Maximum Element in the stack is: 8
Top Most Element Removed: 8
Top Most Element is:
6

計算量

getMax、peek、push、popのすべての操作がO(1)時間で完了し、追加で必要な記憶領域は最大値を保持する1つの整数変数のみです。このため、メモリ制約が厳しい環境でも効率的に動作する実装といえます。