Cài đặt hàng đợi bằng danh sách Python

Đầu ở chỉ số 0, cuối ở chỉ số len(Q)-1

Lưu hàng đợi bằng list theo thứ tự đầu đến cuối. `append(x)` thêm cuối; `pop(0)` lấy và loại bỏ phần tử đầu. `front(Q)` chỉ xem đầu, không xóa. ```python def Queue(): return [] def isEmptyQueue(Q): return len(Q) == 0 def enqueue(Q, x): Q.append(x) def dequeue(Q): if isEmptyQueue(Q): raise ValueError("Hàng đợi rỗng") return Q.pop(0) def front(Q): if isEmptyQueue(Q): raise ValueError("Hàng đợi rỗng") return Q[0] ```

Xen kẽ thêm và lấy

Với Q ban đầu rỗng: |Lệnh|Q sau lệnh|Giá trị trả về nếu có| |---|---|---| |enqueue(Q,3); enqueue(Q,7)|[3, 7]|—| |dequeue(Q)|[7]|3| |enqueue(Q,2)|[7, 2]|—| |front(Q)|[7, 2]|7| |dequeue(Q)|[2]|7| FIFO dựa trên thứ tự thêm, không dựa trên giá trị lớn hay nhỏ. Số 2 vẫn chờ sau 7 vì được thêm sau. Trong cách cài đặt này, `pop(0)` làm các phần tử phía sau dịch vị trí nên chi phí tăng theo độ dài hàng đợi, thường viết O(n). Xem phần tử đầu là O(1); append có chi phí trung bình phân bổ O(1). Vì vậy không kết luận mọi thao tác hàng đợi dùng list đều O(1). Python có collections.deque phù hợp hơn khi cần lấy đầu thường xuyên; ở đây dùng list để theo cách biểu diễn của SGK.

Bài luyện

Lệnh nào lấy đúng phần tử đầu và loại bỏ nó trong cách cài đặt này?

AQ[-1]BQ.pop()CQ[0]DQ.pop(0)

Bài luyện

Theo bảng ví dụ, sau lần dequeue cuối, Q còn gì?

A[7, 2].B[2].C[7].D[].

Bài luyện

Vì sao dequeue dùng list.pop(0) thường có chi phí O(n)?

AVì phải dồn các phần tử phía sau về trước.BVì luôn sắp xếp tăng dần trước khi lấy.CVì phải đảo hàng đợi trước mọi thao tác.DVì front cũng xóa toàn bộ hàng đợi.