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

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

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

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

ในการแก้ปัญหานี้ เราจะทำตามขั้นตอนดังนี้:

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

ลองดูการนำไปใช้ดังต่อไปนี้เพื่อเข้าใจได้ดียิ่งขึ้น:

ตัวอย่าง

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