Giáo án chuyên đề Khoa học máy tính 12 kết nối Bài 4: Kiểu dữ liệu hàng đợi

HOẠT ĐỘNG CỦA GV - HS

DỰ KIẾN SẢN PHẨM

Bước 1: GV chuyển giao nhiệm vụ học tập

- GV yêu cầu HS thảo luận theo nhóm 2 – 3 HS và trả lời các câu hỏ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?

- GV tổng hợp cách dùng kiểu dữ liệu danh sách (list) của Python để biểu diễn hàng đợi.

- GV yêu cầu HS vận dụng kiến thức vừa tìm hiểu, trả lời câu hỏi Củng cố tr.17 SGK:

Câu 1. Khi hàng đợi được cài đặt bằng danh sách (kiểu list của Python), em hãy cho biết cách tính số phần tử của hàng đợi này.

Câu 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,10); dequeue(Q); enqueue (Q,6); dequeue(Q); enqueue(Q,9); enqueue(Q,1).  

Bước 2: HS thực hiện nhiệm vụ học tập

- HS tìm hiểu nội dung mục 1 SGK tr.16 – 17 và thảo luận trả lời các câu hỏi mà GV đưa ra.

- GV quan sát và trợ giúp HS (nếu cần thiết).

Bước 3: Báo cáo kết quả hoạt động và thảo luận

- Đại diện các nhóm HS trả lời.

- Các nhóm khác đưa ra ý kiến nhận xét.

Hướng dẫn trả lời câu hỏi Củng cố SGK tr.17:

Câu 1. Số phần tử của hàng đợi Q chính là giá trị len(Q).

Câu 2. Phần tử đầu của hàng đợi Q là 6, phần tử đuôi là 1.

Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập

- Từ kết quả thảo luận của nhóm, GV nhận xét, đánh giá quá trình HS thực hiện nhiệm vụ.

- GV chính xác hoá lại các nội dung kiến thức.

- GV chốt kiến thức: 

• Hàng đợi được cài đặt bằng mảng một chiều (danh sách thuộc kiểu list của Python). 

• Phép toán enqueue(Q,x) thêm x vào cuối mảng. 

• Phép toán dequeue(Q) lấy ra phần tử cuối của mảng. 

• Đầu (front) là phần tử đầu tiên và đuôi (rear) là phần tử cuối của mảng.

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 CỦA GV - HS

DỰ KIẾN SẢN PHẨM

Bước 1: GV chuyển giao nhiệm vụ học tập

- GV yêu cầu HS đọc Hoạt động 2 - Tìm hiểu các hàm của kiểu dữ liệu hàng đợi SGK tr.17:

Đọ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).

- GV chia lớp thành các nhóm 2 – 3 HS, mỗi nhóm thực hiện viết các hàm cơ bản của hàng đợi ra giấy, sau đó GV cùng HS phân tích đúng sai và rút ra kết luận.

- GV yêu cầu HS vận dụng kiến thức vừa tìm hiểu, trả lời câu hỏi Củng cố tr.19 SGK:

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

Câu 2. Em hãy nêu sự giống nhau và khác nhau giữa các hàm của ngăn xếp và hàng đợi được cài đặt bằng danh sách (kiểu list của Python).

Bước 2: HS thực hiện nhiệm vụ học tập

- HS tìm hiểu nội dung mục 2 SGK tr.17 – 19 và thảo luận theo nhóm thực hiện nhiệm vụ.

- GV quan sát và trợ giúp HS (nếu cần thiết).

Bước 3: Báo cáo kết quả hoạt động và thảo luận

- GV mời 5 HS lên bảng, mỗi HS viết một hàm.

Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập

- GV nhận xét và gọi một số HS đứng tại vị trí giải thích ý nghĩa của từng câu lệnh trong các hàm trên bảng sau đó chạy chương trình cho HS quan sát kết quả.

- GV chính xác hoá lại các nội dung kiến thức.

- GV chốt kiến thức: 

• Hàng đợi có thể được cài đặt bằng danh sách (kiểu list của Python). 

• Các hàm cơ bản trên hàng đợi Q gồm Queue(), isEmptyQueue(Q), enqueue(Q,x), dequeue(Q) và front(Q).

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:

Một số ví dụ thiết lập và làm việc với hàng đợi:

Ví dụ 1. Các lệnh sau tạo hàng đợi rỗng và bổ sung 5 vào hàng đợi:

Ví dụ 2. Đoạn mã sau đây thêm các số lớn hơn hoặc bằng 0 vào hàng đợi Q đến khi gặp số âm:

Hướng dẫn trả lời câu hỏi Củng cố SGK tr.19:

Câu 1. Nếu hàng đợi Q được biểu diễn bằng mảng (list) trong Python thì:

- Chỉ số phần tử đầu hàng đợi: 0; Chỉ số phần tử cuối hàng đợi: len(Q) – 1.

- So sánh với ngăn xếp được biểu diễn bằng mảng (list) của Python ta có:

+ Chỉ số đầu (front) của hàng đợi chính là chỉ số đáy (bottom) của ngăn xếp.

+ Chỉ số đuôi (back, rear, tail) của hàng đợi là chỉ số đỉnh (top) của ngăn xếp.

Câu 2. Bảng sau mô tả sự giống nhau và khác nhau giữa các hàm cơ bản của ngăn xếp và hàng đợi khi các kiểu dữ liệu này được biểu diễn bằng danh sách (list) của Python.