ตรวจสอบว่าการย้ายในสแต็กหรือคิวเป็นไปได้หรือไม่ใน Python

สมมติว่าเรามีรายการไบนารี 1 รายการ โดยที่ 1 หมายถึงการดำเนินการพุช และ 0 หมายถึงการดำเนินการป๊อปในสแต็กหรือคิว เราต้องตรวจสอบว่าชุดปฏิบัติการที่เป็นไปได้นั้นถูกต้องหรือไม่

ดังนั้นหากอินพุตเป็น nums =[1,0,1,1,0,1] เอาต์พุตจะเป็น True ตามลำดับ [Push,Pop,Push,Push,Pop,Push] อย่างที่เราไม่ใช่ popping องค์ประกอบจากรายการว่างเพื่อให้การดำเนินการเหล่านี้ถูกต้อง

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

• push_count :=0
• สำหรับฉันในช่วง 0 ถึงขนาดของ nums - 1 ทำ
  • ถ้า nums[i] คือ 1 แล้ว
    • push_count :=push_count + 1
  • มิฉะนั้น
    • push_count :=push_count - 1
  • ถ้า push_count <0 แล้ว
    • คืนค่าเท็จ
• คืนค่า True

ตัวอย่าง

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

def solve(nums):
   push_count = 0
   for i in range (len(nums)):
      if nums[i]:
         push_count += 1
      else:
         push_count -= 1
      if push_count < 0:
         return False
   return True
nums = [1,0,1,1,0,1]
print(solve(nums))

อินพุต

[1,0,1,1,0,1]

ผลลัพธ์

True