C++でインクリメント操作を使用してスタックを設計する

• CustomStack（int maxSize）これは、スタック内の要素の最大数であるmaxSizeでオブジェクトを初期化するか、スタックがmaxSizeに達した場合は何もしません。

• void push（int x）これは、スタックがmaxSizeに達していない場合に、スタックの一番上にxを挿入します。

• int pop（）これにより、スタックの最上位が削除されて返されます。スタックが空の場合は-1が返されます。

• void inc（int k、int val）これは、スタックの一番下のk要素をvalだけインクリメントします。スタック内の要素がk未満の場合は、スタック内のすべての要素をインクリメントするだけです。

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

• 2つの配列stとincを定義し、1つの整数型データキャップを作成します

• イニシャライザで、cap：=Nを設定し、inc：=サイズN+10の新しい配列を設定します

• push（x）メソッドの場合、スタックのサイズが上限でない場合は、xをstに挿入します。

• pop（）操作は-

  のようになります

• stが空の場合は、-1を返します

• それ以外の場合

  • スタックのトップ：=スタックのトップ+inc[スタックのトップインデックス]

  • スタックに要素がある場合は、inc [size of st –2]をinc[size of st – 1]

    だけ増やします。

  • inc [sのサイズ-1]：=0

  • x：=stの最後の要素

  • xを返す

• inc（）メソッドは次のように機能します-

• kを1減らします

• k：=kの最小値とstのサイズ– 1

• k <0の場合、戻ります

• inc[k]をvalだけ増やします。

例（C ++）

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

#include <bits/stdc++.h>
using namespace std;
class CustomStack {
public:
   vector <int> st;
   vector <int> inc;
   int cap;
   CustomStack(int N) {
      cap = N;
      inc = vector <int>(N + 10);
   }
   void push(int x) {
      if(st.size() == cap) return;
      st.push_back(x);
   }
   int pop() {
      if(st.empty()) return -1;
      else{
         st.back() += inc[st.size() - 1];
         if(st.size() - 1 > 0 ){
            inc[st.size() - 2] += inc[st.size() - 1];
         }
         inc[st.size() - 1] = 0;
         int x = st.back();
         st.pop_back();
         return x;
      }
   }
   void increment(int k, int val) {
      k--;
      k = min(k, (int)st.size() - 1);
      if(k < 0) return;
      inc[k] += val;
   }
};
main(){
   CustomStack ob(3);
   ob.push(1);
   ob.push(2);
   cout << ob.pop() << endl;
   ob.push(2);
   ob.push(3);
   ob.push(4);
   ob.increment(5, 100);
   ob.increment(2, 100);
   cout << ob.pop() << endl;
   cout << ob.pop() << endl;
   cout << ob.pop() << endl;
   cout << ob.pop() << endl;
}

入力

See the main() in the program

出力

2
103
202
201
-1