C++ में स्टैक अनुक्रमों की पुष्टि

मान लीजिए हमारे पास दो अनुक्रम pushed और popped हैं जिनमें विशिष्ट मान हैं। हमें जांचना है कि क्या ये एक प्रारंभिक खाली स्टैक पर पुश और पॉप ऑपरेशन्स के अनुक्रम का परिणाम हो सकते हैं।

उदाहरण: 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।

स्टैक सिमुलेशन एल्गोरिदम

1. एक स्टैक st और इंडेक्स idx = 0 बनाएँ।
2. pushed सरणी के प्रत्येक तत्व के लिए:
   • तत्व को st में पुश करें।
   • जब तक st खाली नहीं है और st.top() == popped[idx]:
     • st.pop(), idx++।
3. अंत में, यदि st खाली है तो true लौटाएँ, अन्यथा false।

C++ कार्यान्वयन

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> st;
        int idx = 0;
        for (int x : pushed) {
            st.push(x);
            while (!st.empty() && idx < popped.size() && st.top() == popped[idx]) {
                st.pop();
                idx++;
            }
        }
        return st.empty();
    }
};

int main() {
    vector<int> pushed = {1,2,3,4,5};
    vector<int> popped = {4,5,3,2,1};
    Solution ob;
    cout << ob.validateStackSequences(pushed, popped); // 1 (true)
    return 0;
}

इनपुट

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

आउटपुट

1