C++ এ স্ট্যাক সিকোয়েন্স যাচাই করুন

ধরুন আমাদের কাছে দুটি সিকোয়েন্স পুশ করা এবং স্বতন্ত্র মান সহ পপ করা হয়েছে, আমাদের সত্য খুঁজে বের করতে হবে যদি এবং শুধুমাত্র যদি এটি একটি প্রাথমিকভাবে খালি স্ট্যাকের উপর পুশ এবং পপ অপারেশনগুলির একটি ক্রম এর ফলাফল হতে পারে। সুতরাং যদি ইনপুটটি পুশ =[1,2,3,4,5] এবং পপ =[4,5,3,2,1] হয় তবে আউটপুটটি সত্য হবে। আমরা push(1), push(2), push(3), push(4), pop() :4, push(5), pop() :5, pop() :3, pop() ব্যবহার করতে পারি :2, পপ() :1

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• সমাধান() নামে একটি পদ্ধতি তৈরি করুন। এটি পুশ করা এবং পপ করা অ্যারে নিয়ে যাবে

• একটি স্ট্যাক st সংজ্ঞায়িত করুন, সূচক সেট করুন :=0

• আমি 0 থেকে পুশ করা অ্যারের আকারের মধ্যে

  • push pushed[i] in st

  • যদি popped[index] =স্ট্যাক শীর্ষ উপাদান, তারপর

    • index :=index + 1

    • স্ট্যাক থেকে পপ

    • যখন st খালি নয়, এবং popped[index] =st এর শীর্ষ

      • index :=index + 1

    • st

      থেকে মুছুন

• যখন সূচক <পপডের আকার

  • যদি popped[index] =স্ট্যাক টপ, তারপর

    • সূচক 1 দ্বারা বৃদ্ধি করুন

    • স্ট্যাক থেকে মুছুন

  • অন্যথায় লুপ থেকে বেরিয়ে আসুন

• স্ট্যাক খালি হলে সত্য ফেরত দিন

• এই সমাধান পদ্ধতিটি নীচের মত প্রধান বিভাগ থেকে কল করা হবে −

• রিটার্ন সলভ (ধাক্কা দেওয়া, পপ করা)

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#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