อัลกอริทึม Python

โครงสร้างข้อมูลคิว (queue) ใน Python

ในบทเรียนนี้ คุณจะสร้างคิวที่มีประสิทธิภาพตามหลักเข้าก่อนออกก่อนด้วย collections.deque

  • ระดับกลาง
  • อ่าน 2 นาที
  • ตัวอย่างที่รันได้ 1 ตัวอย่าง

บทนำ

ปัญหาที่ต้องแก้

งานพิมพ์ ตั๋วแจ้งปัญหาของฝ่ายบริการลูกค้า และข้อความที่ส่งระหว่างโปรแกรม ต้องจัดการตามลำดับที่เข้ามา คิว (queue) รักษาลำดับนั้นไว้ และถ้าเลือกเครื่องมือใน Python ให้ถูก คิวก็ยังเร็วแม้มีรายการเป็นล้าน

ลองนึกภาพแบบนี้

คิวเหมือนแถวหน้าเคาน์เตอร์ขายตั๋ว คนที่มาใหม่ต่อท้ายแถว และคนหน้าสุดได้รับบริการก่อน ไม่มีใครแซงคิว ทุกคนจึงได้รับบริการตามลำดับที่มาถึง

จากแถวขายตั๋วสู่โค้ด
deque(["first", "second"])🚶🚶 มีสองคนรออยู่แล้ว
queue.append("third")🚶 คนใหม่ต่อท้ายแถว
queue.popleft()🎫 คนหน้าสุดได้รับบริการ
list(queue)👀 ใครยังรออยู่
เข้าก่อน ออกก่อน: ลำดับการมาถึงคือลำดับการให้บริการ
สรุปในประโยคเดียว

คิวคือคอลเลกชันแบบเข้าก่อนออกก่อน (FIFO): เพิ่มรายการที่ด้านหลัง และเอาออกจากด้านหน้า

ประเด็นสำคัญ

  1. deque(["first", "second"]) สร้างคิวที่มีสองรายการอยู่แล้ว
  2. queue.append("third") เพิ่มรายการที่ด้านหลัง
  3. queue.popleft() เอาออกและส่งกลับรายการที่ด้านหน้า ในที่นี้คือ "first"
  4. deque เอารายการออกจากด้านหน้าได้เร็ว ส่วนลิสต์ต้องเลื่อนรายการที่เหลือทุกตัว

ใช้เมื่อไร?

  • ประมวลผลงานหรือคำขอตามลำดับที่มาถึง
  • breadth-first search ในกราฟและตาราง
  • บัฟเฟอร์ระหว่างฝั่งที่สร้างข้อมูลกับฝั่งที่นำไปใช้ เช่น ข้อความหรือเหตุการณ์

เมื่อไรยังไม่จำเป็น

  • รายการล่าสุดควรออกก่อน: ใช้สแต็ก
  • รายการมีลำดับความสำคัญ: ใช้ heapq สำหรับ priority queue
  • หลายเธรดใช้คิวร่วมกัน: queue.Queue จัดการเรื่องการล็อกให้

ดูการทำงาน

ลอง enqueue และ dequeue เพื่อดูว่าสมาชิกออกไปตามลำดับที่เข้ามา

โค้ดตัวอย่าง

รันโค้ด →
main.py
from collections import deque

queue = deque(["first", "second"])
queue.append("third")

print("served:", queue.popleft())
print("waiting:", list(queue))
สร้างปุ่ม Run สำหรับตัวอย่างนี้

ผลลัพธ์จากการรัน

served: first
waiting: ['second', 'third']

อธิบายโค้ด

deque เพิ่มสมาชิกทางขวาด้วย append() และหยิบออกทางซ้ายด้วย popleft() ได้ ทั้งสองอย่างใช้เวลา O(1) ถ้าใช้ลิสต์ธรรมดา การลบสมาชิกตัวแรกใช้เวลา O(n) เพราะสมาชิกที่เหลือทั้งหมดต้องเลื่อนตาม deque จึงเหมาะกับคิว

เปลี่ยนค่าและรันโปรแกรมด้วย คอมไพเลอร์ Python ออนไลน์ของ CodeUtility โดยไม่ต้องติดตั้ง Python

แบบฝึกหัดเพิ่มเติม

ลองแก้โค้ดตามคำแนะนำด้านล่าง การเปลี่ยนโค้ดแล้วดูผลลัพธ์จะช่วยให้เข้าใจบทเรียนได้ดีกว่าการอ่านอย่างเดียวมาก

  1. ทดสอบกับลิสต์ว่าง ลิสต์ที่มีสมาชิกตัวเดียว และลิสต์ที่มีค่าซ้ำ
  2. แสดงสถานะหลังแต่ละขั้นเพื่อดูการทำงานของอัลกอริทึม
  3. จับเวลาการทำงานกับข้อมูล 100, 1,000 และ 10,000 ตัว แล้วเทียบกับวิธีอื่น
รันในคอมไพเลอร์ Python →

ข้อผิดพลาดที่พบบ่อย

ใช้ลิสต์กับ pop(0)

pop(0) ต้องเลื่อนรายการที่เหลือทุกตัว คิวยิ่งยาวก็ยิ่งช้า

ปัญหา
queue = ["first", "second"]
queue.pop(0)
วิธีแก้
queue = deque(["first", "second"])
queue.popleft()

เรียนบทนี้จบแล้วใช่ไหม

ทำเครื่องหมายว่าเรียนแล้วเพื่อติดตามความคืบหน้า

ฝึกด้วยโจทย์

ใช้สิ่งที่เรียนในบทนี้แก้ปัญหาจริง ทุกโจทย์รันในเบราว์เซอร์ พร้อมการทดสอบทันทีและรีวิวจาก AI

โจทย์ทั้งหมด