Chuyên đề Tin 12 CTST Bài 1.1. Hàng đợi

Khi làm thủ tục tại các cơ quan hành chính nhà nước, em sẽ gặp các hệ thống xếp hàng tự động (Hình 1). Theo em, các hệ thống này hoạt động theo nguyên tắc nào?

Cho Hình 4, biểu diễn một hàng đợi, hãy cho biết:

a) Phần tử đầu hàng đợi, phần tử cuối hàng đợi.

b) Sau khi lấy ra một phần tử, thì phần tử đầu hàng đợi là phần tử nào?

c) Sau khi thêm vào phần tử k vào thì phần tử cuối hàng đợi là phần tử nào?

Cho hàng đợi rỗng, hãy vẽ hình minh hoạ từng bước thực hiện các thao tác sau: enqueue (1), enqueue (3), enqueue (5), dequeue (), dequeue (), enqueue (7).

Các thông tin cần thiết để biểu diễn hàng đợi bằng mảng 1 chiều là gì?

Với hàng đợi ở Hình 5, hãy vẽ hình khi thực hiện liên tục các thao tác: thêm vào 0, lấy ra, lấy ra

Tại sao không cần sử dụng các chỉ số front, rear khi dùng kiểu list để biểu diễn hàng đợi trong Python?

Theo em, có cách nào kiểm tra hàng đợi queue là rỗng mà không dùng hàm len (queue)?

Trong Python, khi sử dụng kiểu list để biểu diễn hàng đợi. Hãy cho biết:

a) Chỉ số của phần tử đầu.

b) Chỉ số của phần tử cuối.

Theo em, thứ tự thực hiện phép toán enqueue với các giá trị thích hợp để kết quả là một hàng đợi trong Hình 5 là những bước nào?

Các phần tử trong hàng đợi biểu diễn bằng kiểu list trong Python có thể thuộc kiểu chuỗi hay không? Nếu có, sử dụng các hàm initQueue(), enqueue() để tạo hàng đợi có các phần tử như sau:

Sau đó sử dụng các hàm enqueue(), dequeue() để hang đợi có kết quả là:

Theo em, có thể dùng danh sách liên kết để biểu diễn hàng đợi hay không?

Tạo tệp queue py chứa các hàm enqueue(), dequeue(), front(), rear(), isEmptyQueue() của hàng đợi. Sau đó:

- Khởi tạo hàng đọi rồng han trởi sáng tạo

- Thực hiện các hàm enqueue() với giá trị thích hợp để hàng đợi có kết quả như Hình 6a.

- Thực hiện các hàm enqueue(), dequeue() với các giá trị thích hợp để hàng đợi có kết quả như Hình 6b.