सी ++ में स्टैक अनुक्रमों को मान्य करें

मान लीजिए कि हमारे पास अलग-अलग मूल्यों के साथ दो अनुक्रमों को धक्का दिया गया है और पॉप किया गया है, तो हमें सही और केवल तभी खोजना होगा जब यह प्रारंभिक रूप से खाली स्टैक पर पुश और पॉप संचालन के अनुक्रम का परिणाम हो सकता है। तो अगर इनपुट पुश =[1,2,3,4,5], और पॉप =[4,5,3,2,1] है, तो आउटपुट सही होगा। हम पुश(1), पुश(2), पुश(3), पुश(4), पॉप() :4, पुश(5), पॉप() :5, पॉप() :3, पॉप() का उपयोग कर सकते हैं:2, पॉप() :1

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

हल () नामक एक विधि बनाएं। यह पुश और पॉप्ड ऐरे लेगा
स्टैक सेंट को परिभाषित करें, इंडेक्स सेट करें:=0
मेरे लिए 0 से लेकर पुश ऐरे के आकार तक
- पुश पुश[i] सेंट में
- अगर पॉप किया गया [इंडेक्स] =स्टैक टॉप एलिमेंट, तो
  - अनुक्रमणिका :=अनुक्रमणिका + 1
  - स्टैक से पॉप करें
  - जबकि सेंट खाली नहीं है, और पॉप [इंडेक्स] =सेंट के ऊपर
    - अनुक्रमणिका :=अनुक्रमणिका + 1
  - सेंट से हटाएं
जबकि इंडेक्स <पॉप का आकार
- अगर पॉप किया गया [इंडेक्स] =स्टैक टॉप, तो
  - इंडेक्स को 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]