একটি অ্যারে সি++ এ সাজানোর যোগ্য স্ট্যাক কিনা তা পরীক্ষা করুন

ধরুন আমাদের 1 থেকে n পর্যন্ত অনন্য উপাদানগুলির একটি অ্যারে সংখ্যা রয়েছে। আমাদের এটি স্ট্যাক-সর্টেবল কিনা তা পরীক্ষা করতে হবে। একটি অ্যারে স্ট্যাক বাছাইযোগ্য হয় যখন এটি একটি অস্থায়ী স্ট্যাক ব্যবহার করে অন্য কোনো অ্যারেতে সংরক্ষণ করা যায়।

এটি সমাধান করার জন্য, আমরা অ্যারে −

• অ্যারের শুরুর উপাদানটি মুছুন এবং সেই আইটেমটিকে স্ট্যাকের মধ্যে ঠেলে দিন৷

  ৷

• স্ট্যাকের উপরের উপাদানটি মুছুন এবং দ্বিতীয় অ্যারের শেষে সন্নিবেশ করুন।

এখন যদি এই ক্রিয়াকলাপগুলির মাধ্যমে প্রদত্ত অ্যারের সমস্ত উপাদান দ্বিতীয় অ্যারেতে স্থানান্তরিত হয় যাতে দ্বিতীয় অ্যারেটি অ-হ্রাস ক্রমে সাজানো হয়, তাহলে প্রদত্ত অ্যারেটি স্ট্যাক বাছাইযোগ্য৷

সুতরাং, যদি ইনপুটটি nums =[8, 6, 5, 3, 1] এর মতো হয়, তাহলে আউটপুটটি True হবে কারণ আমরা ঘড়ির কাঁটার দিকে দুইবার ঘোরাতে পারি তাহলে এটি [1, 3, 4, 1] এর মতো সাজানো হবে। 5, 6, 8]

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

• এক স্ট্যাক stk সংজ্ঞায়িত করুন
• শেষ :=0
• আরম্ভ করার জন্য i :=0, যখন i করুন
• যদি stk খালি না হয়, তাহলে −
  • top :=stk এর শীর্ষ উপাদান
  • যখন উপরেরটি (শেষ + 1) এর মতো, −
    করুন
    • শেষ :=শেষ + ১
    • stk থেকে পপ
    • যদি stk খালি হয়, তাহলে:
      • লুপ থেকে বেরিয়ে আসুন
    • top :=stk এর শীর্ষ উপাদান
  • যদি stk খালি হয়, তাহলে:
    • v[i] stk-এ ঠেলে
  • অন্যথায়
    • top :=stk এর শীর্ষ উপাদান
    • যদি v[i]
    • v[i] stk-এ ঠেলে
  • অন্যথায়
    • মিথ্যে ফেরত দিন

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

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
bool solve(vector<int> &v) {
   stack<int> stk;
   int last = 0;
   for (int i = 0; i < v.size(); i++) {
      if (!stk.empty()){
         int top = stk.top();
         while (top == last + 1) {
            last = last + 1;
            stk.pop();
            if (stk.empty()){
               break;
            } top = stk.top();
         }
         if (stk.empty()) {
            stk.push(v[i]);
         }else{
            top = stk.top();
            if (v[i] < top){
               stk.push(v[i]);
            }else{
               return false;
            }
         }
      }else{
         stk.push(v[i]);
      }
   } return true;
}
main(){
   vector<int>
   v = {8, 6, 5, 3, 1};
   cout << solve(v);
}

ইনপুট

{8, 6, 5, 3, 1}

আউটপুট

1