जांचें कि क्या एक कतार को पायथन में एक स्टैक का उपयोग करके दूसरी कतार में क्रमबद्ध किया जा सकता है

मान लीजिए कि हमारे पास पहले n प्राकृतिक संख्याओं (बिना क्रमबद्ध) के साथ एक कतार है। हमें यह जांचना होगा कि दिए गए कतार तत्वों को स्टैक का उपयोग करके किसी अन्य कतार में गैर-घटते क्रम में क्रमबद्ध किया जा सकता है या नहीं। इस समस्या को हल करने के लिए हम निम्नलिखित कार्यों का उपयोग कर सकते हैं -

• स्टैक से तत्वों को पुश या पॉप करें
• दी गई कतार से तत्व हटाएं।
• दूसरी कतार में तत्व डालें।

इसलिए, यदि इनपुट क्यू =[6, 1, 2, 3, 4, 5] जैसा है, तो आउटपुट ट्रू होगा क्योंकि हम क्यू से 6 पॉप कर सकते हैं, फिर इसे स्टैक में धकेल दें। अब सभी शेष तत्वों को क्यू से दूसरी कतार में पॉप करें, फिर स्टैक से 6 पॉप करें और दूसरी कतार में पुश करें, इसलिए नई कतार में सभी तत्वों को गैर-घटते क्रम में क्रमबद्ध किया जाएगा।

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

• n :=कतार का आकार
• stk :=एक नया स्टैक
• exp_val :=1
• सामने:=शून्य
• जबकि क्यू खाली नहीं है, करें
  • सामने:=कतार का अगला तत्व
  • क्यू से फ्रंट एलिमेंट हटाएं
  • यदि सामने exp_val के समान है, तो
    • exp_val :=exp_val + 1
  • अन्यथा,
    • यदि stk खाली है, तो
      • आगे को stk में धकेलें
    • अन्यथा जब stk खाली न हो और stk के ऊपर <सामने हो, तो
      • झूठी वापसी
    • अन्यथा,
      • आगे को stk में धकेलें
  • जबकि stk खाली नहीं है और स्टैक का शीर्ष exp_val के समान है, करें
    • stk से पॉप
    • exp_val :=exp_val + 1
• यदि exp_val - 1 n के समान है और stk खाली है, तो
  • सही लौटें
• झूठी वापसी

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

उदाहरण

from queue import Queue
def solve(que):
   n = que.qsize()
   stk = []
   exp_val = 1
   front = None
   while (not que.empty()):
      front = que.queue[0]
      que.get()
      if (front == exp_val):
         exp_val += 1
      else:
         if (len(stk) == 0):
            stk.append(front)
         elif (len(stk) != 0 and stk[-1] < front):
            return False
         else:
            stk.append(front)
   while (len(stk) != 0 and stk[-1] == exp_val):
      stk.pop()
      exp_val += 1
   if (exp_val - 1 == n and len(stk) == 0):
      return True
   return False
que = Queue()
items = [6, 1, 2, 3, 4, 5]
for i in items:
   que.put(i)
print(solve(que))

इनपुट

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

आउटपुट

True