🎫 Hàng đợi (Queue)

Xếp hàng mua vé: ai đến trước được phục vụ trước, người mới đến phải nối vào cuối hàng chờ tới lượt. Đó là quy tắc FIFO - First In, First Out (vào trước, ra trước) mà hàng đợi (queue) mô phỏng: phần tử được thêm vào một đầu (rear - cuối hàng) và lấy ra ở đầu kia (front - đầu hàng).

Hai thao tác nền tảng:

enqueue (hoặc push) - thêm phần tử vào cuối hàng.
dequeue (hoặc pop) - lấy và xóa phần tử ở đầu hàng.

So với stack (LIFO, thao tác cùng một đầu), queue thao tác ở hai đầu khác nhau - đây là điểm khác biệt cốt lõi giữa hai cấu trúc.

Cài đặt

Nếu cài đặt queue bằng list thường của Python, dequeue (xóa phần tử đầu) sẽ tốn O(n) vì mọi phần tử phía sau phải dịch chuyển lên một vị trí. Cách tránh: dùng collections.deque - một cấu trúc được cài đặt sẵn để thêm/xóa ở cả hai đầu đều O(1):

from collections import deque

queue = deque()
queue.append(1)        # enqueue: thêm vào cuối
queue.append(3)
queue.append(2)

front = queue[0]         # peek: xem đầu hàng, O(1)
val = queue.popleft()     # dequeue: lấy và xóa đầu hàng, O(1)

Ứng dụng: duyệt theo từng lớp với BFS

Ứng dụng quan trọng nhất của queue là thuật toán duyệt theo chiều rộng (BFS - Breadth-First Search): khám phá đồ thị hoặc cây theo từng “lớp” lan ra từ điểm xuất phát, giống như sóng nước lan tỏa từ tâm.

Ý tưởng: đưa điểm xuất phát vào queue; lặp lại việc lấy một điểm ra khỏi đầu hàng, rồi đưa tất cả “hàng xóm” chưa thăm của nó vào cuối hàng. Vì queue là FIFO, những điểm được thêm vào trước (tức gần điểm xuất phát hơn) luôn được xử lý trước những điểm thêm vào sau - đảm bảo thứ tự duyệt đúng là lan dần theo từng lớp.

from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    order = []

    while queue:
        node = queue.popleft()      # lấy điểm gần nhất chưa xử lý
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)   # đưa vào cuối hàng, chờ đến lượt
    return order

Độ phức tạp: O(V + E) với V là số đỉnh, E là số cạnh - mỗi đỉnh và mỗi cạnh chỉ được xét đúng một lần. Xem chi tiết hơn về BFS/DFS ở trang Duyệt đồ thị.

Deque - hàng đợi hai đầu

Deque (double-ended queue) là bản mở rộng của queue: cho phép thêm và xóa ở cả hai đầu, không chỉ riêng đầu hoặc riêng cuối.

from collections import deque

dq = deque()
dq.append(2)         # thêm vào cuối
dq.appendleft(1)      # thêm vào đầu
dq.pop()               # xóa cuối
dq.popleft()            # xóa đầu

Deque hữu ích khi bài toán cần cả hai chiều thao tác - ví dụ cài đặt một “hàng đợi vừa có thể chèn ưu tiên ở đầu, vừa nhận thêm ở cuối”, hoặc dùng làm nền cho thuật toán sliding window tối ưu (giữ trong deque các ứng viên còn “có ích”, loại bỏ từ cả hai đầu tùy điều kiện).

Stack vs Queue

	Stack (LIFO)	Queue (FIFO)
Thêm/lấy	Cùng một đầu (đỉnh)	Hai đầu khác nhau (đầu/cuối)
Ví dụ đời thực	Chồng đĩa, nút Undo	Hàng chờ mua vé
Ứng dụng thuật toán	DFS, call stack	BFS