C++でスタックシーケンスを検証する

2つのシーケンスが異なる値でプッシュおよびポップされたとすると、これが最初は空のスタックでのプッシュおよびポップ操作のシーケンスの結果である可能性がある場合にのみ、trueを見つける必要があります。したがって、入力がpush =[1,2,3,4,5]、pop =[4,5,3,2,1]の場合、出力はtrueになります。 push（1）、push（2）、push（3）、push（4）、pop（）：4、push（5）、pop（）：5、pop（）：3、pop（）：を使用できます。 2、pop（）：1

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

• Solve（）という1つのメソッドを作成します。これには、プッシュおよびポップされた配列が必要です

• スタックstを定義し、インデックスを設定します：=0

• 0からプッシュされた配列のサイズまでの範囲のiの場合

  • push push [i] into st

  • popped [index] =スタックトップ要素の場合、

    • インデックス：=インデックス+ 1

    • スタックからポップ

    • stが空ではなく、popped [index] =top of st

      • インデックス：=インデックス+ 1

    • stから削除

• インデックス<ポップのサイズ

  • popped [index] =スタックトップの場合、

    • インデックスを1増やします

    • スタックから削除

  • それ以外の場合はループから出てきます

• スタックが空の場合はtrueを返します

• この解決メソッドは、以下のようなメインセクションから呼び出されます-

• リターンソルブ（プッシュ、ポップ）

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

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool solve(vector<int>& pushed, vector<int>& popped){
      stack <int> st;
      int currentIndexOfPopped = 0;
      for(int i =0;i<pushed.size();i++){
         st.push(pushed[i]);
         if(popped[currentIndexOfPopped] == st.top()){
            currentIndexOfPopped++;
            st.pop();
            while(!st.empty() && popped[currentIndexOfPopped]==st.top()){
               currentIndexOfPopped++;
               st.pop();
            }
         }
      }
      while(currentIndexOfPopped <popped.size()){
         if (popped[currentIndexOfPopped]==st.top()){
            currentIndexOfPopped++;
            st.pop();
         }else{
            break;
         }
      }
      return st.empty();
   }
   bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
      Solution s;
      bool flag = s.solve(pushed, popped);
      return flag;
   }
};
main(){
   vector<int> v = {1,2,3,4,5};
   vector<int> v1 = {4,5,3,2,1};
   Solution ob;
   cout << (ob.validateStackSequences(v, v1));
}

入力

[1,2,3,4,5]
[4,5,3,2,1]

出力

1