Ngăn xếp và hàng đợi: LIFO và FIFO kèm ví dụ Python

Ngăn xếp và hàng đợi giải quyết vấn đề gì

Nhiều chương trình cần nhớ các phần tử rồi xử lý sau theo một thứ tự cố định. Ngăn xếp trả về phần tử mới nhất trước, phù hợp với công việc lồng nhau: lời gọi hàm, lịch sử hoàn tác, ghép cặp ngoặc và tìm kiếm theo chiều sâu. Hàng đợi trả về phần tử cũ nhất trước, phù hợp với việc chờ công bằng: hàng chờ in, bộ lập lịch tác vụ, hàng đợi thông điệp và tìm kiếm theo chiều rộng.

Cả hai đều là kiểu dữ liệu trừu tượng: chúng được định nghĩa bằng các thao tác, không phải bằng cách lưu trữ. Bạn có thể xây dựng chúng trên mảng hoặc danh sách liên kết.

Các thao tác và tên gọi

Ví dụ minh họa: push và pop từng bước

Đẩy 1, 2 và 3 vào cả hai cấu trúc, rồi lấy ra hai phần tử.

Cài đặt bằng Python

list của Python đã là một ngăn xếp tốt: append và pop() làm việc ở cuối danh sách trong O(1) khấu hao. Với hàng đợi, đừng dùng list.pop(0), vì nó dịch mọi phần tử còn lại và tốn O(n). Hãy dùng collections.deque, có O(1) ở cả hai đầu.

from collections import deque
stack = []
stack.append(1)
stack.append(2)
stack.append(3)
print(stack.pop(), stack[-1])   # 3 2
queue = deque()
queue.append("a")
queue.append("b")
queue.append("c")
print(queue.popleft(), queue[0])  # a b
print(len(stack), len(queue))     # 2 2

Nếu muốn có phương thức đặt tên rõ ràng và thông báo lỗi dễ hiểu, hãy bọc các kiểu dựng sẵn trong một lớp nhỏ:

from collections import deque
class Queue:
    def __init__(self):
        self._items = deque()
    def enqueue(self, item):
        self._items.append(item)
    def dequeue(self):
        if not self._items:
            raise IndexError("dequeue from empty queue")
        return self._items.popleft()
    def __len__(self):
        return len(self._items)
q = Queue()
q.enqueue("job1")
q.enqueue("job2")
print(q.dequeue(), len(q))  # job1 1

Bài toán kinh điển của ngăn xếp: ngoặc cân bằng

Để kiểm tra mọi dấu ngoặc đều được đóng đúng thứ tự, hãy đẩy từng ngoặc mở vào ngăn xếp. Khi gặp ngoặc đóng, phần tử trên đỉnh ngăn xếp phải là ngoặc mở tương ứng.

def is_balanced(text):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in text:
        if ch in "([{":
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack
print(is_balanced("f(a[1], {b: 2})"))  # True
print(is_balanced("(]"))               # False
print(is_balanced("(("))               # False

Cùng ý tưởng này dùng để tính biểu thức ở dạng ký pháp Ba Lan ngược, chuyển đệ quy thành vòng lặp, và là cơ sở của tìm kiếm theo chiều sâu: thay ngăn xếp lời gọi bằng list của riêng bạn.

Bài toán kinh điển của hàng đợi: tìm kiếm theo chiều rộng

Tìm kiếm theo chiều rộng (BFS) duyệt đồ thị từng tầng một. Hàng đợi giúp điều đó xảy ra: node được phát hiện trước sẽ được xử lý trước.

from collections import deque
def bfs_order(graph, start):
    seen = {start}
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in graph[node]:
            if nxt not in seen:
                seen.add(nxt)
                queue.append(nxt)
    return order
graph = {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": []}
print(bfs_order(graph, "A"))  # ['A', 'B', 'C', 'D']

Độ phức tạp thời gian và không gian

Khấu hao (amortized) nghĩa là đôi khi một lần append phải đổi kích thước mảng bên dưới và tốn O(n), nhưng tính trung bình qua nhiều thao tác thì mỗi thao tác là O(1).

Các biến thể và lỗi thường gặp

• Deque (hàng đợi hai đầu): thêm và lấy ở cả hai đầu. collections.deque chính là một deque, và nó có thể đóng vai cả ngăn xếp lẫn hàng đợi.
• Hàng đợi ưu tiên (priority queue): lấy phần tử nhỏ nhất (hoặc lớn nhất) trước, không phải phần tử cũ nhất. Dùng heapq; xem trang về heap nhị phân.
• Bộ đệm vòng (circular buffer): hàng đợi kích thước cố định lưu trong mảng với chỉ số quay vòng. deque(maxlen=n) loại bỏ phần tử cũ nhất khi đầy.
• Hàng đợi an toàn luồng: queue.Queue cho thread và asyncio.Queue cho coroutine sẽ chặn (block) khi chờ phần tử.
• Hàng đợi xây từ hai ngăn xếp: push vào ngăn xếp vào, và khi ngăn xếp ra rỗng thì chuyển hết sang. Mỗi phần tử chỉ được chuyển một lần, nên các thao tác là O(1) khấu hao.