On this page
บทเรียน: Stack & Queue
👋 อ่านฟรีทั้งหมดบน Aph's Blog — เนื้อหาภาษาไทย ทำตามทีละหน้าใน sidebar ได้เลย หากมีข้อเสนอแนะหรืออยากให้เพิ่มหัวข้อไหน บอกได้เสมอ
Stack เข้าทีหลังออกก่อน (LIFO), Queue เข้าก่อนออกก่อน (FIFO)
Stack และ Queue เป็นโครงสร้างที่จำกัดวิธีเพิ่ม/เอาออก Stack = เข้าทีหลังออกก่อน (เหมือนกองจาน) Queue = เข้าก่อนออกก่อน (เหมือนเข้าแถว) ทั้งคู่เพิ่ม/ลบเป็น O(1)
Stack: ตรวจวงเล็บถูกคู่ไหม
python
def is_valid(s):
stack = []
pairs = {')': '(', ']': '[', '}': '{'}
for ch in s:
if ch in '([{':
stack.append(ch)
elif not stack or stack.pop() != pairs[ch]:
return False
return not stack
print(is_valid("([])")) # True
print(is_valid("([)]")) # FalseQueue: ใช้ deque
python
from collections import deque
q = deque()
q.append(1) # เข้าท้าย
q.append(2)
print(q.popleft()) # 1 (ออกหัว)เจอเมื่อไหร่
Stack เหมาะกับการจับคู่ (วงเล็บ), undo, และโจทย์ "next greater element" (monotonic stack) ส่วน Queue ใช้คู่กับ BFS เสมอ