Queues · Hàng đợi (Queues)
A queue is FIFO
- A queue is First In, First Out (FIFO).
- The first item you add is the first one to leave.
- Think of a line of people: the person at the front is served first.
Hàng đợi遵循 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 and dequeue with a list
- We can build a queue from a Python list.
- enqueue =
queue.append(x)— add to the back. - dequeue =
queue.pop(0)— remove and return the front.
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 and empty
- Look at the front without removing it:
queue[0]. - A queue is empty when
len(queue) == 0. - Check it is not empty before you dequeue.
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?
A note on speed
pop(0)has to shift every other item forward by one place.- For a big queue that is slow, so it uses more time.
- Real systems use a circular buffer with front and rear pointers instead.
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.
In Cambridge pseudocode
- The exam builds a queue from an array with a
frontand arearpointer.
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
Common mistakes
- A queue is first-in, first-out: join the back, leave from the front.
- Check it is not empty before you dequeue.
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.
Now you try
- Use a list as your queue (
appendto enqueue,pop(0)to dequeue). - Press Check answer to test your code.
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.
A queue is FIFO · Hàng đợi hoạt động theo FIFO
A queue adds at the back and removes at the front — first in, first out. · Hàng đợi thêm ở phía sau và lấy ở phía trước — đầu vào, đầu ra.
Start with an empty queue. Enqueue "a", then "b", then "c". Then dequeue once, storing the removed value in first. (first should be "a" and the queue should be ["b", "c"].) · 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"].)
Click Run to see the output here. · Nhấn Chạy để xem kết quả ở đây.
Enqueue 1, 2, 3 onto a queue, then dequeue them all into result. Unlike a stack, a queue keeps the same order. (result should be [1, 2, 3].) · 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].)
Click Run to see the output here. · Nhấn Chạy để xem kết quả ở đây.
Write serve(queue) that dequeues the front item: remove it from the list and return it. The caller's list should get shorter. · 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.
Click Run to see the output here. · Nhấn Chạy để xem kết quả ở đây.
Write front(queue) that returns the front item without removing it, so the queue is unchanged. If the queue is empty, return None. · 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.
Click Run to see the output here. · Nhấn Chạy để xem kết quả ở đây.