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

Giải Chuyên đề Tin 12 Bài 4: Kiểu dữ liệu hàng đợi - Kết nối tri thức

Hoạt động 1 trang 16 Chuyên đề Tin học 12: 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?

Quảng cáo

Lời giải:

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

Có, hoàn toàn có thể biểu diễn hàng đợi (queue) bằng mảng một chiều (array). Trong Python, danh sách (list) có thể được sử dụng để cài đặt hàng đợi. Tuy nhiên, cần quản lý các chỉ số cho phép thêm phần tử vào cuối hàng đợi (enqueue) và lấy phần tử ra từ đầu hàng đợi (dequeue) một cách hiệu quả.

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?

Để thực hiện các phép toán thêm vào và lấy ra trong hàng đợi biểu diễn bằng mảng một chiều, cần có các biến sau:

1. Front (đầu hàng đợi):

- Đây là biến giữ vị trí của phần tử đầu tiên trong hàng đợi.

- Khi thực hiện phép toán lấy ra (dequeue), phần tử tại vị trí front sẽ được lấy ra, và chỉ số front sẽ được cập nhật để trỏ đến phần tử tiếp theo.

2. Rear (cuối hàng đợi):

- Đây là biến giữ vị trí của phần tử cuối cùng trong hàng đợi.

- Khi thực hiện phép toán thêm vào (enqueue), phần tử mới sẽ được thêm vào vị trí kế tiếp của rear, và chỉ số rear sẽ được cập nhật để trỏ đến vị trí cuối mới của hàng đợi.

3. Size (kích thước hiện tại):

- Đây là biến theo dõi số lượng phần tử hiện có trong hàng đợi.

- Biến này giúp kiểm tra hàng đợi có rỗng hay đầy để tránh các lỗi underflow (lấy từ hàng đợi rỗng) và overflow (thêm vào hàng đợi đầy).

4. Capacity (dung lượng tối đa):

- Đây là biến xác định dung lượng tối đa của mảng được sử dụng để cài đặt hàng đợi.

- Giúp kiểm tra và ngăn chặn tình trạng tràn (overflow) khi hàng đợi đầy.

Quảng cáo

Lời giải bài tập Chuyên đề Tin 12 Bài 4: Kiểu dữ liệu hàng đợi hay, ngắn gọn khác: