Queues · คิว (Queues)
A queue is FIFO
- A queue is First In, First Out (FIFO).
- The first item you add is the first one to leave.
- Think of a line of people: the person at the front is served first.
Queue เป็น FIFO
- Queue คือ First In, First Out (FIFO)
- รายการแรกที่คุณเพิ่มเข้าไป จะเป็นรายการแรกที่ออก
- คิดถึงคนในแถว: คนที่อยู่ด้านหน้าจะถูกบริการก่อน
enqueue and dequeue with a list
- We can build a queue from a Python list.
- enqueue =
queue.append(x)— add to the back. - dequeue =
queue.pop(0)— remove and return the front.
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 and empty
- Look at the front without removing it:
queue[0]. - A queue is empty when
len(queue) == 0. - Check it is not empty before you dequeue.
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?
A note on speed
pop(0)has to shift every other item forward by one place.- For a big queue that is slow, so it uses more time.
- Real systems use a circular buffer with front and rear pointers instead.
ข้อสังเกตเกี่ยวกับความเร็ว
pop(0)ต้องเลื่อนรายการอื่นๆ ทั้งหมดไปข้างหน้าหนึ่งตำแหน่ง- สำหรับ Queue ขนาดใหญ่这种做法ช้า ทำให้ใช้ เวลา มากขึ้น
- ระบบจริงใช้ circular buffer พร้อมตัวชี้ด้านหน้าและด้านหลังแทน
In Cambridge pseudocode
- The exam builds a queue from an array with a
frontand arearpointer.
ใน伪代码 Cambridge
- การสอบสร้าง 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
Common mistakes
- A queue is first-in, first-out: join the back, leave from the front.
- Check it is not empty before you dequeue.
ข้อผิดพลาดที่พบบ่อย
- Queue เป็น First-in, first-out: เข้าที่ด้านหลัง, ออกที่ด้านหน้า
- ตรวจสอบว่ามันไม่ว่างเปล่าก่อนที่คุณจะ dequeue
Now you try
- Use a list as your queue (
appendto enqueue,pop(0)to dequeue). - Press Check answer to test your code.
ลองดูเลย
- ใช้ List เป็น Queue ของคุณ (
appendสำหรับ enqueue,pop(0)สำหรับ dequeue) - กด Check answer เพื่อทดสอบโค้ดของคุณ
A queue is FIFO · คิวเป็นแบบ FIFO
A queue adds at the back and removes at the front — first in, first out. · คิวเพิ่มที่ด้านหลังและนำออกที่ด้านหน้า — เข้าทีแรก ออกทีแรก (first in, first out)
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"].) · เริ่มจากคิวว่าง Enqueue "a" แล้ว "b" แล้ว "c" จากนั้น dequeue หนึ่งครั้ง เก็บค่าที่ถูกลบออกไว้ใน first (first ควรจะเป็น "a" และคิวควรเป็น ["b", "c"])
Click Run to see the output here. · คลิก Run เพื่อดูผลลัพธ์ที่นี่
Enqueue 1, 2, 3 onto a queue, then dequeue them all into result. Unlike a stack, a queue keeps the same order. (result should be [1, 2, 3].) · Enqueue 1, 2, 3 ลงในคิว แล้ว Dequeue ทั้งหมดเข้าไปใน result. ต่างจากสแต็ก คิวจะรักษา ลำดับเดิม ไว้ (result ควรจะเป็น [1, 2, 3].)
Click Run to see the output here. · คลิก Run เพื่อดูผลลัพธ์ที่นี่
Write serve(queue) that dequeues the front item: remove it from the list and return it. The caller's list should get shorter. · เขียน serve(queue) ที่ Dequeue รายการหน้าสุด: ลบออกจาก list และ return ค่านั้น. List ของผู้เรียกจะสั้นลง
Click Run to see the output here. · คลิก Run เพื่อดูผลลัพธ์ที่นี่
Write front(queue) that returns the front item without removing it, so the queue is unchanged. If the queue is empty, return None. · เขียน front(queue) ที่ คืนค่า รายการหน้าสุด โดยไม่ ลบออก เพื่อให้คิวไม่เปลี่ยนแปลง. หากคิวว่าง ให้คืนค่า None
Click Run to see the output here. · คลิก Run เพื่อดูผลลัพธ์ที่นี่