Queue là gì và nó được dùng ở đâu?

Question

Accepted Answer

**Queue** (hàng đợi) là một collection **FIFO** (First-In, First-Out — vào trước, ra trước): phần tử được thêm vào **cuối (back)** và lấy ra từ **đầu (front)**, giống như một hàng người xếp hàng. ## Các thao tác ```text enqueue(1) enqueue(2) enqueue(3) dequeue()->1 front ->[1][2][3]<- back front ->[2][3]<- back ``` ## Ví dụ ```python from collections import deque queue = deque() queue.append('a') # enqueue (cuối) queue.append('b') first = queue.popleft() # dequeue (đầu) -> 'a' ``` Một `list` thuần của Python khiến `pop(0)` trở thành thao tác **O(n)**, vì vậy hãy dùng `deque` để có **O(1)** ở cả hai đầu. | Thao tác | Thời gian (deque) | |---|---| | enqueue | O(1) | | dequeue | O(1) | | peek front | O(1) | ## Các ứng dụng phổ biến - **Lập lịch tác vụ / công việc** — xử lý công việc theo thứ tự đến. - **Tìm kiếm theo chiều rộng (BFS)** — duyệt các node theo từng tầng. - **Đệm (buffering)** — pipeline producer/consumer, print spooler, hàng đợi request. ## Tại sao điều này quan trọng Queue đảm bảo tính công bằng và thứ tự, điều này rất quan trọng cho bộ lập lịch, hệ thống nhắn tin, và BFS. Bất cứ khi nào công việc phải được xử lý "theo thứ tự nó đến," queue là lựa chọn tự nhiên.