BÀI 4: KIỂU DỮ LIỆU HÀNG ĐỢI

Chào mừng các em đến với bài học ngày hôm nay!

A. KHỞI ĐỘNG

Từ các bài học trước, em đã biết viết chương trình đơn giản để sử dụng các hàm cơ bản của ngăn xếp được cài đặt bằng danh sách (kiểu list của Python). Em hãy trả lời các câu hỏi sau:

a) Có thể cài đặt hàng đợi bằng mảng một chiều tương tự như ngăn xếp được không?

b) Khi cài đặt hàng đợi bằng mảng một chiều, cần có thông tin nào để thực hiện phép toán thêm vào và lấy ra?

B. HÌNH THÀNH KIẾN THỨC

Hoạt động 1. Dùng kiểu dữ liệu mảng để biểu diễn hàng đợi

Theo em, hàng đợi được cài đặt bằng một danh sách (kiểu list của Python) có những trường hợp nào?

Dự kiến sản phẩm:

1. Biểu diễn hàng đợi bằng mảng một chiều

Hàng đợi được cài đặt bằng một danh sách (kiểu list của Python) có các trường hợp sau:

a) Khởi tạo hàng đợi Q là rỗng; nghĩa là Q là danh sách rỗng.

Hình 4.1a. Hàng đợi rỗng

b) Phép toán enqueue(Q,x):

- Dùng để thêm x vào đuôi (back) của hàng đợi Q, nghĩa là thêm x vào cuối danh sách.

- Đầu (front) của hàng đợi là phần tử đầu tiên và đuôi (back, rear, tail) của hàng đợi là phần tử cuối của danh sách.

Ví dụ: Hình 4.1b cho thấy quá trình thêm các giá trị 5, 2, –4, 10, –8, 11 vào hàng đợi.

Hình 4.1b. Hàng đợi với phép toán
thêm vào

c) Phép toán dequeue(Q) dùng để lấy ra và trả về phần tử ở đầu (front) của hàng đợi Q, nghĩa là lấy ra phần tử đầu tiên của danh sách.

Ví dụ: Hình 4.1c cho thấy hàng đợi sau khi lấy ra một phần tử.

Hình 4.1c. Hàng đợi với phép toán lấy ra

Có thể biểu diễn hàng đợi bằng list của Python:

Lưu ý: Dùng kiểu dữ liệu danh sách (list) của Python để biểu diễn hàng đợi chỉ là một cách và không phải là cách duy nhất. Có nhiều cách biểu diễn khác nhưng trong phạm vi Bài 4 chỉ học cách này.

Hoạt động 2. Tìm hiểu các hàm của kiểu dữ liệu hàng đợi

Đọc, trao đổi để biết các hàm cơ bản của hàng đợi được cài đặt bằng danh sách (kiểu list của Python).

Dự kiến sản phẩm:

2. Tìm hiểu các hàm của kiểu dữ liệu hàng đợi

Một số hàm cơ bản của hàng đợi được cài đặt bằng danh sách (kiểu list của Python):

* Đầu (front) của hàng đợi Q là phần tử đầu tiên của danh sách, nghĩa là biến front = 0. Đuôi (rear) của hàng đợi Q là phần tử cuối của danh sách, nghĩa là biến rear = len(Q)-1. Do đó, không cần các biến front và rear.

a) Hàm Queue() dùng để tạo hàng đợi rỗng, hàm trả về danh sách rỗng:

Lệnh tạo hàng đợi Q rỗng (Q là danh sách rỗng):

b) Hàm enqueue(Q,x) dùng để thêm x vào đuôi (rear) của hàng đợi Q, nghĩa là thêm x vào cuối danh sách Q bằng hàm append():

Lệnh gọi hàm:

c) Hàm isEmptyQueue(Q):

- Trả về True nếu hàng đợi Q rỗng.

- Ngược lại trả về False.

d) Hàm dequeue(Q):

- Lấy ra phần tử tại đầu (front) của hàng đợi Q (phần tử đầu tiên của danh sách Q) và trả về phần tử này.

- Nếu Q rỗng thì hàm báo lỗi ngoại lệ ValueError và dừng chương trình.

Lệnh gọi hàm:

e) Hàm front(Q):

- Trả về phần tử tại đầu (front) của hàng đợi Q (phần tử đầu tiên của danh sách) và phần tử này vẫn còn trong hàng đợi Q (hàng đợi Q không bị thay đổi).

- Nếu Q rỗng thì hàm báo lỗi ngoại lệ ValueError và dừng chương trình.

Lệnh gọi hàm:

C. LUYỆN TẬP

Khoanh tròn vào chữ cái đứng trước câu trả lời đúng nhất:

Câu 1. Biến rear của hàng đợi Q có chỉ số là

A. 0.

B. 1.

C. len(Q) – 1.

D. len(Q).

Câu 2. Lệnh gọi hàm thêm x vào đuôi của hàng đợi Q là

A. Q.append(x).

B. def enqueue(Q,x).

C. dequeue(Q,x).

D. enqueue(Q,x).

Câu 3. Hàm front(Q) có độ phức tạp thời gian là

A. O(1).

B. O(n).

C. O(n²).

D. O(n!).

Câu 4. Hàm dequeue(Q) được dùng để làm gì?

A. Lấy ra phần tử tại đuôi (rear) của hàng đợi Q và trả về phần tử này.

B. Trả về phần tử tại đầu (font) của hàng đợi Q và phần tử này vẫn còn trong hàng đợi Q.

C. Lấy ra phần tử tại đầu (font) của hàng đợi Q và trả về phần tử này.

D. Trả về phần tử tại đầu (rear) của hàng đợi Q và phần tử này vẫn còn trong hàng đợi Q.

Câu 5. Giá trị của phần tử ở đuôi (rear) sau khi thực hiện tuần tự các phép toán enqueue(Q,1); enqueue(Q,2); enqueue (Q,7); dequeue(Q); dequeue(Q); enqueue(Q,5); dequeue(Q); enqueue(Q,9) là

A. 5.

B. 9.

C. 1.

D. 7.

Gợi ý trả lời:

D. VẬN DỤNG

Câu 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.

Câu 2. Cho trước mảng T gồm N phần tử T[0], T[1], ..., T[N-1]. Hãy viết hàm thiết lập hàng đợi và các thao tác cơ bản với hàng đợi từ mảng T.

Hướng dẫn về nhà:

- Xem lại kiến thức đã học ở Bài 4.

- Xem trước nội dung Bài 5: Thực hành kiểu dữ liệu ngăn xếp và hàng đợi.

Xin trận trọng cảm ơn sự quan tâm theo dõi của các em, hẹn gặp lại!