1. BIỂU DIỄN HÀNG ĐỢI BẰNG MẢNG MỘT CHIỀU

Hoạt động 1

Quan sát, trao đổi, thảo luận để tìm hiểu cách biểu diễn hàng đợi bằng mảng một chiều. Em hãy trả lời các câu hỏi sau:

1. Có thể biểu diễn hàng đợi bằng mảng một chiều được không? 

2. Cần có các biến nào để thực hiện các phép toán thêm vào và lấy ra?

Câu hỏi 2: Ban đầu, hàng đợi là rỗng. Em hãy cho biết giá trị của phần tử ở đầu (front) và đuôi (rear) sau khi thực hiện tuần tự các phép toán enqueue(Q,2); enqueue(Q,19); dequeue(Q), enaqueue (Q, 6); dequeue(Q); enqueue(Q, 9); enqueue(Q,1).

Câu hỏi 1: Khi hàng đợi Q được cài đặt bằng danh sách (kiểu list của Python), em hãy cho biết chỉ số của các phản tử tại đầu (front) và đuôi (rear). So sánh các chỉ số này với chỉ số của các phần tử tại đáy (bottom) và đỉnh (top) của ngăn xếp (cũng được cài đặt bằng danh sách). 

Luyện tập

1.

Sửa lại hàm dequeue(Q) và front(Q) trong chương trình trên như sau: Nếu hàng đợi rỗng thì thông báo: "Hàng đợi rỗng không thể thực hiện được lệnh".

Vận dụng

1. Hãy giải thích vì sao lệnh dequeue(Q) lại có độ phức tạp thời gian là O(n), với n là độ dài của hàng đợi hiện thời.