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

ধরা যাক pushed এবং popped নামে দুটি সিকোয়েন্স আছে যাদের মান ভিন্ন। আমরা যাচাই করব যে কি এই সিকোয়েন্সগুলো একটি প্রাথমিক খালি স্ট্যাকে push এবং pop অপারেশন থেকে আসতে পারে কিনা। যদি 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() নামে একটি মেথড তৈরি করব। এটি pushed এবং popped অ্যারে নিবে
একটি স্ট্যাক st সংজ্ঞা করব, index := 0 সেট করব
i = 0 থেকে pushed অ্যারের সাইজ পর্যন্ত লুপ চলাব
- pushed[i] st-তে পুশ করব
- যদি popped[index] = স্ট্যাকের টপ এলিমেন্ট হয়, তবে
  - index := index + 1
  - স্ট্যাক থেকে পপ করব
  - যখন st খালি নয় এবং popped[index] = st-এর টপ
    - index := index + 1
  - st থেকে ডিলিট করব
যখন index < popped-এর সাইজ
- যদি popped[index] = স্ট্যাক টপ হয়, তবে
  - index ১ বাড়াব
  - স্ট্যাক থেকে ডিলিট করব
- অন্যথায় লুপ থেকে বের হব
যখন স্ট্যাক খালি হয়, true রিটার্ন করব
এই solve মেথডটি মেইন সেকশন থেকে নিচের মতো কল হবে −
রিটার্ন solve(pushed, popped)

নিচের ইমপ্লিমেন্টেশন দেখুন −

উদাহরণ

#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]