Stack, Queue & Deque
👋 อ่านฟรีทั้งหมดบน Aph's Blog — เนื้อหาภาษาไทย ทำตามทีละหน้าใน sidebar ได้เลย หากมีข้อเสนอแนะหรืออยากให้เพิ่มหัวข้อไหน บอกได้เสมอ
สองโครงสร้างพื้นฐาน: stack (เข้าหลังออกก่อน) และ queue (เข้าก่อนออกก่อน)
stack และ queue เป็นโครงสร้างที่เจอทุกที่ ตั้งแต่ undo/redo, การเรียกฟังก์ชัน, ไปจนถึงคิวงาน เข้าใจสองตัวนี้แล้วต่อยอดไปอีกหลายเรื่อง
Stack — LIFO (Last In, First Out)
เข้าทีหลังออกก่อน เหมือนกองจานซ้อนกัน — ใช้ list ได้เลย (append/pop ท้าย เป็น O(1))
python
stack = []
stack.append(1) # push
stack.append(2)
stack.append(3)
print(stack.pop()) # 3 (ตัวล่าสุดออกก่อน)
print(stack.pop()) # 2
print(stack) # [1]ใช้จริง: ตรวจวงเล็บสมดุล, undo, การเรียกฟังก์ชัน (call stack), ประวัติเบราว์เซอร์
python
def is_balanced(s):
stack = []
pairs = {")": "(", "]": "[", "}": "{"}
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 len(stack) == 0
print(is_balanced("([{}])")) # True
print(is_balanced("([)]")) # FalseQueue — FIFO (First In, First Out)
เข้าก่อนออกก่อน เหมือนคนต่อแถว — ใช้ deque (จากบท collections) เพราะ pop หัวแถวเป็น O(1)
python
from collections import deque
queue = deque()
queue.append("a") # เข้าคิว
queue.append("b")
queue.append("c")
print(queue.popleft()) # 'a' (เข้าก่อนออกก่อน)
print(queue.popleft()) # 'b'อย่าใช้ list.pop(0) เป็น queue
list.pop(0) ดึงหัวแถวเป็น O(n) เพราะต้องเลื่อนทุกตัว — ช้ามากเมื่อข้อมูลเยอะ ใช้ collections.deque ที่ popleft() เป็น O(1) เสมอสำหรับ queue
สรุปหัวข้อนี้
- stack = LIFO (เข้าหลังออกก่อน) — ใช้ list, append/pop ท้าย O(1)
- queue = FIFO (เข้าก่อนออกก่อน) — ใช้ deque, popleft O(1)
- stack ใช้: ตรวจวงเล็บ, undo, call stack
- อย่าใช้ list.pop(0) ทำ queue (O(n)) — ใช้ deque
แบบฝึกหัด
1) เขียนฟังก์ชันตรวจวงเล็บสมดุลด้วย stack 2) จำลอง undo ด้วย stack 3) จำลองคิวงานด้วย deque 4) อธิบายว่าทำไม list.pop(0) ช้ากว่า deque.popleft()