On this page
Queue — พื้นฐาน & แนวคิด
แถวที่ "ใครมาก่อนได้ก่อน" (FIFO) — นึกถึงต่อคิวร้านสะดวกซื้อ แล้วใช้ collections.deque เป็นอาวุธ (ห้าม list.pop(0)!)
ถ้า Stack คือกระป๋องมันฝรั่ง Pringles ที่ "เข้าทีหลัง ออกก่อน" ... Queue (คิว) ก็คือขั้วตรงข้ามอย่างสมบูรณ์แบบครับ!
ส่วนที่ 1 · ปลดล็อกไอเดีย
ภาพจำ: นึกถึง "การต่อแถวซื้อของที่ร้านสะดวกซื้อ" — คนที่เดินมาต่อแถวก่อน จะได้จ่ายเงินก่อนแล้วเดินออกจากร้านไป ส่วนคนที่เพิ่งเดินเข้ามาใหม่ ก็ต้องไปต่อท้ายแถวเท่านั้น จะมาแทรกคิวหรือแซงหน้าคนอื่นไม่ได้เด็ดขาด! นี่แหละครับคือคอนเซปต์ของ Queue
Stack เข้าและออกทางเดียว (ปากกระป๋อง) แต่ Queue จะมีสองปลาย คือ หัวแถว (Front) เอาไว้ออก และ หางแถว (Rear) เอาไว้เข้า
ออกร้าน <- [ 10 | 20 | 30 ] <- ต่อคิวเข้า
(หัวแถว) (หางแถว)
dequeue() จะได้ 10 (คนที่มาก่อนใครเพื่อน) · แถวจะหดเหลือ [20, 30]ส่วนที่ 2 · กฎเหล็ก — FIFO
Queue มีกฎศักดิ์สิทธิ์ข้อเดียวคือ FIFO = First In, First Out = "เข้าก่อน ออกก่อน" อาวุธประจำกายของมันมี 3 ท่าหลัก:
- Enqueue (ต่อคิว) — เอาของชิ้นใหม่ไปต่อไว้ที่ "ท้ายแถว"
- Dequeue (เรียกคิว) — เรียกของที่อยู่ "หน้าสุด" ออกจากแถว (ชิ้นนั้นจะหายไปจากคิวเลย)
- Peek (แอบดู) — ขอแอบดูหน่อยว่าใครอยู่หน้าสุดของแถว แต่ยังไม่เรียกตัวออกมา
ส่วนที่ 3 · ห้ามใช้ list เด็ดขาด!
หลายคนเห็นว่า Python list มีคำสั่ง .append() และดึงตัวหน้าสุดออกด้วย .pop(0) ได้ ก็เลยเอามาทำ Queue... นี่คือกับดักที่ทำให้โค้ดช้าจนสอบไม่ผ่านครับ!
เพราะเวลาเราดึงคนหน้าสุดออก (pop(0)) Python จะต้องสั่งให้คนที่เหลือ "ทุกคน" เดินขยับมาข้างหน้า 1 ก้าว ซึ่งกินเวลา O(N) ถ้าคิวยาวเป็นหมื่นคน โค้ดจะอืดสนิท
deque (อ่านว่า "เด็ค" ย่อจาก double-ended queue) เป็นโครงสร้างพิเศษที่ออกแบบมาให้เข้า-ออกได้ทั้งหัวและหางในระดับความเร็วแสง O(1)!
| แอคชันของ Queue | คำสั่ง Python (ใช้ deque) | Big-O |
|---|---|---|
| Enqueue (ต่อคิวเข้าหาง) | q.append(x) | O(1) |
| Dequeue (เรียกคิวออกหัว) | q.popleft() | O(1) |
| Peek (แอบดูหัวคิว) | q[0] | O(1) |
| Is Empty (ว่างไหม) | not q | O(1) |
ส่วนที่ 4 · จำลองการทำงาน
ลองต่อคิวทีละคน แล้วดูว่า Peek กับ Dequeue ต่างกันยังไง — ทิศคงที่: ซ้าย = หัว (ออก) · ขวา = หาง (เข้า)
| ขั้น | ทำอะไร | q ตอนนี้ (หัว … หาง) |
|---|---|---|
| เปิดร้าน | — | [] |
| append(10) | เข้าหาง | 10 |
| append(20) | เข้าหาง | 10 → 20 |
| append(30) | เข้าหาง | 10 → 20 → 30 |
| peek (q[0]) | แอบดูหัว — ไม่เอาออก | 10 → 20 → 30 (หัวยังเป็น 10) |
| popleft() | ออกหัว ได้ 10 | 20 → 30 |
| popleft() × 2 | เรียกคิวที่เหลือจนหมด | [] |
สัญลักษณ์ → อ่านจากหัวไปหาง · คนที่เข้าก่อนอยู่ซ้ายสุด และจะออกก่อนเสมอ
from collections import deque
q = deque() # 1. เปิดร้าน! แถวยังว่างเปล่า
q.append(10) # 2. Enqueue 10 -> 10
q.append(20) # 3. Enqueue 20 -> 10 → 20
q.append(30) # 4. Enqueue 30 -> 10 → 20 → 30
print(q[0]) # 5. Peek (แอบดูหัว) -> เห็น 10 (คิวยังเป็น 10 → 20 → 30)
first = q.popleft() # 6. Dequeue -> ได้ 10, คิวเหลือ 20 → 30
print(first) # พิมพ์ 10
# 7. เรียกคิวที่เหลือจนกว่าจะหมดแถว
while q:
print(q.popleft()) # จะได้ 20 ก่อน แล้วตามด้วย 3010
10
20
30ส่วนที่ 5 · สัญญาณว่าโจทย์ข้อนี้ต้องใช้ Queue
ถ้าเจอโจทย์แนว ๆ นี้ ให้นึกถึง deque เตรียมไว้เลยครับ:
- "ต้องประมวลผลตามลำดับก่อน-หลัง (In Order)" — อะไรเกิดก่อนต้องโดนจัดการก่อน
- "เก็บเหตุการณ์ล่าสุดในช่วงเวลาหนึ่ง (Sliding Window)" — เช่น ขอเช็คข้อมูลย้อนหลังแค่ 3,000 มิลลิวินาทีล่าสุด (เดี๋ยวเราจะได้เจอในโจทย์ข้อถัดไป!)
- "การสำรวจเป็นตึกทีละชั้น (BFS — Breadth-First Search)" — อันนี้คือท่าไม้ตาย! เอาไว้ใช้ไล่หาของใน Tree หรือ Graph แบบกระจายตัวออกไปรอบ ๆ ซึ่งเป็นหัวข้อใหญ่ในอนาคตแน่นอน
มาทีหลังไปต่อท้าย ถึงคิวเมื่อไหร่ค่อยออกไป = ใช้ Queue (และต้องเป็น deque ด้วยนะ)!
พื้นฐานครบแล้ว — หมวดนี้มี 2 ข้อ พร้อมแล้วกดถัดไปลุยโจทย์ข้อแรกเพื่อดูพลังของ deque กันเลยครับ