คิว (Queues)
Queue เป็น FIFO
- Queue คือ First In, First Out (FIFO)
- รายการแรกที่คุณเพิ่มเข้าไป จะเป็นรายการแรกที่ออก
- คิดถึงคนในแถว: คนที่อยู่ด้านหน้าจะถูกบริการก่อน
enqueue และ dequeue ด้วย List
- เราสามารถสร้าง Queue จาก Python list ได้
- enqueue =
queue.append(x)— เพิ่มไปที่ ด้านหลัง - dequeue =
queue.pop(0)— ลบออกและคืนค่าที่ ด้านหน้า
queue = []
queue.append("first")
queue.append("second")
print(queue.pop(0))
print(queue)
front และ empty
- ดูที่ ด้านหน้า โดยไม่ลบออก:
queue[0] - Queue จะ empty เมื่อ
len(queue) == 0 - ตรวจสอบว่ามันไม่ว่างเปล่าก่อนที่คุณจะ dequeue
queue = [10, 20, 30]
print(queue[0]) # the front
print(len(queue) == 0) # is it empty?
ข้อสังเกตเกี่ยวกับความเร็ว
pop(0)ต้องเลื่อนรายการอื่นๆ ทั้งหมดไปข้างหน้าหนึ่งตำแหน่ง- สำหรับคิวใหญ่ที่ช้า ใช้ เวลา มากขึ้น
- ระบบจริงใช้ circular buffer พร้อมตัวชี้ด้านหน้าและด้านหลังแทน
In Cambridge pseudocode
- การสอบสร้าง Queue จาก Array พร้อมตัวชี้
frontและตัวชี้rear
DECLARE queue : ARRAY[1:10] OF INTEGER
DECLARE front, rear : INTEGER
front ← 1
rear ← 0 // empty
// enqueue value
rear ← rear + 1
queue[rear] ← value
// dequeue into value
value ← queue[front]
front ← front + 1
ข้อผิดพลาดที่พบบ่อย
- Queue เป็น First-in, first-out: เข้าที่ด้านหลัง, ออกที่ด้านหน้า
- ตรวจสอบว่ามันไม่ว่างเปล่าก่อนที่คุณจะ dequeue
ลองดูเลย
- ใช้ List เป็น Queue ของคุณ (
appendสำหรับ enqueue,pop(0)สำหรับ dequeue) - กด Check answer เพื่อทดสอบโค้ดของคุณ
A queue is FIFO
A queue adds at the back and removes at the front — first in, first out.
ความยาก 4/5 · 280 เหรียญ + บอนัสน้อยๆ เมื่อทำสำเร็จครั้งแรกในวันนี้
Start with an empty queue. Enqueue "a", then "b", then "c". Then dequeue once, storing the removed value in first. (first should be "a" and the queue should be ["b", "c"].)
คลิก Run เพื่อดูผลลัพธ์ที่นี่
ความยาก 4/5 · 280 เหรียญ + บอนัสน้อยๆ เมื่อทำสำเร็จครั้งแรกในวันนี้
Enqueue 1, 2, 3 onto a queue, then dequeue them all into result. Unlike a stack, a queue keeps the เหมือนเดิม order. (result should be [1, 2, 3].)
คลิก Run เพื่อดูผลลัพธ์ที่นี่
ความยาก 4/5 · 280 เหรียญ + บอนัสน้อยๆ เมื่อทำสำเร็จครั้งแรกในวันนี้
Write serve(queue) that dequeues the front item: remove it from the list and ผลตอบแทน it. The caller's list should get shorter.
คลิก Run เพื่อดูผลลัพธ์ที่นี่
ความยาก 4/5 · 280 เหรียญ + บอนัสน้อยๆ เมื่อทำสำเร็จครั้งแรกในวันนี้
Write front(queue) that ผลตอบแทน the front item without removing it, so the queue is unchanged. If the queue is empty, return None.
คลิก Run เพื่อดูผลลัพธ์ที่นี่