On this page
Stack — พื้นฐาน & แนวคิด
กองข้อมูลที่ "ใส่ทีหลัง หยิบออกก่อน" (LIFO) — นึกถึงกระป๋อง Pringles หรือกองจาน แล้วใช้ list ของ Python เป็นอาวุธได้ทันที
เวลาได้ยินคำว่า data structure (โครงสร้างข้อมูล) มือใหม่อาจคิดว่าต้องเป็นโค้ดซับซ้อน แต่ Stack (สแต็ก) คือโครงสร้างที่ไอเดียง่ายที่สุดอย่างหนึ่ง — และเป็นอาวุธหลักของโจทย์ในหมวดนี้ทั้งหมด
ส่วนที่ 1 · ปลดล็อกไอเดีย
ภาพจำ: นึกถึงกระป๋องมันฝรั่ง Pringles หรือกองจาน — แผ่นแรกที่ใส่ตกไปก้นกระป๋อง แผ่นถัดไปทับลงไป แผ่นสุดท้ายอยู่บนสุด เวลาหยิบกินต้องหยิบแผ่นบนสุดออกก่อนเสมอ เสกแผ่นล่างสุดทะลุกระป๋องออกมาไม่ได้ (ถ้าทำได้คือพัง) นี่คือคอนเซปต์ทั้งหมดของ stack
| 30 | <- top (หยิบออกก่อน)
| 20 |
| 10 | <- bottom (ใส่เข้ามาก่อนสุด)
+----+
pop() ได้ 30 · กองเหลือ [10, 20]ส่วนที่ 2 · กฎเหล็ก — LIFO
Stack มีกฎเดียวที่ต้องเคารพ: LIFO = Last In, First Out = "เข้าทีหลัง ออกก่อน" อาวุธประจำกายมี 3 ท่า:
- Push — วางของชิ้นใหม่ทับลงบนสุดของกอง
- Pop — หยิบของชิ้นบนสุดออกจากกอง (ชิ้นนั้นหายจากกองเลย)
- Peek / Top — แอบดูว่าของบนสุดคืออะไร แต่ยังไม่หยิบออก
ส่วนที่ 3 · ใน Python พร้อมใช้เลย
ข่าวดี: ไม่ต้อง import อะไร — list ธรรมดา `[ ]` ทำหน้าที่เป็น stack ได้ครบด้วยคำสั่งที่คุ้นอยู่แล้ว
| แอคชันของ Stack | คำสั่ง Python (ใช้ list) | Big-O |
|---|---|---|
| Push (ใส่ของ) | stack.append(x) | O(1) |
| Pop (ดึงออก) | stack.pop() | O(1) |
| Peek (แอบดู) | stack[-1] | O(1) |
| Is Empty (ว่างไหม) | not stack | O(1) |
เราแตะแค่ของที่อยู่ปากกระป๋องเท่านั้น ไม่ต้องเลื่อนหรือไล่ของข้างล่าง — กองสูงแค่ไหนก็เร็วเท่าเดิม
ส่วนที่ 4 · จำลองการทำงาน
ลองหย่อนตัวเลขใส่กระป๋องทีละชิ้น แล้วดูว่า Peek กับ Pop ต่างกันยังไง:
stack = [] # 1. กระป๋องเปล่า
stack.append(10) # 2. Push 10 -> [10]
stack.append(20) # 3. Push 20 -> [10, 20]
stack.append(30) # 4. Push 30 -> [10, 20, 30]
print(stack[-1]) # 5. Peek ตัวบนสุด -> 30 (กองยังเป็น [10, 20, 30])
top = stack.pop() # 6. Pop ตัวบนสุด -> ได้ 30, กองเหลือ [10, 20]
print(top)
# 7. เทของออกให้หมด (เคลียร์ stack)
while stack:
print(stack.pop()) # ได้ 20 ก่อน แล้วตามด้วย 1030
30
20
10ส่วนที่ 5 · สัญญาณว่าโจทย์ข้อนี้ต้องใช้ Stack
เวลาลุย LeetCode ถ้าเจอสถานการณ์แบบนี้ ให้นึกถึง stack เป็นอันดับแรก:
- ตรวจจับการจับคู่ / เปิด-ปิด — เช่น จับคู่วงเล็บ (เจอเปิดให้เก็บไว้ เจอปิดค่อยเทียบกับตัวล่าสุด)
- การย้อนรอย (Undo / Backspace) — เช่น เจอ # ให้ลบตัวอักษรที่เพิ่งพิมพ์ไปก่อนหน้า
- ข้อมูลซ้อนชั้น (Nested) — เช่น ถอดรหัสข้อความที่มีวงเล็บซ้อนหลายชั้น เช่น 3[a2[c]]
ถ้าต้องจำของล่าสุดไว้ก่อน เพื่อรอเอามาจัดการทีหลัง = ใช้ Stack
พื้นฐานครบแล้ว — หมวดนี้มี 3 ข้อ: Removing Stars · Asteroid Collision · Decode String พร้อมแล้วกดถัดไปลุยข้อแรกได้เลย