C++で指定された操作で最大スタックを構築するプログラム

次の操作をサポートする最大スタックを作成するとします-

• MaxStk（）これにより、最大スタックの新しいインスタンスが構築されます

• push（val）はvalをスタックに挿入します

• top（）は、スタックから最上位の要素を取得します

• max（）はスタックから最大の要素を取得します

• pop（）は、スタックから最上位の要素を削除して返します

• popmax（）は、スタックから最大の要素を削除して返します

次に、MasStk（）を呼び出して最大スタックを構築し、5、15、10などの3つの値をプッシュしてから、それぞれtop（）、max（）、popmax（）、max（）pop（）、top（）関数を呼び出します。その場合、初期スタックステータスは[5、15、10]になり、関数に対応する出力は10、15、15、10、10、5

これを解決するには、次の手順に従います-

• pos_index：=0

• 1つのセットstkを別のセットauxに定義する

• コンストラクターを定義します。これは特別なタスクを実行していません

• 関数push（）を定義します。これにはvalが必要です

• pos_index、valをstkに挿入します

• val、pos_indexをauxに挿入します

• （pos_indexを1増やします）

• 関数top（）を定義する

• stkが空の場合、-

  • -1を返す

• stkの最初のアイテムの2番目の値を返す

• 関数max（）

  を定義します

• auxが空の場合、-

  • -1を返す

• auxの最初のアイテムの最初の値を返す

• 関数pop（）

  を定義します

• stkが空の場合、-

  • -1を返す

• id：=stkの最初のアイテムの最初の値、ret=stkの最初のアイテムの2番目の値

• stkの最初の要素をstkから削除する

• auxからペア（ret、id）を削除する

• retを返す

• 関数popmax（）

  を定義します

• auxが空の場合、-

  • -1を返す

• ret：=auxの最初のアイテムの最初の値、id=auxの最初のアイテムの2番目の値

• auxの最初の要素をauxから削除する

• stkからpair（id、ret）を削除する

• retを返す

理解を深めるために、次の実装を見てみましょう-

例

#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