পাইথনে একটি স্ট্যাক ব্যবহার করে একটি সারি অন্য সারিতে সাজানো যায় কিনা তা পরীক্ষা করুন

ধরুন আমাদের প্রথম n প্রাকৃতিক সংখ্যা সহ একটি সারি আছে (বিন্যস্ত)। একটি স্ট্যাক ব্যবহার করে আমাদের প্রদত্ত সারির উপাদানগুলিকে অন্য সারিতে অ-হ্রাস না হওয়া ক্রম অনুসারে সাজানো যায় কিনা তা পরীক্ষা করতে হবে। এই সমস্যাটি সমাধান করার জন্য আমরা নিম্নলিখিত অপারেশনগুলি ব্যবহার করতে পারি -

• স্ট্যাক থেকে উপাদানগুলি পুশ বা পপ করুন
• প্রদত্ত সারি থেকে উপাদান মুছুন।
• অন্য সারিতে উপাদান ঢোকান।

সুতরাং, যদি ইনপুটটি Que =[6, 1, 2, 3, 4, 5] এর মত হয়, তাহলে আউটপুটটি True হবে কারণ আমরা Que থেকে 6 পপ করতে পারি, তারপর এটিকে স্ট্যাকের মধ্যে পুশ করি। এখন Que থেকে অন্য সারিতে বাকি সমস্ত উপাদান পপ করুন, তারপর স্ট্যাক থেকে 6 পপ করুন এবং দ্বিতীয় সারিতে পুশ করুন, তাই নতুন সারিতে থাকা সমস্ত উপাদান অ-হ্রাস না হওয়া ক্রমানুসারে সাজানো হবে।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• n :=que এর আকার
• stk :=একটি নতুন স্ট্যাক
• exp_val :=1
• সামনে :=শূন্য
• যখন que খালি না, do
  • সামনে :=que এর সামনের উপাদান
  • que থেকে সামনের উপাদান সরান
  • যদি সামনে exp_val এর মত হয়, তাহলে
    • exp_val :=exp_val + 1
  • অন্যথায়,
    • যদি stk খালি হয়, তাহলে
      • stk এ সামনে ঠেলে
    • অন্যথায় যখন stk খালি না থাকে এবং stk এর উপরের <সামনে, তারপর
      • মিথ্যে ফেরত দিন
    • অন্যথায়,
      • stk এ সামনে ঠেলে
  • যদিও stk খালি না থাকে এবং স্ট্যাকের উপরের অংশটি exp_val এর মতই থাকে, do
    • 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