Tin học 12 · SGK Chuyên đề Khoa học máy tính

Bài 4. Kiểu dữ liệu hàng đợi

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

SAU BÀI HỌC NÀY EM SẼ:

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:

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

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

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:

Chúng ta sẽ quan sát hàng đợi được cài đặt bằng một danh sách (kiểu list của Python). Sau đây là các trường hợp của 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

Qua ví dụ trên, chúng ta thấy trong quá trình thêm vào và lấy ra các phần tử của hàng đợi Q thì đầu (front) là phần tử đầu tiên và đuôi (rear) là phần tử cuối của hàng đợi.

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.

2. Các phép toán của kiểu dữ liệu hàng đợi

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

Sau đây là 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). Đầ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.

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

Q = Queue()
enqueue(Q, 5)

Ví dụ 2. Cho trước dãy số A. Đ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, bắt đầu từ số đầu tiên. Kết thúc khi gặp số âm:

Q = Queue()
for x in A:
if x >= 0:
enqueue(Q, x)
else:
break

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

Bài 4. Kiểu dữ liệu hàng đợi