Dùng List làm Stack và Queue trong Python

List Python có thể dùng làm Stack (LIFO) và Queue (FIFO) nhờ các method built-in.

Stack - Last In First Out

• Push: list.append(item) - O(1)
• Pop: list.pop() - O(1)
• Peek: list[-1] - O(1)
• Empty check: not stack hoặc len(stack) == 0

stack = []
stack.append(1)
stack.append(2)
stack.append(3)
print("Stack:", stack)        # [1, 2, 3]
print("Pop:", stack.pop())    # 3
print("Peek:", stack[-1])     # 2
print("Stack:", stack)        # [1, 2]

Queue - First In First Out

• Enqueue: list.append(item) - O(1)
• Dequeue: list.pop(0) - O(n) (dịch chuyển tất cả phần tử!)
• Peek: list[0]

# List as Queue - KHÔNG KHUYẾN NGHỊ cho data lớn
queue = []
queue.append(5)
queue.append(6)
queue.append(9)
print("Dequeue:", queue.pop(0))  # 5 - O(n)!
print("Queue:", queue)           # [6, 9]

Queue hiệu năng cao: collections.deque

from collections import deque

queue = deque()
queue.append(5)      # Enqueue right
queue.append(6)
queue.append(9)
print("Dequeue:", queue.popleft())  # 5 - O(1)!
print("Queue:", queue)              # deque([6, 9])

So sánh hiệu năng

Kết luận

• Stack: List Python hoàn hảo (append/pop đều O(1)).
• Queue: KHÔNG dùng list (pop(0) O(n)). Bắt buộc dùng collections.deque cho O(1)兩 đầu.