Thuật toán Python

Cấu trúc dữ liệu hàng đợi (queue) trong Python với deque

Vào trước, ra trước: phục vụ theo thứ tự đến với collections.deque, nhanh ở cả hai đầu.

Trung cấp
Đọc trong 2 phút
1 ví dụ chạy được

Bạn sẽ học được gì

append() và popleft() trên deque
Vì sao list.pop(0) chậm
Hàng đợi được dùng ở đâu

Chạy trong trình biên dịch Python →

deque(["first", "second", "third"])

firstđầu

second

thirdcuối

↑ popleft() phục vụ "first"

Vào ở cuối, ra ở đầu

Queue (hàng đợi) hoạt động theo nguyên tắc vào trước, ra trước (FIFO), giống như hàng người xếp hàng thanh toán: ai đến trước được phục vụ trước. Hàng đợi thường được dùng để lập lịch xử lý công việc và trong thuật toán tìm kiếm theo chiều rộng (BFS).

Những điểm quan trọng

queue.append(x) thêm vào cuối hàng.
queue.popleft() lấy ra từ đầu hàng trong O(1).
list.pop(0) phải dời mọi phần tử, nên mất O(n).
Hàng đợi dùng để lập lịch công việc và tìm kiếm theo chiều rộng.

Khi nào nên sử dụng?

Rèn luyện tư duy giải quyết vấn đề và hiểu cách thuật toán hoạt động qua từng bước.
Chọn được cách giải phù hợp khi cần xử lý nhiều dữ liệu hoặc cần chương trình chạy nhanh hơn.
Chuẩn bị cho các kỳ thi, bài tập và phỏng vấn lập trình.

Xem cách hoạt động

Enqueue và dequeue để thấy các phần tử rời đi đúng theo thứ tự chúng đến.

Code ví dụ

Chạy code →

main.py

from collections import deque

queue = deque(["first", "second"])
queue.append("third")

print("served:", queue.popleft())
print("waiting:", list(queue))

Lấy nút Run cho ví dụ này

Kết quả khi chạy

served: first
waiting: ['second', 'third']

Giải thích code

deque cho phép thêm phần tử vào bên phải bằng append() và lấy ra từ bên trái bằng popleft(), cả hai đều mất O(1). Nếu dùng list thông thường, việc xóa phần tử đầu tiên mất O(n) vì mọi phần tử phía sau đều phải dịch lên, nên deque là lựa chọn phù hợp hơn cho hàng đợi.

Thay đổi giá trị và chạy chương trình bằng trình chạy Python online của CodeUtility mà không cần cài Python.

Bài tập mở rộng

Hãy thử chỉnh sửa code theo các gợi ý dưới đây. Tự thay đổi và quan sát kết quả sẽ giúp bạn hiểu bài sâu hơn nhiều so với chỉ đọc code.

Thử với danh sách rỗng, danh sách chỉ có một phần tử hoặc có giá trị trùng lặp.
In ra trạng thái sau mỗi bước để quan sát thuật toán hoạt động.
Đo thời gian chạy với 100, 1.000 và 10.000 phần tử, rồi so sánh với một cách giải khác.

Chạy trong trình biên dịch Python →

Luyện tập với thử thách

Áp dụng kiến thức của bài học này để giải một bài toán thực tế. Mỗi thử thách chạy ngay trên trình duyệt, có kiểm thử tức thì và AI nhận xét.

Tất cả thử thách