Khi nào bạn nên dùng stack thay vì queue? Cho ví dụ thực tế.

Question

Accepted Answer

Cả hai đều là ADT tuyến tính với hai đầu O(1), nhưng **thứ tự lấy ra** thì ngược nhau: một **stack là LIFO** (gần đây nhất trước), một **queue là FIFO** (cũ nhất trước). Hãy khớp cấu trúc với thứ tự mà bài toán của bạn yêu cầu.

## Khác biệt cốt lõi

```text
Stack (LIFO):  push 1,2,3  -> thứ tự pop 3,2,1
Queue (FIFO):  enq  1,2,3  -> thứ tự deq 1,2,3
```

## Ví dụ thực tế

| Dùng STACK khi... | Dùng QUEUE khi... |
|---|---|
| Undo/redo (hành động mới nhất trước) | Lập lịch công việc (thứ tự đến) |
| Nút back trình duyệt | Print spooler / hàng đợi tác vụ |
| Lời gọi hàm/đệ quy | BFS / đường đi ngắn nhất trên graph |
| Khớp ngoặc, phân tích cú pháp | Đệm tin nhắn giữa các dịch vụ |
| DFS (khám phá sâu nhất trước) | Giới hạn tốc độ / xử lý request |

## Đối chiếu code

```python
# DFS dùng một stack: khám phá nhánh mới nhất trước
stack = [start]
while stack:
    node = stack.pop()        # LIFO -> đi sâu
    for nb in graph[node]: stack.append(nb)

# BFS dùng một queue: khám phá gần nhất trước
from collections import deque
q = deque([start])
while q:
    node = q.popleft()        # FIFO -> đi theo từng tầng
    for nb in graph[node]: q.append(nb)
```

## Tại sao điều này quan trọng

Lựa chọn LIFO-so-với-FIFO thay đổi trực tiếp hành vi thuật toán: *cùng một* phép duyệt graph trở thành DFS với một stack hoặc BFS với một queue.

Nhận ra liệu bài toán của bạn cần "gần đây nhất" hay "cũ nhất trước" lập tức chỉ cho bạn cấu trúc đúng.

Undo/redo (hành động mới nhất trước)	Lập lịch công việc (thứ tự đến)
Nút back trình duyệt	Print spooler / hàng đợi tác vụ
Lời gọi hàm/đệ quy	BFS / đường đi ngắn nhất trên graph
Khớp ngoặc, phân tích cú pháp	Đệm tin nhắn giữa các dịch vụ
DFS (khám phá sâu nhất trước)	Giới hạn tốc độ / xử lý request