ตรวจสอบว่าสามารถจัดเรียงคิวไปยังคิวอื่นโดยใช้สแต็กใน Python . ได้หรือไม่

สมมติว่าเรามีคิวที่มีตัวเลขธรรมชาติ n ตัวแรก (ไม่เรียงลำดับ) เราต้องตรวจสอบว่าองค์ประกอบคิวที่กำหนดสามารถเรียงลำดับในลำดับที่ไม่ลดลงในคิวอื่นโดยใช้กองซ้อนหรือไม่ เราสามารถใช้การดำเนินการต่อไปนี้เพื่อแก้ปัญหานี้ -

• ดันหรือป๊อปองค์ประกอบจากสแต็ก
• ลบองค์ประกอบออกจากคิวที่กำหนด
• แทรกองค์ประกอบในคิวอื่น

ดังนั้น หากอินพุตเป็นเหมือน Que =[6, 1, 2, 3, 4, 5] เอาต์พุตจะเป็น True เนื่องจากเราสามารถป๊อป 6 จาก Que จากนั้นจึงพุชลงในสแต็ก ตอนนี้ป๊อปองค์ประกอบที่เหลือทั้งหมดจาก Que ไปยังคิวอื่น จากนั้นป๊อป 6 จากสแต็กและพุชไปยังคิวที่สอง ดังนั้นองค์ประกอบทั้งหมดในคิวใหม่จะถูกจัดเรียงในลำดับที่ไม่ลดลง

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=ขนาดของ que
• stk :=สแต็คใหม่
• exp_val :=1
• ด้านหน้า :=null
• ในขณะที่ que ไม่ว่างเปล่า ให้ทำ
  • ด้านหน้า :=องค์ประกอบด้านหน้าของ que
  • ลบองค์ประกอบด้านหน้าออกจาก que
  • ถ้าด้านหน้าเหมือนกับ exp_val แล้ว
    • exp_val :=exp_val + 1
  • มิฉะนั้น
    • ถ้า stk ว่างเปล่า
      • ดันหน้าเข้า stk
    • มิฉะนั้นเมื่อ stk ไม่ว่างเปล่าและอยู่ด้านบนของ stk <ข้างหน้าแล้ว
      • คืนค่าเท็จ
    • มิฉะนั้น
      • ดันหน้าเข้า stk
  • ในขณะที่ stk ไม่ว่างเปล่าและด้านบนของ stack เหมือนกับ exp_val ให้ทำ
    • ป๊อปจาก stk
    • exp_val :=exp_val + 1
• ถ้า exp_val - 1 เหมือนกับ n และ stk ว่างเปล่า ดังนั้น
  • คืนค่า True
• คืนค่าเท็จ

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

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