পাইথনে যাচাই করুন কিউ স্ট্যাক ব্যবহার করে অন্য কিউ-তে সর্ট করা যায় কিনা

ধরুন, একটি কিউ Que আছে যাতে প্রথম nটি প্রাকৃতিক সংখ্যা (unsorted) আছে। আমাদের যাচাই করতে হবে যে এই কিউ-র এলিমেন্টগুলো কি একটি স্ট্যাক ব্যবহার করে অন্য একটি কিউ-তে নন-ডিক্রিজিং অর্ডারে (সর্টেড) রেখা সম্ভব।

অনুমোদিত অপারেশন:

• স্ট্যাকে পুশ/পপ
• দেওয়া কিউ থেকে ডিলিট
• নতুন কিউ-তে ইন্সার্ট

যেমন, ইনপুট Que = [6, 1, 2, 3, 4, 5] হলে আউটপুট হবে True।

সমাধানের ধাপসমূহ

• n = que.qsize(), stk = [], exp_val = 1 (এক্সপেক্টেড ভ্যালু)।
• while que not empty:
  • front = que.get()।
  • যদি front == exp_val হয়, তবে exp_val++ (নতুন কিউ-তে চলে যাবে)।
  • অন্যথায়:
    • যদি স্ট্যাক খালি হয়, front পুশ করুন।
    • যদি স্ট্যাকের টপ front-এর চেয়ে ছোট হয়, তবে False (কারণ স্ট্যাক LIFO, বড় মান নিচে থাকলে ছোট মান বের করতে পারবে না)।
    • অন্যথায় front পুশ করুন।
• লুপের পরে, স্ট্যাক খালি না হয় না পর্যন্ত:
  • যদি স্ট্যাকের টপ exp_val হয়, পপ করুন এবং exp_val++।
• যদি exp_val - 1 == n এবং স্ট্যাক খালি হয়, তবে True, অন্যথায় 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 not stk:
                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 not stk:
        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