โครงสร้างข้อมูลคิว (queue) ใน Python
ในบทเรียนนี้ คุณจะสร้างคิวที่มีประสิทธิภาพตามหลักเข้าก่อนออกก่อนด้วย collections.deque
บทนำ
ปัญหาที่ต้องแก้
งานพิมพ์ ตั๋วแจ้งปัญหาของฝ่ายบริการลูกค้า และข้อความที่ส่งระหว่างโปรแกรม ต้องจัดการตามลำดับที่เข้ามา คิว (queue) รักษาลำดับนั้นไว้ และถ้าเลือกเครื่องมือใน Python ให้ถูก คิวก็ยังเร็วแม้มีรายการเป็นล้าน
ลองนึกภาพแบบนี้
คิวเหมือนแถวหน้าเคาน์เตอร์ขายตั๋ว คนที่มาใหม่ต่อท้ายแถว และคนหน้าสุดได้รับบริการก่อน ไม่มีใครแซงคิว ทุกคนจึงได้รับบริการตามลำดับที่มาถึง
deque(["first", "second"])🚶🚶 มีสองคนรออยู่แล้วqueue.append("third")🚶 คนใหม่ต่อท้ายแถวqueue.popleft()🎫 คนหน้าสุดได้รับบริการlist(queue)👀 ใครยังรออยู่คิวคือคอลเลกชันแบบเข้าก่อนออกก่อน (FIFO): เพิ่มรายการที่ด้านหลัง และเอาออกจากด้านหน้า
ประเด็นสำคัญ
deque(["first", "second"])สร้างคิวที่มีสองรายการอยู่แล้วqueue.append("third")เพิ่มรายการที่ด้านหลังqueue.popleft()เอาออกและส่งกลับรายการที่ด้านหน้า ในที่นี้คือ"first"dequeเอารายการออกจากด้านหน้าได้เร็ว ส่วนลิสต์ต้องเลื่อนรายการที่เหลือทุกตัว
ใช้เมื่อไร?
- ประมวลผลงานหรือคำขอตามลำดับที่มาถึง
- breadth-first search ในกราฟและตาราง
- บัฟเฟอร์ระหว่างฝั่งที่สร้างข้อมูลกับฝั่งที่นำไปใช้ เช่น ข้อความหรือเหตุการณ์
เมื่อไรยังไม่จำเป็น
- รายการล่าสุดควรออกก่อน: ใช้สแต็ก
- รายการมีลำดับความสำคัญ: ใช้
heapqสำหรับ priority queue - หลายเธรดใช้คิวร่วมกัน:
queue.Queueจัดการเรื่องการล็อกให้
ดูการทำงาน
ลอง enqueue และ dequeue เพื่อดูว่าสมาชิกออกไปตามลำดับที่เข้ามา
โค้ดตัวอย่าง
from collections import deque
queue = deque(["first", "second"])
queue.append("third")
print("served:", queue.popleft())
print("waiting:", list(queue))
ผลลัพธ์จากการรัน
served: first
waiting: ['second', 'third']
อธิบายโค้ด
deque เพิ่มสมาชิกทางขวาด้วย append() และหยิบออกทางซ้ายด้วย popleft() ได้ ทั้งสองอย่างใช้เวลา O(1) ถ้าใช้ลิสต์ธรรมดา การลบสมาชิกตัวแรกใช้เวลา O(n) เพราะสมาชิกที่เหลือทั้งหมดต้องเลื่อนตาม deque จึงเหมาะกับคิว
เปลี่ยนค่าและรันโปรแกรมด้วย คอมไพเลอร์ Python ออนไลน์ของ CodeUtility โดยไม่ต้องติดตั้ง Python
แบบฝึกหัดเพิ่มเติม
ลองแก้โค้ดตามคำแนะนำด้านล่าง การเปลี่ยนโค้ดแล้วดูผลลัพธ์จะช่วยให้เข้าใจบทเรียนได้ดีกว่าการอ่านอย่างเดียวมาก
- ทดสอบกับลิสต์ว่าง ลิสต์ที่มีสมาชิกตัวเดียว และลิสต์ที่มีค่าซ้ำ
- แสดงสถานะหลังแต่ละขั้นเพื่อดูการทำงานของอัลกอริทึม
- จับเวลาการทำงานกับข้อมูล 100, 1,000 และ 10,000 ตัว แล้วเทียบกับวิธีอื่น
ข้อผิดพลาดที่พบบ่อย
ใช้ลิสต์กับ pop(0)
pop(0) ต้องเลื่อนรายการที่เหลือทุกตัว คิวยิ่งยาวก็ยิ่งช้า
queue = ["first", "second"]
queue.pop(0)
queue = deque(["first", "second"])
queue.popleft()
เรียนบทนี้จบแล้วใช่ไหม
ทำเครื่องหมายว่าเรียนแล้วเพื่อติดตามความคืบหน้า
ฝึกด้วยโจทย์
ใช้สิ่งที่เรียนในบทนี้แก้ปัญหาจริง ทุกโจทย์รันในเบราว์เซอร์ พร้อมการทดสอบทันทีและรีวิวจาก AI
- Course Schedule Order Order courses so every prerequisite comes first. ยาก
- Can We Split Into Two Teams? Decide whether people can be assigned to two teams so that each listed pair is on opposite teams. ปานกลาง