Giáo án điện tử chuyên đề Khoa học máy tính 12 cánh diều Bài 1: 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!

Hình 1. Một số ví dụ về nhiều máy tính cùng kết nối đến một máy in

Một phòng thực hành có 50 máy tính nối mạng với một máy in duy nhất (Hình 1). Có nhiều người dùng trong phòng đều có nhu cầu in tệp dữ liệu của họ. Theo em, các tệp dữ liệu đó sẽ được in theo thứ tự thế nào và hệ thống phải sắp xếp các tệp dữ liệu này như thế nào để làm được điều đó?

KHỞI ĐỘNG

Hệ thống hàng đợi

Cơ chế FIFO

• Tài liệu nào đưa đến trước in trước.
• Tài liệu nào đưa đến sau in sau.

Mục đích

• Đảm bảo tính công bằng khi in tài liệu

Phần mềm ứng dụng

• CUPS (Common Unix Printing System)

CHUYÊN ĐỀ 1:

TÌM HIỂU MỘT VÀI KIỂU DỮ LIỆU TUYẾN TÍNH

BÀI 1.

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

NỘI DUNG BÀI HỌC

Một số ví dụ về hàng đợi và cơ chế hoạt động

1

Kiểu dữ liệu hàng đợi và các phép toán cơ bản trên hàng đợi

2

Cài đặt hàng đợi

3

Thực hành

4

PHẦN 1. MỘT SỐ VÍ DỤ VỀ HÀNG ĐỢI VÀ CƠ CHẾ HOẠT ĐỘNG

Tìm hiểu thông tin mục 1 trong SGK tr.6 và trả lời câu hỏi:

Xếp hàng chờ thanh toán trong siêu thị

• Nêu các ví dụ về xếp hàng đợi đến lượt?
• Mục đích của việc xếp hàng đợi là gì?
• Cơ chế hoạt động của hàng đợi tuân theo quy tắc nào?
• Nêu một số ứng dụng của hàng đợi trong Tin học?

MỘT SỐ VÍ DỤ

Xếp hàng đợi

thanh toán ở siêu thị

Xếp hàng đợi

mua vé xem phim

Xếp hàng đợi để bác sĩ thăm khám

Hình 2. Ví dụ xếp hàng đợi thanh toán ở siêu thị

Mục đích: tạo ra hàng đợi để đảm bảo tính công bằng.

Cơ chế: vào trước ra trước – FIFO

Ứng dụng trong tin học:

Tin nhắn trên mạng được gửi cho người nhận không có kết nối Internet, nhờ cơ chế của hàng đợi, tin nhắn được chuyển đi đúng thứ tự.

PHẦN 2. KIỂU DỮ LIỆU HÀNG ĐỢI VÀ CÁC PHÉP TOÁN CƠ BẢN TRÊN HÀNG ĐỢI

Em hãy đọc thông tin và trả lời câu hỏi sau đây:

Hàng đợi thuộc kiểu dữ liệu nào?

Các phép toán cơ bản trên hàng đợi gồm những phép toán nào?

10

3

5

6

-7

12

4

9

Lấy ra

Thêm vào

(dequeue)

(enqueue)

Đầu (Front)

Cuối (Back)

• Hàng đợi thuộc kiểu dữ liệu tuyến tính.

Phép toán lấy ra: dequeue

Thực hiện ở đầu front

Phép toán thêm vào: enqueue

Thực hiện ở đầu back

• Khi dùng mảng một chiều để lưu các phần tử của hàng đợi, ta sẽ lưu như sau:

Quan sát Hình 3a và cho biết mỗi số nguyên được lưu như thế nào?

Hình 3a

• Các số trong hàng đợi được lưu ở hàng đợi Q như sau:

Số 10 lưu ở Q[Front]

Front = 0

Số 3 lưu ở

Q[Front + 1]

...

Số 9 lưu ở Q[Back]

Back = 7

Nếu tiến hành thực hiện một thao tác lấy ra thì số nào sẽ được đưa ra khỏi hàng đợi? Vì sao? Hàng đợi mới thu được sẽ bao gồm những phần tử nào và chỉ số của các phần tử này trong mảng thay đổi như thế nào?

10

3

5

6

-7

12

4

9

Lấy ra

Thêm vào

(dequeue)

(enqueue)

Đầu (Front)

Cuối (Back)

10

• Nếu tiến hành lấy ra, số 10 sẽ bị lấy đầu tiên, vì đứng đầu hàng đợi:

• Sau khi lấy số 10 ra, mảng một chiều Q sẽ tăng giá trị biến Front lên 1 đơn vị:

Front = 0

Back = 7

Biểu diễn hàng đợi Hình 4a bởi mảng một chiều

Trả lời câu hỏi củng cố:

Em hãy:

a. Cho biết những thao tác nào cần được thực hiện để có thể lấy số 6 ra khỏi hàng đợi ở Hình 4a và vẽ hàng đợi biểu diễn bởi mảng một chiều tại thời điểm lấy xong số 6. Giá trị biến Front thay đổi thế nào so với trạng thái ban đầu ở Hình 4b.

10

3

5

6

-7

12

4

9

Lấy ra

Thêm vào

(dequeue)

(enqueue)

Đầu (Front)

Cuối (Back)

Hình 4a

Front = 4

Back = 7

Thao tác thực hiện:

• Lần lượt lấy ra số 3 và tăng giá trị biến Front = 2
• Lấy ra số 5 và tăng giá trị biến Front = 3
• Lấy ra số 6 và tăng giá trị biến Front = 4.

Giá trị biến Front tăng lên 3 đơn vị so với Hình 4b.

Trả lời câu hỏi củng cố:

Em hãy:

b. Vẽ hàng đợi thu được khi tiếp tục thực hiện một thao tác thêm vào số 8. Giá trị biến Back thay đổi thế nào so với Hình 4b

Front = 4

Back = 8

Giá trị biến Back tăng lên 1 đơn vị so với Hình 4b.

Trả lời câu hỏi củng cố:

--------------- Còn tiếp ---------------