โครงสร้างข้อมูลสแตก (stack) ใน Python
ในบทเรียนนี้ คุณจะใช้ลิสต์ของ Python สร้างการทำงานพื้นฐานของสแตก ได้แก่ push, pop และ peek
บทนำ
ปัญหาที่ต้องแก้
ปุ่ม undo ปุ่มย้อนกลับในเบราว์เซอร์ และการตรวจวงเล็บที่จับคู่กัน ล้วนต้องจำรายการและเอารายการล่าสุดกลับมาก่อน สแต็กคือโครงสร้างข้อมูลที่สร้างมาเพื่อสิ่งนั้นโดยเฉพาะ
ลองนึกภาพแบบนี้
สแต็กเหมือนกองจานในโรงอาหาร คุณวางจานใหม่ไว้ด้านบนและหยิบจานจากด้านบน จานที่เพิ่มล่าสุดคือจานแรกที่ถูกใช้ และคุณดึงจานจากตรงกลางไม่ได้
stack.append("third")🍽️ วางจานไว้ด้านบนstack.pop()⬆️ หยิบจานบนสุดออกstack[-1]👀 ดูจานบนสุดโดยไม่หยิบstack📚 จานที่ยังอยู่บนกองสแต็กคือคอลเลกชันแบบเข้าหลังออกก่อน (LIFO): รายการถูกเพิ่มและเอาออกที่ด้านบนเท่านั้น
ประเด็นสำคัญ
stack.append(...)push รายการขึ้นด้านบน ซึ่งคือท้ายลิสต์stack.pop()เอาออกและคืนรายการบนสุด ในที่นี้คือ"third"stack[-1]อ่านรายการบนสุดโดยไม่เอาออก- ทั้ง
appendและpopทำงานที่ท้ายลิสต์ จึงเร็ว
ใช้เมื่อไร?
- ประวัติการ undo และ redo
- ตรวจวงเล็บที่จับคู่กันและแยกวิเคราะห์นิพจน์
- depth-first search และ backtracking โดยไม่ใช้ recursion
เมื่อไรยังไม่จำเป็น
- รายการต้องออกตามลำดับที่มาถึง: นั่นคือคิว
- คุณต้องการรายการจากตรงกลางหรือตามตำแหน่ง: ลิสต์ปกติหรือโครงสร้างอื่นเหมาะกว่า
ดูการทำงาน
ลอง push และ pop เพื่อดูว่าสิ่งที่ใส่เข้าไปล่าสุดจะออกมาก่อนเสมอ
โค้ดตัวอย่าง
stack = []
stack.append("first")
stack.append("second")
stack.append("third")
print("popped:", stack.pop())
print("top:", stack[-1])
print("stack:", stack)
ผลลัพธ์จากการรัน
popped: third
top: second
stack: ['first', 'second']
อธิบายโค้ด
เมธอด append() วางสมาชิกไว้บนสุดของสแตก และ pop() หยิบสมาชิกบนสุดออกมาและคืนค่า "third" จึงออกมาก่อน stack[-1] ใช้ดูสมาชิกบนสุดโดยไม่หยิบออก append() และ pop() ที่ท้ายลิสต์ใช้เวลาเฉลี่ย O(1)
เปลี่ยนค่าและรันโปรแกรมด้วย คอมไพเลอร์ Python ออนไลน์ของ CodeUtility โดยไม่ต้องติดตั้ง Python
แบบฝึกหัดเพิ่มเติม
ลองแก้โค้ดตามคำแนะนำด้านล่าง การเปลี่ยนโค้ดแล้วดูผลลัพธ์จะช่วยให้เข้าใจบทเรียนได้ดีกว่าการอ่านอย่างเดียวมาก
- ทดสอบกับลิสต์ว่าง ลิสต์ที่มีสมาชิกตัวเดียว และลิสต์ที่มีค่าซ้ำ
- แสดงสถานะหลังแต่ละขั้นเพื่อดูการทำงานของอัลกอริทึม
- จับเวลาการทำงานกับข้อมูล 100, 1,000 และ 10,000 ตัว แล้วเทียบกับวิธีอื่น
ข้อผิดพลาดที่พบบ่อย
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()
เรียนบทนี้จบแล้วใช่ไหม
ทำเครื่องหมายว่าเรียนแล้วเพื่อติดตามความคืบหน้า
ฝึกด้วยโจทย์
ใช้สิ่งที่เรียนในบทนี้แก้ปัญหาจริง ทุกโจทย์รันในเบราว์เซอร์ พร้อมการทดสอบทันทีและรีวิวจาก AI
- Nearest Smaller Value to the Left For each number, find the closest earlier position containing a strictly smaller number. ปานกลาง
- Mini Stack-Language Interpreter Evaluate a small stack language. ยาก