อัลกอริทึม Python

โครงสร้างข้อมูลสแตก (stack) ใน Python

ในบทเรียนนี้ คุณจะใช้ลิสต์ของ Python สร้างการทำงานพื้นฐานของสแตก ได้แก่ push, pop และ peek

  • ระดับกลาง
  • อ่าน 2 นาที
  • ตัวอย่างที่รันได้ 1 ตัวอย่าง

บทนำ

ปัญหาที่ต้องแก้

ปุ่ม undo ปุ่มย้อนกลับในเบราว์เซอร์ และการตรวจวงเล็บที่จับคู่กัน ล้วนต้องจำรายการและเอารายการล่าสุดกลับมาก่อน สแต็กคือโครงสร้างข้อมูลที่สร้างมาเพื่อสิ่งนั้นโดยเฉพาะ

ลองนึกภาพแบบนี้

สแต็กเหมือนกองจานในโรงอาหาร คุณวางจานใหม่ไว้ด้านบนและหยิบจานจากด้านบน จานที่เพิ่มล่าสุดคือจานแรกที่ถูกใช้ และคุณดึงจานจากตรงกลางไม่ได้

จากกองจานสู่โค้ด
stack.append("third")🍽️ วางจานไว้ด้านบน
stack.pop()⬆️ หยิบจานบนสุดออก
stack[-1]👀 ดูจานบนสุดโดยไม่หยิบ
stack📚 จานที่ยังอยู่บนกอง
เข้าหลัง ออกก่อน: เข้าถึงได้แค่ด้านบน
สรุปในประโยคเดียว

สแต็กคือคอลเลกชันแบบเข้าหลังออกก่อน (LIFO): รายการถูกเพิ่มและเอาออกที่ด้านบนเท่านั้น

ประเด็นสำคัญ

  1. stack.append(...) push รายการขึ้นด้านบน ซึ่งคือท้ายลิสต์
  2. stack.pop() เอาออกและคืนรายการบนสุด ในที่นี้คือ "third"
  3. stack[-1] อ่านรายการบนสุดโดยไม่เอาออก
  4. ทั้ง append และ pop ทำงานที่ท้ายลิสต์ จึงเร็ว

ใช้เมื่อไร?

  • ประวัติการ undo และ redo
  • ตรวจวงเล็บที่จับคู่กันและแยกวิเคราะห์นิพจน์
  • depth-first search และ backtracking โดยไม่ใช้ recursion

เมื่อไรยังไม่จำเป็น

  • รายการต้องออกตามลำดับที่มาถึง: นั่นคือคิว
  • คุณต้องการรายการจากตรงกลางหรือตามตำแหน่ง: ลิสต์ปกติหรือโครงสร้างอื่นเหมาะกว่า

ดูการทำงาน

ลอง push และ pop เพื่อดูว่าสิ่งที่ใส่เข้าไปล่าสุดจะออกมาก่อนเสมอ

โค้ดตัวอย่าง

รันโค้ด →
main.py
stack = []
stack.append("first")
stack.append("second")
stack.append("third")

print("popped:", stack.pop())
print("top:", stack[-1])
print("stack:", stack)
สร้างปุ่ม Run สำหรับตัวอย่างนี้

ผลลัพธ์จากการรัน

popped: third
top: second
stack: ['first', 'second']

อธิบายโค้ด

เมธอด append() วางสมาชิกไว้บนสุดของสแตก และ pop() หยิบสมาชิกบนสุดออกมาและคืนค่า "third" จึงออกมาก่อน stack[-1] ใช้ดูสมาชิกบนสุดโดยไม่หยิบออก append() และ pop() ที่ท้ายลิสต์ใช้เวลาเฉลี่ย O(1)

เปลี่ยนค่าและรันโปรแกรมด้วย คอมไพเลอร์ Python ออนไลน์ของ CodeUtility โดยไม่ต้องติดตั้ง Python

แบบฝึกหัดเพิ่มเติม

ลองแก้โค้ดตามคำแนะนำด้านล่าง การเปลี่ยนโค้ดแล้วดูผลลัพธ์จะช่วยให้เข้าใจบทเรียนได้ดีกว่าการอ่านอย่างเดียวมาก

  1. ทดสอบกับลิสต์ว่าง ลิสต์ที่มีสมาชิกตัวเดียว และลิสต์ที่มีค่าซ้ำ
  2. แสดงสถานะหลังแต่ละขั้นเพื่อดูการทำงานของอัลกอริทึม
  3. จับเวลาการทำงานกับข้อมูล 100, 1,000 และ 10,000 ตัว แล้วเทียบกับวิธีอื่น
รันในคอมไพเลอร์ Python →

ข้อผิดพลาดที่พบบ่อย

pop จากสแต็กที่ว่าง

pop() บนลิสต์ว่างเกิด IndexError

ปัญหา
item = stack.pop()
วิธีแก้
if stack:
    item = stack.pop()

ใช้ด้านหน้าของลิสต์เป็นด้านบน

insert(0, x) และ pop(0) ย้ายทุกรายการ ซึ่งช้า

ปัญหา
stack.insert(0, item)
stack.pop(0)
วิธีแก้
stack.append(item)
stack.pop()

เรียนบทนี้จบแล้วใช่ไหม

ทำเครื่องหมายว่าเรียนแล้วเพื่อติดตามความคืบหน้า

ถัดไป: การค้นหาตามแนวกว้าง (BFS) ใน Python →

ฝึกด้วยโจทย์

ใช้สิ่งที่เรียนในบทนี้แก้ปัญหาจริง ทุกโจทย์รันในเบราว์เซอร์ พร้อมการทดสอบทันทีและรีวิวจาก AI

โจทย์ทั้งหมด