दिए गए पुश-पॉप अनुक्रम वैध हैं या नहीं जांचने का पायथन प्रोग्राम

मान लीजिए हमारे पास pushes नामक संख्याओं की एक सूची है, और pops नामक संख्याओं की एक और सूची है, हमें जांचना है कि क्या यह स्टैक पुश और पॉप क्रियाओं का एक वैध अनुक्रम है या नहीं।

उदाहरण के लिए, यदि इनपुट pushes = [1, 2, 5, 7, 9] pops = [2, 1, 9, 7, 5] है, तो आउटपुट True होगा, क्योंकि हम पहले [1, 2] पुश कर सकते हैं फिर दोनों को पॉप कर सकते हैं। फिर [5, 7, 9] पुश करें और उन सभी को पॉप करें।

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

• s := एक नया स्टैक
• i := 0
• प्रत्येक ele के लिए pushes में, करें
  • ele को s में पुश करें
  • जब तक s का आकार > 0 और pops[i], s के शीर्ष तत्व के समान है, करें
    • s से शीर्ष तत्व हटाएं
    • i := i + 1
• सत्य लौटाएं जब s का आकार 0 के समान हो, अन्यथा असत्य

बेहतर समझ के लिए निम्न कार्यान्वयन देखें:

उदाहरण

class Solution:
    def solve(self, pushes, pops):
        s = []
        i = 0
        for ele in pushes:
            s.append(ele)
            while len(s) > 0 and pops[i] == s[-1]:
                s.pop()
                i += 1
        return len(s) == 0

ob = Solution()
pushes = [1, 2, 5, 7, 9]
pops = [2, 1, 9, 7, 5]
print(ob.solve(pushes, pops))

इनपुट

[1, 2, 5, 7, 9], [2, 1, 9, 7, 5]

आउटपुट

True