ลิงก์ลิสต์ สแตก และคิว
โครงสร้างข้อมูลเชิงเส้น (linear) คือข้อมูลที่เรียงต่อกันเป็นลำดับเดียว แต่สิ่งที่ทำให้สแตกและคิวทรงพลังไม่ใช่ “สิ่งที่ทำได้” หากเป็น “สิ่งที่จงใจห้ามทำ” — เราจำกัดวิธีเข้าถึงข้อมูลโดยตั้งใจ เพื่อแลกความยืดหยุ่นกับการรับประกันต้นทุน O(1) และความถูกต้องของลำดับงาน
วินัยของการจำกัด (discipline of restriction) คือหัวใจ: ยิ่งโครงสร้างทำอะไรได้น้อย เรายิ่งให้เหตุผลกับมันได้ง่าย
ลิงก์ลิสต์ (Linked List)
หัวข้อที่มีชื่อว่า “ลิงก์ลิสต์ (Linked List)”อาเรย์เก็บข้อมูลในหน่วยความจำที่ต่อเนื่องกัน ทำให้เข้าถึงด้วยดัชนีได้ O(1) แต่มีข้อจำกัด: การแทรกหรือลบกลางอาเรย์ต้องเลื่อนสมาชิกที่เหลือทั้งหมด เป็น O(n) และขนาดมักถูกกำหนดล่วงหน้า
ลิงก์ลิสต์แก้ปัญหานี้ด้วยแนวคิด โหนด (node) ที่กระจายอยู่ในหน่วยความจำ แต่ละโหนดเก็บ “ข้อมูล” และ “พอยน์เตอร์ (pointer)” ที่ชี้ไปยังโหนดถัดไป ไม่มีบล็อกต่อเนื่องให้เลื่อน — มีแต่ลูกศรให้ปรับ
ลิงก์ลิสต์แบบทางเดียว (Singly Linked List)
หัวข้อที่มีชื่อว่า “ลิงก์ลิสต์แบบทางเดียว (Singly Linked List)”head │ ▼┌────┬───┐ ┌────┬───┐ ┌────┬───┐│ 10 │ ●─┼──▶│ 20 │ ●─┼──▶│ 30 │ ✕ │└────┴───┘ └────┴───┘ └────┴───┘ data next data next data next(null)เมื่อเรามีพอยน์เตอร์อยู่ที่โหนดใดโหนดหนึ่งแล้ว การแทรกหรือลบ ณ ตำแหน่งนั้นเป็นเพียงการ “ปรับลูกศร” ไม่กี่เส้น จึงเป็น O(1) ไม่ต้องเลื่อนสมาชิกใด ๆ
แต่มีราคาที่ต้องจ่าย: ลิงก์ลิสต์ไม่มีดัชนี การจะไปถึงโหนดที่
iต้องเดินจากheadทีละก้าว จึงเป็นO(n)และการค้นหาค่าก็O(n)เช่นกัน
ตัวอย่างคลี่ทีละขั้นที่ 1 — prepend เทียบกับ append สมมติเราสร้างลิสต์ [4, 8, 15] โดยแทรกที่หัวทีละค่า เริ่มจากลิสต์ว่าง
| ขั้น | ปฏิบัติการ | ลิสต์หลังทำ | พอยน์เตอร์ที่แตะ | ต้นทุน |
|---|---|---|---|---|
| 1 | prepend 15 | 15 → null |
head = โหนดใหม่ |
O(1) |
| 2 | prepend 8 | 8 → 15 → null |
new.next = head, head = new |
O(1) |
| 3 | prepend 4 | 4 → 8 → 15 → null |
new.next = head, head = new |
O(1) |
ทุก prepend เป็น O(1) เพราะแตะแค่ head กับพอยน์เตอร์ next เส้นเดียว ลองเทียบกับการ append ค่าเดิมสามค่าตามลำดับ โดยมีแค่พอยน์เตอร์ head ไม่มี tail:
| ขั้น | ปฏิบัติการ | งานที่ต้องทำ | ต้นทุน |
|---|---|---|---|
| 1 | append 4 | เดิน 0 โหนดจาก head (ลิสต์ว่าง) |
O(1) |
| 2 | append 8 | เดิน 1 โหนดเพื่อหาโหนดสุดท้าย | O(n) |
| 3 | append 15 | เดิน 2 โหนดเพื่อหาโหนดสุดท้าย | O(n) |
การ append โดยไม่มีพอยน์เตอร์ tail จะกลายเป็น O(n) ต่อครั้ง เพราะต้องเดินทั้งลิสต์เพื่อหาโหนดสุดท้ายก่อนปรับลูกศร ถ้าเก็บพอยน์เตอร์ tail ไว้ (อัปเดตทุกครั้งที่ append) จะกลับมาเป็น O(1) — นี่คือกลเม็ดเดียวกับที่ collections.deque และการเขียนลิงก์ลิสต์ระดับโปรดักชันส่วนใหญ่ใช้
ลิงก์ลิสต์แบบสองทาง (Doubly Linked List)
หัวข้อที่มีชื่อว่า “ลิงก์ลิสต์แบบสองทาง (Doubly Linked List)”ลิงก์ลิสต์แบบสองทาง เพิ่มพอยน์เตอร์ที่สองต่อโหนด คือ prev ชี้ย้อนกลับ ราคาที่จ่ายคือหน่วยความจำต่อโหนดมากขึ้น แต่แลกมาด้วยความสามารถเดินย้อนกลับได้ O(1) ต่อก้าว และลบโหนดได้ O(1) เมื่อมีแค่พอยน์เตอร์ไปยังโหนดนั้น โดยไม่ต้องตามหาหรือเก็บโหนดก่อนหน้าแยกต่างหาก
head tail │ │ ▼ ▼┌────┬────┬────┐ ┌────┬────┬────┐ ┌────┬────┬────┐│null│ 10 │ ●──┼───────▶│ ●──┼ 20 │ ●──┼───────▶│ ●──┼ 30 │null│└────┴────┴────┘◀───────┴────┴────┴────┘◀───────┴────┴────┴────┘ prev data next prev data next prev data nextตัวอย่างคลี่ทีละขั้นที่ 2 — ลบโหนดกลาง เพื่อลบโหนดที่เก็บ 20 ออกจากลิสต์ข้างบน ต้องปรับลูกศรพอดี 2 เส้น: โหนด ก่อนหน้า ต้องชี้ไปข้างหน้าข้ามมันไป และโหนด ถัดไป ต้องชี้ย้อนกลับข้ามมันไป
| ขั้น | การกระทำ | ผลลัพธ์ |
|---|---|---|
| 1 | node20.prev.next = node20.next |
โหนด 10 ชี้ไปข้างหน้าหาโหนด 30 ข้าม 20 |
| 2 | node20.next.prev = node20.prev |
โหนด 30 ชี้ย้อนกลับหาโหนด 10 ข้าม 20 |
| 3 | (โหนด 20 เข้าถึงไม่ได้อีกต่อไป) |
ถูกเก็บกวาดโดย garbage collector ลิสต์เหลือ 10 ⇄ 30 |
ต้องทำทั้งสองขั้น ถ้าข้ามขั้นที่ 2 ลิสต์จะ “อ่านถูก” เมื่อเดินไปข้างหน้า แต่การเดิน ย้อนกลับ จากโหนด 30 จะวกกลับไปเจอโหนด 20 ที่ถูกลบไปแล้วอย่างผิดพลาด — บั๊กแอบแฝงที่โผล่มาก็ต่อเมื่อมีใครเดินย้อนทิศ (ดูข้อ 2 ในแบบฝึกหัด)
| คุณสมบัติ | อาเรย์ | ลิงก์ลิสต์ทางเดียว | ลิงก์ลิสต์สองทาง |
|---|---|---|---|
| เข้าถึงด้วยดัชนี | O(1) |
O(n) |
O(n) |
| ค้นหาค่า | O(n) |
O(n) |
O(n) |
| แทรก/ลบ ณ โหนดที่รู้ตำแหน่ง | O(n) |
O(1) ไปข้างหน้าเท่านั้น |
O(1) ทั้งสองทิศ |
| แทรก/ลบ ที่หัว | O(n) |
O(1) |
O(1) |
| แทรก/ลบ ที่ท้าย | O(n) |
O(1) ถ้ามี tail ไม่งั้น O(n) |
O(1) ถ้ามี tail |
| เดินย้อนกลับ | O(1) ต่อก้าว |
ทำไม่ได้ | O(1) ต่อก้าว |
| หน่วยความจำต่อสมาชิก | น้อย (เฉพาะข้อมูล) | ปานกลาง (ข้อมูล + พอยน์เตอร์ 1 ตัว) | มาก (ข้อมูล + พอยน์เตอร์ 2 ตัว) |
สแตก (Stack) — เข้าหลังออกก่อน (LIFO)
หัวข้อที่มีชื่อว่า “สแตก (Stack) — เข้าหลังออกก่อน (LIFO)”สแตกคือโครงสร้างแบบ LIFO (Last In, First Out) — สิ่งที่ใส่เข้าไปล่าสุดจะถูกหยิบออกก่อน เหมือนกองจานที่วางซ้อนกัน เราหยิบจานบนสุดได้เท่านั้น มีเพียงสองปฏิบัติการหลัก:
- push — วางข้อมูลไว้บนสุด
O(1) - pop — หยิบข้อมูลบนสุดออก
O(1)
การใช้งานในโลกจริง: ปุ่ม undo ในโปรแกรม, backtracking (ลองเดินทางหนึ่ง แล้วย้อนกลับไปจุดตัดสินใจล่าสุดเมื่อทางนั้นตัน — เขาวงกต ตัวไขปริศนา การค้นหาแบบเรียกซ้ำ), call stack ที่ภาษาโปรแกรมใช้จำว่าฟังก์ชันไหนเรียกฟังก์ชันไหน, และการตรวจ วงเล็บสมดุล ในคอมไพเลอร์และเอดิเตอร์
stack = [] # ใช้ list ของ Python เป็นสแตกได้เลย
stack.append("A") # pushstack.append("B") # push -> ['A', 'B']top = stack.pop() # pop -> คืน 'B', เหลือ ['A']ตัวอย่างคลี่ทีละขั้นที่ 3 — ตรวจวงเล็บสมดุลด้วยสแตก ไล่ is_balanced("{[()]}"): push วงเล็บเปิดทุกตัว และเมื่อเจอวงเล็บปิด ต้องจับคู่กับตัวที่อยู่บนสุด
| ขั้น | ตัวอักษร | การกระทำ | สแตก (บนสุด → ขวา) |
|---|---|---|---|
| 1 | { |
push | { |
| 2 | [ |
push | { [ |
| 3 | ( |
push | { [ ( |
| 4 | ) |
pop, คาดหวัง ( — ตรงกัน |
{ [ |
| 5 | ] |
pop, คาดหวัง [ — ตรงกัน |
{ |
| 6 | } |
pop, คาดหวัง { — ตรงกัน |
(ว่าง) |
สแตกว่างตอนจบ → สมดุล ถ้าวงเล็บปิดตัวใดเจอสิ่งที่ผิดบนสุด หรือสแตกว่างตอนที่ต้อง pop ทันที ให้สรุปว่าไม่สมดุลได้เลย
ตัวอย่างคลี่ทีละขั้นที่ 4 — เห็น call stack ด้วยตาตัวเอง ทุกครั้งที่โปรแกรมเรียกฟังก์ชัน รันไทม์ของภาษาจะ push มันลงสแตกโดยอัตโนมัติ และ pop ออกเมื่อฟังก์ชันนั้น return ไล่ factorial(4):
| ขั้น | การกระทำ | call stack (บนสุด → ล่างสุด) |
|---|---|---|
| 1 | เรียก factorial(4) |
factorial(4) |
| 2 | มันเรียก factorial(3) |
factorial(3), factorial(4) |
| 3 | มันเรียก factorial(2) |
factorial(2), factorial(3), factorial(4) |
| 4 | มันเรียก factorial(1) → เงื่อนไขฐาน คืนค่า 1 |
factorial(2), factorial(3), factorial(4) |
| 5 | factorial(2) คืนค่า 2 * 1 = 2 |
factorial(3), factorial(4) |
| 6 | factorial(3) คืนค่า 3 * 2 = 6 |
factorial(4) |
| 7 | factorial(4) คืนค่า 4 * 6 = 24 |
(ว่าง) |
นี่คือเหตุผลที่การเรียกซ้ำแบบลึกไม่จำกัดจะพังด้วย RecursionError / “stack overflow” — call stack คือสแตกจริง ๆ ที่มีพื้นที่จำกัด และเป็นเหตุผลที่อัลกอริทึม backtracking (แก้เขาวงกต, N-Queens, ไข Sudoku) มักเขียนด้วยการเรียกซ้ำโดยธรรมชาติ: call stack ของภาษา คือ สแตกของการตัดสินใจที่ต้องคลายเมื่อทางนั้นตัน
คิว (Queue) — เข้าก่อนออกก่อน (FIFO)
หัวข้อที่มีชื่อว่า “คิว (Queue) — เข้าก่อนออกก่อน (FIFO)”คิวคือโครงสร้างแบบ FIFO (First In, First Out) — ใครมาก่อนได้ก่อน เหมือนคนต่อแถวซื้อของ ปฏิบัติการหลักคือ:
- enqueue — เพิ่มข้อมูลที่ “ท้ายแถว”
O(1) - dequeue — นำข้อมูลที่ “หัวแถว” ออก
O(1)
การใช้งานในโลกจริง: การจัดคิวงาน (task scheduling — คิวงานพิมพ์, job queue, ready queue ของระบบปฏิบัติการ), การค้นหาตามความกว้าง (BFS) ในกราฟและต้นไม้, และการจัดการคำขอแบบจำกัดอัตรา (rate limiting)
ตัวอย่างคลี่ทีละขั้นที่ 5 — BFS ด้วยคิว กำหนดกราฟ A–B, A–C, B–D, C–D, D–E ไล่การค้นหาตามความกว้างเริ่มจาก A คิวรับประกันว่าเราจะเยี่ยมทุกโหนดที่ระยะ 1 ก่อนโหนดใด ๆ ที่ระยะ 2
| ขั้น | dequeue | เยี่ยม | โหนดที่เพิ่งเพิ่มเข้าคิว (เพื่อนบ้านที่ยังไม่เยี่ยม) | คิวหลังทำ |
|---|---|---|---|---|
| 0 | — | — | — | [A] |
| 1 | A |
A |
B, C |
[B, C] |
| 2 | B |
B |
D |
[C, D] |
| 3 | C |
C |
(D อยู่ในคิวแล้ว) | [D] |
| 4 | D |
D |
E |
[E] |
| 5 | E |
E |
— | [] |
ลำดับการเยี่ยม A, B, C, D, E — ทีละชั้น ระยะ 0 ก่อน แล้วจึง 1 แล้วจึง 2 ถ้าสลับคิวเป็นสแตกจะได้ลำดับแบบ depth-first แทน (A, C, D, E, B หรือใกล้เคียง) — กราฟเดิม โครงสร้างต่าง ผลลัพธ์การท่องต่างกันโดยสิ้นเชิง
ทำไม list.pop(0) เป็น O(n) แต่ deque.popleft() เป็น O(1)
หัวข้อที่มีชื่อว่า “ทำไม list.pop(0) เป็น O(n) แต่ deque.popleft() เป็น O(1)”list ของ Python คือ อาเรย์ แบบไดนามิกภายใต้ผิว — หน่วยความจำต่อเนื่องกัน การ enqueue ด้วย append() เป็น O(1) (แบบตัดจ่าย) แต่การ dequeue จากหัวด้วย pop(0) บังคับให้สมาชิกที่เหลือทุกตัวเลื่อนซ้ายทีละช่องเพื่อปิดช่องว่าง — O(n) ต่อครั้ง และ O(n²) เพื่อ dequeue ให้หมด n ชิ้น
collections.deque ถูกสร้างเป็นลิงก์ลิสต์แบบสองทางของบล็อกขนาดคงที่เล็ก ๆ ทั้งสองปลายเป็น “พลเมืองชั้นหนึ่ง” เท่ากัน — การเพิ่มหรือลบที่ปลายใดก็เพียงปรับพอยน์เตอร์ไม่กี่เส้น เหมือนลิงก์ลิสต์สองทางในหัวข้อก่อนหน้าเป๊ะ ไม่มีการเลื่อนเลย
from collections import deque
q = deque()q.append("A") # enqueue ที่ท้าย O(1)q.append("B")first = q.popleft() # dequeue ที่หัว O(1) -> คืน 'A'Deque — คิวสองปลาย (Double-Ended Queue)
หัวข้อที่มีชื่อว่า “Deque — คิวสองปลาย (Double-Ended Queue)”deque (อ่านว่า “เด็ก”) ครอบคลุมทั้งสแตกและคิวไว้ในตัวเดียว: รองรับ push และ pop ที่ปลาย ทั้งสอง ด้าน ด้วย O(1)
from collections import deque
d = deque([2, 3, 4])d.appendleft(1) # [1, 2, 3, 4] O(1) ที่หัวd.append(5) # [1, 2, 3, 4, 5] O(1) ที่ท้ายd.pop() # -> 5, เหลือ [1, 2, 3, 4] O(1) ที่ท้ายd.popleft() # -> 1, เหลือ [2, 3, 4] O(1) ที่หัวใช้ deque แทน list ธรรมดาทุกครั้งที่ต้องเพิ่ม/ลบจากปลาย ทั้งสองด้าน อย่างมีประสิทธิภาพ: หน้าต่างเลื่อน (sliding window) เหนือสตรีมข้อมูล, ประวัติเบราว์เซอร์แบบโครงสร้างเดียว, ตัวจัดสรรงานแบบ work-stealing (คนงานขโมยงานจากปลายหนึ่งขณะเจ้าของ push/pop อีกปลาย) หรือง่าย ๆ คือ “คิวที่ต้องมี undo ด้วย”
สรุปความซับซ้อน (Complexity)
หัวข้อที่มีชื่อว่า “สรุปความซับซ้อน (Complexity)”| ปฏิบัติการ | อาเรย์ | ลิงก์ลิสต์ | สแตก | คิว | Deque |
|---|---|---|---|---|---|
| เข้าถึงด้วยดัชนี | O(1) |
O(n) |
O(1) เฉพาะบนสุด |
O(1) เฉพาะหัว |
O(1) ทั้งสองปลาย |
| แทรกที่หัว | O(n) |
O(1) |
— | — | O(1) |
| แทรกที่ท้าย | O(n)* |
O(1) ถ้ามี tail |
O(1) (push) |
O(1) (enqueue) |
O(1) |
| ลบที่หัว | O(n) |
O(1) |
— | O(1) (dequeue) |
O(1) |
| ลบที่ท้าย | O(1)* |
O(1) สองทาง / O(n) ทางเดียว |
O(1) (pop) |
— | O(1) |
| ค้นหา | O(n) |
O(n) |
O(n) |
O(n) |
O(n) |
*อาเรย์ไดนามิกของ Python ตัดจ่าย append/pop ที่ ท้าย ให้เป็น O(1) เฉพาะปฏิบัติการที่ หัว เท่านั้นที่เป็น O(n)
สแตก คิว และ deque มักถูก “สร้างทับ” บนอาเรย์หรือลิงก์ลิสต์อีกที พวกมันคือ กติกาการเข้าถึง ไม่ใช่วิธีจัดเก็บใหม่ — บทเรียนทั้งหน้านี้คือกติกาที่คุณเลือกต่างหากที่กำหนด Big-O ไม่ใช่ตัวข้อมูลดิบ
โจทย์จากโลกจริง — ปุ่มย้อนกลับ/ไปข้างหน้าของเบราว์เซอร์
หัวข้อที่มีชื่อว่า “โจทย์จากโลกจริง — ปุ่มย้อนกลับ/ไปข้างหน้าของเบราว์เซอร์”ปุ่ม Back และ Forward ของเบราว์เซอร์จำลองได้ด้วย สแตกสองตัว:
- เมื่อเข้าหน้าใหม่ →
pushหน้าปัจจุบันลงสแตกbackแล้วล้างสแตกforward - กด Back →
popจากสแตกbackมาเป็นหน้าปัจจุบัน และpushหน้าเดิมลงสแตกforward - กด Forward →
popจากสแตกforwardมาเป็นหน้าปัจจุบัน และpushหน้าเดิมกลับลงสแตกback
ทำไมต้องเป็นสแตก? เพราะพฤติกรรม “ย้อนกลับ” คือ LIFO โดยธรรมชาติ — เราต้องกลับไปยังหน้าที่ “เพิ่งออกมา” ก่อนเสมอ และทุกปฏิบัติการเป็น O(1) ถ้าใช้คิวซึ่งเป็น FIFO ลำดับจะกลับด้าน ทำให้ผิดความหมายไปเลย: กด Back จะพาไปหน้า เก่าที่สุด ที่เคยเข้า ไม่ใช่หน้าล่าสุด
เมื่อขยายสเกล (เซสชันที่มีการนำทางนับพันครั้ง) ทางเลือกไร้เดียงสา — เก็บประวัติเป็น list ธรรมดาแล้ว slice ใหม่ทุกครั้งที่นำทาง — จะเป็น O(n) ต่อคลิก เพราะ slice คือการคัดลอก การออกแบบด้วยสแตกสองตัวทำให้ทุกคลิกเป็น O(1) ไม่ว่าประวัติจะยาวแค่ไหน
ทางเลือกอื่น: เบราว์เซอร์จริงหลายตัวจำลองประวัติด้วย ลิงก์ลิสต์สองทางเส้นเดียว พร้อมพอยน์เตอร์
currentแทนสแตกสองตัว การกด Back/Forward คือการขยับcurrentไปตามprev/next; การเข้าหน้าใหม่คือการตัดสายnextจากcurrentเป็นต้นไป รับประกันO(1)เท่ากัน แต่มุมมองต่างกัน — พิสูจน์ว่าสแตก คิว และลิงก์ลิสต์มักเป็น “เปลือก” ที่สลับกันได้บนไอเดียเดียวกัน
แบบฝึกหัด
หัวข้อที่มีชื่อว่า “แบบฝึกหัด”ข้อ 1 — Big-O: append โดยมีและไม่มีพอยน์เตอร์ tail
ลิงก์ลิสต์แบบทางเดียวเก็บแค่พอยน์เตอร์ head (ไม่มี tail) การ append สมาชิกใหม่หนึ่งตัวที่ท้ายมีความซับซ้อนเท่าไร? ถ้าลิสต์เก็บพอยน์เตอร์ tail ที่อัปเดตทันเวลาด้วย จะเปลี่ยนอย่างไร?
เฉลย
ถ้าไม่มีพอยน์เตอร์ tail การ append เป็น O(n): ต้องเดินจาก head ไปจนถึงโหนดสุดท้ายก่อนจึงต่อโหนดใหม่ได้ ถ้ามีพอยน์เตอร์ tail ที่อัปเดตทุกครั้งที่แทรก การ append จะกลายเป็น O(1): ปรับ tail.next = new_node แล้ว tail = new_node นี่คือกลเม็ดเดียวกับที่ทำให้ collections.deque เร็วทั้งสองปลาย
ข้อ 2 — จับบั๊กในการลบโหนดของลิงก์ลิสต์สองทาง
def remove(node: "Node") -> None: node.prev.next = node.next # (ไม่มีอย่างอื่น)โค้ดนี้ “ดูเหมือนทำงานได้” เวลาทดสอบผิวเผิน — การเดินไปข้างหน้าดูปกติดี อะไรจะพัง และบั๊กจะโผล่ตอนไหน?
เฉลย
โค้ดลืม node.next.prev = node.prev การเดินไปข้างหน้า (node.next, node.next.next, …) ไม่แตะ prev เลย จึงดูถูกต้อง แต่การเดิน ย้อนกลับ จากโหนดใดก็ตามหลังโหนดที่ถูกลบ จะยังเจอ prev ชี้ไปที่โหนดที่ถูกลบอยู่ — เดินย้อนกลับเข้าไปในหน่วยความจำที่ “ถูกลบ” ไปแล้วได้ นอกจากนี้ยังพังเงียบ ๆ ถ้า node เป็นโหนดท้าย (node.next เป็น None) หรือหัว (node.prev เป็น None) — กรณีเหล่านี้ต้องอัปเดต head/tail แทนการอ้างอิง None เวอร์ชันแก้ไข:
def remove(node: "Node") -> None: if node.prev: node.prev.next = node.next else: head = node.next # node เป็น head if node.next: node.next.prev = node.prev else: tail = node.prev # node เป็น tailข้อ 3 — ทายผลลัพธ์ (สแตก)
s = []s.append(1)s.append(2)s.append(3)s.pop()s.append(4)s.pop()s.append(5)print(s)เฉลย
ไล่ทีละขั้น: [1] → [1,2] → [1,2,3] → pop เอา 3 ออก → [1,2] → append 4 → [1,2,4] → pop เอา 4 ออก → [1,2] → append 5 → [1,2,5] คำตอบสุดท้าย: [1, 2, 5]
ข้อ 4 — ทายผลลัพธ์ (คิวเทียบกับสแตก อินพุตชุดเดียวกัน)
ปฏิบัติการชุดเดียวกัน — ใส่ A, ใส่ B, เอาออกหนึ่งตัว, ใส่ C — รันบนสแตกครั้งหนึ่งและบนคิวครั้งหนึ่ง แต่ละอันจะมีอะไรเหลืออยู่ตอนจบ?
เฉลย
สแตก: push A, push B → [A, B]; pop เอา B ออก (เข้าล่าสุด) → [A]; push C → [A, C]
คิว: enqueue A, enqueue B → [A, B]; dequeue เอา A ออก (เข้าก่อน) → [B]; enqueue C → [B, C]
ปฏิบัติการเดียวกัน อินพุตเดียวกัน แต่ผลลัพธ์สุดท้ายต่างกัน — พิสูจน์ว่า กติกาการเข้าถึง ต่างหากที่กำหนดผล ไม่ใช่ตัวข้อมูล
ข้อ 5 — เลือกโครงสร้างข้อมูลให้ถูก แต่ละสถานการณ์ ให้ระบุโครงสร้างที่เหมาะสมที่สุด (ลิงก์ลิสต์ทางเดียว, ลิงก์ลิสต์สองทาง, สแตก, คิว หรือ deque) พร้อมเหตุผลหนึ่งประโยค:
- การกด “เพลงก่อนหน้า” / “เพลงถัดไป” ในเครื่องเล่นเพลง
- ระบบตั๋วซัพพอร์ตลูกค้าที่ต้องให้บริการตามลำดับที่มาถึง
- การ undo และ redo การแก้ไขในโปรแกรมแก้เอกสาร
- อัลกอริทึมหน้าต่างเลื่อน (sliding window) ที่ต้องตัดสมาชิกออกทั้งจากหัวและท้ายขณะหน้าต่างเลื่อนไป
เฉลย
- ลิงก์ลิสต์สองทาง (หรือ deque ที่ทำหน้าที่แบบนั้น) — ต้องเคลื่อนที่
O(1)ได้ ทั้งสองทิศ จากเพลงปัจจุบัน - คิว — ความเป็นธรรมแบบ FIFO เข้มงวด ตั๋วที่มาก่อนต้องได้รับบริการก่อน
- สแตกสองตัว (หรือ deque หนึ่งตัว) — undo/redo เป็น LIFO ในแต่ละทิศทาง เหมือนรูปแบบปุ่ม Back/Forward ของเบราว์เซอร์ข้างต้นเป๊ะ
- Deque — ต้องการลบที่ ทั้งสองปลาย ด้วย
O(1)ขณะหน้าต่างเลื่อนไปข้างหน้า
ข้อ 6 — สร้างฟีเจอร์ undo
ออกแบบคลาส TextEditor ที่มีเมท็อด type(ch) และ undo() โดยใช้สแตกเก็บประวัติ
เฉลย
class TextEditor: def __init__(self) -> None: self.history: list[str] = []
def type(self, ch: str) -> None: self.history.append(ch)
def undo(self) -> None: if self.history: self.history.pop()
def text(self) -> str: return "".join(self.history)ทุกการกดแป้นคือ push, O(1); ทุกการ undo คือ pop, O(1) ทั้งฟีเจอร์คือการประยุกต์ใช้ LIFO โดยตรง
ข้อ 7 — ตรวจวงเล็บสมดุล
เขียนฟังก์ชัน is_balanced(s) ที่คืน True หากวงเล็บ ()[]{} ทุกตัวใน s จับคู่และซ้อนกันถูกต้อง
เฉลย
def is_balanced(s: str) -> bool: pairs = {")": "(", "]": "[", "}": "{"} stack: list[str] = [] for ch in s: if ch in "([{": stack.append(ch) elif ch in pairs: if not stack or stack.pop() != pairs[ch]: return False return not stackเวลา O(n) พื้นที่ O(n) ดูตัวอย่างคลี่ทีละขั้นที่ 3 ข้างบนสำหรับการไล่ทวนแบบเต็ม
ข้อ 8 — สร้างคิวจากสองสแตก สร้างคิว (enqueue/dequeue) โดยใช้สแตกสองตัวเท่านั้น (ห้ามใช้โครงสร้างอื่น)
เฉลย
class QueueFromStacks: def __init__(self) -> None: self.in_s: list[int] = [] self.out_s: list[int] = []
def enqueue(self, x: int) -> None: self.in_s.append(x)
def dequeue(self) -> int: if not self.out_s: while self.in_s: self.out_s.append(self.in_s.pop()) return self.out_s.pop()สมาชิกทุกตัวข้ามจาก in_s ไป out_s เพียงครั้งเดียว ดังนั้นแม้ dequeue ครั้งใดครั้งหนึ่งอาจมีต้นทุน O(n) เป็นครั้งคราว แต่ต้นทุน ตัดจ่าย เฉลี่ยตลอด n ปฏิบัติการคือ O(1) ต่อครั้ง
ข้อ 9 — โบนัส: กลับลำดับสตริงด้วยสแตก
เฉลย
def reverse(s: str) -> str: stack = list(s) out: list[str] = [] while stack: out.append(stack.pop()) return "".join(out)การ push ทุกตัวอักษรแล้ว pop ออกทั้งหมด จะกลับลำดับโดยธรรมชาติ — LIFO คลี่ลำดับ FIFO เดิมที่ตัวอักษรเข้ามาให้กลับด้าน
วิพากษ์โค้ดจากปัญญาประดิษฐ์ (AI Code Critique)
หัวข้อที่มีชื่อว่า “วิพากษ์โค้ดจากปัญญาประดิษฐ์ (AI Code Critique)”ปัญญาประดิษฐ์เสนอคิวดังนี้ ดูเผิน ๆ ทำงานถูกต้อง แต่มีต้นทุนซ่อนอยู่ — หาให้เจอ
class Queue: def __init__(self) -> None: self.items: list[int] = []
def enqueue(self, x: int) -> None: self.items.append(x) # O(1) — ดี
def dequeue(self) -> int: return self.items.pop(0) # ❓ ราคาเท่าไร?คำถาม:
list.pop(0)มีความซับซ้อนเท่าไร? ถ้ามีงานnชิ้น การ dequeue ทั้งหมดจะกลายเป็นเท่าไร?
เฉลย
list.pop(0) เป็น O(n) เพราะ list ของ Python คืออาเรย์ต่อเนื่องกัน สมาชิกที่เหลือทุกตัวต้องเลื่อนขึ้นมาเติมช่องว่างที่หัว ดังนั้นการ dequeue ครบ n ชิ้นจะกลายเป็น O(n²) — ช้าลงอย่างมากเมื่อข้อมูลโต และเป็นบั๊กประเภทที่ผ่านทุก unit test (ผลลัพธ์ถูกต้อง) แต่แอบพังทุก performance test เมื่อขยายสเกล
แก้ด้วย collections.deque ซึ่งสร้างจากลิงก์ลิสต์สองทางของบล็อกย่อย ทำให้ popleft() เป็น O(1) — ไม่มีการเลื่อน มีแต่การปรับพอยน์เตอร์:
from collections import deque
class Queue: def __init__(self) -> None: self.items: deque[int] = deque()
def enqueue(self, x: int) -> None: self.items.append(x) # O(1)
def dequeue(self) -> int: return self.items.popleft() # O(1)นิสัยการเป็น “ผู้ตัดสิน” ที่ดี: ทุกครั้งที่ AI เลือกใช้ list แล้วเรียก .pop(0), .insert(0, x), หรือ slice จากหัวในลูป ให้ถามว่า ข้างใต้ list นั้นคืออะไร — อาเรย์ต่อเนื่องกันเสมอ — และปฏิบัติการนั้นแตะที่หัวหรือไม่ ถ้าใช่ collections.deque มักเป็นทางแก้เสมอ
🎮 เกมเดฟ: สแตกย้อนกลับ (Undo) และคิวคำสั่ง/คิวเทิร์น
หัวข้อที่มีชื่อว่า “🎮 เกมเดฟ: สแตกย้อนกลับ (Undo) และคิวคำสั่ง/คิวเทิร์น”ประวัติ undo/redo ของเลเวลเอดิเตอร์คือปัญหา LIFO แบบเดียวกับรูปแบบปุ่ม Back/Forward ของเบราว์เซอร์ข้างบน — การแก้ไข ล่าสุด คือสิ่งแรกที่เราต้องการย้อนกลับ ส่วนบัฟเฟอร์อินพุตของเกมต่อสู้ หรือคิวปฏิบัติการของเกมแบบผลัดตา (turn-based) คือภาพสะท้อนแบบ FIFO — คำสั่งต้องยิงตามลำดับที่ผู้เล่นกดจริง และความไร้เดียงสาแบบ “ใช้ list ก็พอ” นี่เองคือจุดที่กับดัก pop(0) จากบทเรียนนี้กัดแรงที่สุด เพราะบัฟเฟอร์อินพุตถูกอ่านทุก ๆ เฟรม
ตัวอย่างคลี่ทีละขั้น — สแตก undo สำหรับเลเวลเอดิเตอร์ และคิวอินพุตที่ใช้ deque
class LevelEditor: """วางไทล์คือ push ลงสแตก, undo คือ pop ตัวล่าสุดออก"""
def __init__(self) -> None: self.tiles: list[str] = [] self.undo_stack: list[str] = [] self.redo_stack: list[str] = []
def place(self, tile: str) -> None: self.tiles.append(tile) self.undo_stack.append(tile) # push — O(1) self.redo_stack.clear() # แก้ไขใหม่ ล้างประวัติ redo ทิ้ง
def undo(self) -> None: if not self.undo_stack: return tile = self.undo_stack.pop() # LIFO — undo ตัวที่วางล่าสุดก่อน self.tiles.remove(tile) self.redo_stack.append(tile)
def redo(self) -> None: if not self.redo_stack: return tile = self.redo_stack.pop() self.tiles.append(tile) self.undo_stack.append(tile)list ธรรมดาคือเครื่องมือที่ถูกต้องตรงนี้ — ทุก push และ pop แตะแค่ “ปลาย” เดียว ซึ่งเป็น O(1) อยู่แล้ว ไม่มีอะไรต้องแก้ วินัยของ “แตะแค่ปลายเดียว” คือเหตุผลทั้งหมดที่มันใช้ได้ผล
บัฟเฟอร์อินพุตเป็นอีกเรื่องหนึ่ง ร่างแรกแบบไร้เดียงสา:
class InputBuffer: """ไร้เดียงสา: ทำงานถูก แต่ถูกเช็คทุกเฟรม — ต้นทุนซ่อนอยู่ตรงไหน?"""
def __init__(self) -> None: self.queue: list[str] = []
def press(self, action: str) -> None: self.queue.append(action) # enqueue — O(1)
def next_action(self) -> str | None: return self.queue.pop(0) if self.queue else None # ❓ O(n)!ที่ 60 เฟรมต่อวินาที pop(0) นี้เลื่อนอินพุตที่ค้างอยู่ทุกตัวไปทางซ้ายทีละช่อง ทุกเฟรม ตราบเท่าที่บัฟเฟอร์ยังมีของอยู่ — กับดัก O(n) เป๊ะแบบเดียวกับในหัวข้อ “วิพากษ์โค้ดจากปัญญาประดิษฐ์” ข้างบน เพียงแต่ย้ายมาอยู่ใน hot loop ทางแก้แบบขยายสเกลก็เหมือนเดิม: สลับไปใช้ collections.deque
from collections import deque
class InputBuffer: def __init__(self) -> None: self.queue: deque[str] = deque()
def press(self, action: str) -> None: self.queue.append(action) # enqueue — O(1)
def next_action(self) -> str | None: return self.queue.popleft() if self.queue else None # dequeue — O(1)รูป: สแตก undo pop การเปลี่ยนแปลงล่าสุดออกก่อน (LIFO) ส่วนคิวอินพุตเล่นซ้ำคำสั่งที่บัฟเฟอร์ไว้ตามลำดับที่มาถึง (FIFO)
แต่ไม่ใช่ทุกลำดับในเกมจะเป็น FIFO ธรรมดา — เกมแบบผลัดตาที่ตัวละครความเร็วสูงต้องได้ลงมือก่อนเสมอ ไม่ว่าเทิร์นของมันจะถูกเข้าคิวเมื่อไร ต้องใช้คิวที่เรียงตาม ความสำคัญ (ค่าความเร็ว) แทนลำดับการมาถึง ลองเล่นด้านล่าง: มันคือคำถาม “ใครไปต่อ” แบบเดียวกัน เพียงแต่กติกาของคำว่า “ต่อไป” เปลี่ยนไป
แบบฝึกหัด
หัวข้อที่มีชื่อว่า “แบบฝึกหัด”ข้อ G1 — สแตกหรือคิว? แต่ละฟีเจอร์ ให้ระบุ สแตก หรือ คิว พร้อมเหตุผลหนึ่งประโยค:
- สถานีคราฟต์ที่ต้องคราฟต์ไอเทมเสร็จตามลำดับที่ผู้เล่นสั่งเข้าคิว
- กลไก “ย้อนเวลา” ที่ให้ผู้เล่นถอยหลังผ่านการเคลื่อนไหวไม่กี่ครั้งล่าสุด
- ระบบบทสนทนา NPC ที่ต้องแสดงประโยคตามลำดับที่ถูกกระตุ้น
- ปุ่ม Ctrl+Z ของเลเวลเอดิเตอร์
เฉลย
- คิว — สั่งก่อนคราฟต์ก่อน ความเป็นธรรมแบบ FIFO
- สแตก — ย้อนเวลาคือ undo การเคลื่อนไหว ล่าสุด ก่อน แบบ LIFO
- คิว — บทสนทนาต้องเล่นตามลำดับที่ถูกกระตุ้น ไม่ใช่กลับด้าน
- สแตก — เหตุผลเดียวกับเลเวลเอดิเตอร์ข้างบน Ctrl+Z คือการ pop
ข้อ G2 — ทายผลลัพธ์ undo/redo
ed = LevelEditor()ed.place("torch")ed.place("chest")ed.undo()ed.place("door")ed.undo()ed.redo()print(ed.tiles)เฉลย
ไล่ทีละขั้น: place torch → [torch]; place chest → [torch, chest]; undo pop chest ออก → [torch] (redo_stack = [chest]); place door → [torch, door] ซึ่ง ล้าง redo_stack ทิ้ง; undo pop door ออก → [torch] (redo_stack = [door]); redo pop door กลับมา → [torch, door] คำตอบสุดท้าย: ['torch', 'door'] — สังเกตว่า chest หายไปตลอดกาล เพราะการวาง door ล้างประวัติ redo ที่เคยเก็บมันไว้
ข้อ G3 — ทำไมไม่สแกนประวัติทั้งหมดแทน?
โปรแกรมเมอร์จูเนียร์เสนอให้เก็บทุกปฏิบัติการของเอดิเตอร์ใน list เดียว แล้วเวลา undo ก็หา action “ล่าสุด” ด้วยการสแกนจากดัชนี 0 ไปจนถึง len(list) - 1 ทำไมกรอบคิดแบบสแตกยังดีกว่า ทั้งที่ list[-1] ก็เป็น O(1) อยู่แล้วใน Python?
เฉลย
list[-1] และ list.pop() เป็น O(1) ทั้งคู่ใน CPython จริง — list ธรรมดา ก็คือ สแตกที่ดีอยู่แล้วตราบใดที่แตะแค่ปลายเดียว คุณค่าของการเรียกมันว่า “สแตก” ตรงนี้ไม่ใช่การแก้ปัญหาความเร็ว แต่เป็นวินัยเรื่อง ความถูกต้อง: มันบังคับให้เราไม่มีวันเอื้อมเข้าไปกลางลิสต์ (เช่น “undo action ที่ 3 จากท้าย”) ไม่งั้นจะเสียการรับประกันว่าประวัติ redo ยังคงสอดคล้องกัน คำศัพท์ push/pop คือสัญญา ไม่ใช่แค่การปรับความเร็ว
ข้อ G4 — บัฟเฟอร์อินพุต deque เทียบกับ list
เกมจังหวะ (rhythm game) อ่านอินพุตที่บัฟเฟอร์ไว้หนึ่งตัวต่อเฟรมที่ 60 FPS และบัฟเฟอร์รับได้สูงสุด 200 อินพุตค้างคิวช่วงที่ยุ่ง ประเมินงานเลื่อนสมาชิกทั้งหมดที่ list.pop(0) ต้องทำใน 1 วินาที เทียบกับ deque.popleft()
เฉลย
ด้วย list.pop(0) การ dequeue แต่ละครั้งเลื่อนสมาชิกได้ถึงประมาณ 200 ตัว และเกิดขึ้นได้ถึง 60 ครั้งต่อวินาที — กรณีเลวร้ายสุดราว 60 × 200 = 12,000 การเลื่อนสมาชิกต่อวินาที และโตแบบกำลังสองตามขนาดบัฟเฟอร์ deque.popleft() ทำ dequeue 60 ครั้งเท่ากันแต่ที่ O(1) แต่ละครั้ง — การปรับพอยน์เตอร์จำนวนน้อยคงที่ต่อวินาที ไม่ว่าบัฟเฟอร์จะใหญ่แค่ไหน ความต่างนี้มองไม่เห็นตอนบัฟเฟอร์มี 5 อินพุต แต่เห็นชัดมาก (เฟรมหลุด) ตอน 200 อินพุต
โจทย์ท้าทาย
หัวข้อที่มีชื่อว่า “โจทย์ท้าทาย”โจทย์ท้าทาย 1 — ตัวจับอินพุตคอมโบ
สร้างบัฟเฟอร์อินพุตของเกมต่อสู้ที่จำแค่การกดปุ่ม 5 ครั้งล่าสุด และตรวจจับว่าตรงกับลำดับท่าไม้ตายหรือไม่ เช่น ["down", "down-forward", "forward", "punch"]
แนวทาง
ใช้ collections.deque(maxlen=5) — การ append เกินขีดจำกัดจะทิ้งตัวเก่าสุดออกอัตโนมัติ ไม่ต้องตัดบัฟเฟอร์เองเลย หลังทุก append ให้เทียบสมาชิก ท้ายสุด จำนวน len(sequence) ตัว (สไลซ์ของ deque ที่แปลงเป็นลิสต์) กับลำดับเป้าหมาย:
from collections import deque
class ComboBuffer: def __init__(self, size: int = 5) -> None: self.buffer: deque[str] = deque(maxlen=size)
def press(self, action: str) -> None: self.buffer.append(action)
def matches(self, sequence: list[str]) -> bool: recent = list(self.buffer)[-len(sequence):] return recent == sequencemaxlen คือไอเดียสำคัญ: มันเปลี่ยน deque ให้เป็นหน้าต่างเลื่อนขนาดคงที่ที่ push เป็น O(1) และเขี่ยตัวเก่าออกอัตโนมัติ แทนที่จะสไลซ์ลิสต์ที่โตขึ้นเรื่อย ๆ เองทุกเฟรม
โจทย์ท้าทาย 2 — ตารางเวลาปฏิบัติการหน่วง RPG แบบผลัดตาต้องการเอฟเฟกต์แบบ “พิษ: 3 ดาเมจต่อเทิร์น เป็นเวลา 3 เทิร์น” และเอฟเฟกต์หน่วง/ซ้ำแบบอื่น ๆ ออกแบบระบบที่ทุกเทิร์นจะยิงทุกเอฟเฟกต์ที่นับถอยหลังถึงศูนย์แล้ว โดยใช้แค่โครงสร้างแบบคิวเท่านั้น
แนวทาง
เก็บคิวของคู่ (turns_remaining, effect) ทุกเทิร์น: dequeue ทุกอย่างที่อยู่ในคิวตอนนี้ ลดตัวนับแต่ละตัวลง ใช้เอฟเฟกต์ แล้ว enqueue กลับเฉพาะตัวที่ turns_remaining > 0:
from collections import deque
def process_turn(effects: deque[tuple[int, str]]) -> None: for _ in range(len(effects)): turns_left, effect = effects.popleft() apply_effect(effect) # เช่น ให้ดาเมจพิษ if turns_left - 1 > 0: effects.append((turns_left - 1, effect))วิธีนี้ใช้ได้เพราะทุกอย่างในคิวถูกเช็คทุกเทิร์น — เหมาะกับเอฟเฟกต์จำนวนไม่มาก ถ้าเอฟเฟกต์ยิงที่ เทิร์นอนาคตต่างกัน แทน (เช่น “ร่ายเวทที่จะลงในอีก 5 เทิร์น” ปนกับ “พิษติ๊กทุกเทิร์น”) การสแกนทั้งคิวทุกเทิร์นจะเสียงานเปล่า ควรใช้คิวลำดับความสำคัญ (priority queue) ที่เรียงตามเทิร์นที่จะเกิดแทน เพื่อดูแค่ตัวที่ใกล้ที่สุดเท่านั้น — ไอเดียเดียวกับคิวเทิร์นเรียงตามความเร็วข้างบน เพียงแต่ใช้ “เมื่อไร” แทน “เร็วแค่ไหน” เป็นตัวเรียง
เจาะลึกเพิ่มเติม
หัวข้อที่มีชื่อว่า “เจาะลึกเพิ่มเติม”- MIT 6.006 — Introduction to Algorithms (Lecture 2: data structures)
- Harvard CS50 — Data Structures (สแตก คิว ลิงก์ลิสต์)
- VisuAlgo — Linked List และ Stack/Queue (ภาพเคลื่อนไหวเชิงโต้ตอบ)
- CLRS — Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (ฉบับที่ 4) บทที่ 10: Elementary Data Structures — การอธิบายเชิงทางการฉบับมาตรฐานของสแตก คิว และลิงก์ลิสต์ รวมถึงการอิมพลีเมนต์แบบพอยน์เตอร์โดยไม่มี garbage collector
- Sedgewick & Wayne — Algorithms (ฉบับที่ 4) ตอนที่ 1.3: Bags, Queues, and Stacks — โค้ด Java ที่สะอาด และการเปรียบเทียบข้อดีข้อเสียระหว่างลิงก์ลิสต์กับอาเรย์ที่ปรับขนาดได้
- Weiss — Data Structures and Algorithm Analysis บทที่ 3: Lists, Stacks, and Queues — อธิบายลิงก์ลิสต์แบบทางเดียว/สองทาง/วงกลมอย่างละเอียด พร้อมการวิเคราะห์แบบตัดจ่าย (amortized analysis)
- Goodrich, Tamassia & Goldwasser — Data Structures and Algorithms in Python บทที่ 6–7: Stacks, Queues, and Deques; Linked Lists — อิมพลีเมนต์แบบ Python ล้วน ที่แม็ปตรงกับโค้ดในบทเรียนนี้