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

मान लीजिए हमारे पास पहले n प्राकृतिक संख्याओं (असॉर्टेड) के साथ एक क्यू है। हमें यह जांचना है कि क्या दी गई क्यू के तत्वों को स्टैक का उपयोग करके दूसरी क्यू में गैर-घटते क्रम में सॉर्ट किया जा सकता है। हम निम्नलिखित ऑपरेशन्स का उपयोग कर सकते हैं:

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

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

समाधान दृष्टिकोण

हम अपेक्षित मान exp_val = 1 से शुरू करते हैं। क्यू के प्रत्येक तत्व के लिए, यदि यह अपेक्षित मान है, तो हम इसे सीधे आउटपुट क्यू में भेजते हैं और exp_val बढ़ाते हैं। अन्यथा, हम इसे स्टैक में पुश करते हैं (बशर्ते स्टैक के शीर्ष से छोटा हो)। अंत में स्टैक से शेष तत्वों को निकालते हैं।

एल्गोरिदम चरण:

1. n = que.qsize(), खाली स्टैक stk, exp_val = 1
2. जब क्यू खाली नहीं है:
• front = क्यू का पहला तत्व, क्यू से हटाएं
• यदि front == exp_val: exp_val += 1
• अन्यथा:
• यदि स्टैक खाली है: front को स्टैक में पुश करें
• अन्यथा यदि स्टैक का शीर्ष front से छोटा है: False लौटाएं (स्टैक में बढ़ता क्रम होना चाहिए)
• अन्यथा: front को स्टैक में पुश करें
• जब स्टैक खाली नहीं है और शीर्ष == exp_val: स्टैक से पॉप करें, exp_val += 1
3. यदि exp_val - 1 == n और स्टैक खाली है, तो True लौटाएं
4. अन्यथा False लौटाएं

पायथन कार्यान्वयन

from queue import Queue

def solve(que):
    n = que.qsize()
    stk = []
    exp_val = 1
    
    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 stk[-1] < front:
                return False
            else:
                stk.append(front)
        
        # स्टैक से निकालें यदि संभव हो
        while stk 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))  # True

इनपुट

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

आउटपुट

True

चरण-दर-चरण:

1. 6 → स्टैक में (exp_val=1)
2. 1 → आउटपुट (exp_val=2)
3. 2 → आउटपुट (exp_val=3)
4. 3 → आउटपुट (exp_val=4)
5. 4 → आउटपुट (exp_val=5)
6. 5 → आउटपुट (exp_val=6)
7. स्टैक से 6 → आउटपुट (exp_val=7)

आउटपुट: [1,2,3,4,5,6] ✓ सॉर्टेड!