Hàng đợi (Queues)
Một hàng đợi tuân theo nguyên tắc FIFO
- Một queue (hàng đợi) là First In, First Out (Vào trước, Ra trước - FIFO).
- Mục đầu tiên bạn thêm vào là mục đầu tiên rời đi.
- Hãy tưởng tượng hàng người: người ở đầu hàng được phục vụ trước.
enqueue và dequeue với danh sách
- Chúng ta có thể xây dựng hàng đợi từ một danh sách Python.
- enqueue =
queue.append(x)— thêm vào cuối. - dequeue =
queue.pop(0)— xóa và trả về đầu.
queue = []
queue.append("first")
queue.append("second")
print(queue.pop(0))
print(queue)
front và empty
- Nhìn vào đầu mà không xóa nó:
queue[0]. - Hàng đợi empty (trống) khi
len(queue) == 0. - Kiểm tra nó không rỗng trước khi dequeue.
queue = [10, 20, 30]
print(queue[0]) # the front
print(len(queue) == 0) # is it empty?
Lưu ý về tốc độ
pop(0)phải di chuyển mỗi phần tử kế tiếp về phía trước một vị trí.- Đối với hàng đợi lớn thì chậm, vì vậy nó tốn nhiều thời gian hơn.
- Các hệ thống thực tế sử dụng circular buffer (vòng đệm tròn) với con trỏ front và rear thay vì dùng.
Trong pseudocode Cambridge
- Bài thi xây dựng hàng đợi từ mảng với một con trỏ
frontvà một con trỏrear.
DECLARE queue : ARRAY[1:10] OF INTEGER
DECLARE front, rear : INTEGER
front ← 1
rear ← 0 // empty
// enqueue value
rear ← rear + 1
queue[rear] ← value
// dequeue into value
value ← queue[front]
front ← front + 1
Lỗi thường gặp
- Hàng đợi là vào trước, ra trước: vào cuối, ra từ đầu.
- Kiểm tra nó không rỗng trước khi dequeue.
Bây giờ bạn thử
- Dùng danh sách làm hàng đợi của bạn (
appendđể enqueue,pop(0)để dequeue). - Nhấn Check answer (Kiểm tra câu trả lời) để thử mã của bạn.
Hàng đợi hoạt động theo FIFO
Hàng đợi thêm ở phía sau và lấy ở phía trước — đầu vào, đầu ra.
Độ khó 4/5 · 280 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
Bắt đầu với hàng đợi rỗng. Thêm vào queue "a", sau đó "b", rồi "c". Sau đó lấy khỏi queue một lần, lưu giá trị bị loại bỏ vào first. (first nên là "a" và hàng đợi nên là ["b", "c"].)
Nhấn Chạy để xem kết quả ở đây.
Độ khó 4/5 · 280 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
Thêm vào queue 1, 2, 3, sau đó lấy tất cả vào result. Khác với ngăn xếp, hàng đợi giữ nguyên thứ tự giống nhau. (result nên là [1, 2, 3].)
Nhấn Chạy để xem kết quả ở đây.
Độ khó 4/5 · 280 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
Viết serve(queue) lấy khỏi queue phần tử ở phía trước: loại bỏ nó khỏi danh sách và trả về nó. Danh sách của người gọi sẽ ngắn đi.
Nhấn Chạy để xem kết quả ở đây.
Độ khó 4/5 · 280 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
Viết front(queue) trả về phần tử ở phía trước không loại bỏ nó, để hàng đợi không thay đổi. Nếu hàng đợi rỗng, trả về None.
Nhấn Chạy để xem kết quả ở đây.