Câu hỏi:

13/07/2024 200

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?

Xem lời giải

Câu hỏi trong đề: Giải chuyên đề Tin 12 KNTT Bài 4: Kiểu dữ liệu hàng đợi có đáp án !!

Bắt đầu thi

Quảng cáo

Trả lời:

Giải bởi Vietjack

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.

Hot: 500+ Đề thi thử tốt nghiệp THPT các môn, ĐGNL các trường ĐH... file word có đáp án (2025). Tải ngay

Sách thầy cô Vietjack biên soạn:

Xem thêm »

CÂU HỎI HOT CÙNG CHỦ ĐỀ

Câu 1

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

Xem đáp án

Lời giải

So sánh giữa các hàm của ngăn xếp (stack) và hàng đợi (queue) được cài đặt bằng danh sách (list) của Python:

* Sự giống nhau

1. Dữ liệu cơ bản:

- Cả hai đều sử dụng danh sách (list) của Python để lưu trữ các phần tử.

2. Khởi tạo:

- Cả hai đều cần một phương thức khởi tạo (__init__) để tạo một danh sách trống.

3. Kiểm tra rỗng:

- Cả hai đều có một phương thức để kiểm tra xem cấu trúc dữ liệu có rỗng hay không (is_empty).

* Sự khác nhau:

1. Thêm phần tử:

- Ngăn xếp (stack):

+ Hàm push thêm một phần tử vào cuối danh sách (đỉnh ngăn xếp).

+ self.stack.append(item)

- Hàng đợi (queue):

+ Hàm enqueue thêm một phần tử vào cuối danh sách (đuôi hàng đợi).

+ self.queue.append(item)

- Lấy phần tử:

+ Ngăn xếp (stack):

+ Hàm pop lấy phần tử cuối cùng của danh sách (đỉnh ngăn xếp) và trả về phần tử đó.

+ return self.stack.pop()

+ Hàng đợi (queue):

+ Hàm dequeue lấy phần tử đầu tiên của danh sách (đầu hàng đợi) và trả về phần tử đó.

+ return self.queue.pop(0)

- Lấy phần tử nhưng không xóa:

+ Ngăn xếp (stack):

Hàm top trả về phần tử cuối cùng của danh sách (đỉnh ngăn xếp) mà không xóa nó.

return self.stack[-1]

Hàm bottom trả về phần tử đầu tiên của danh sách (đáy ngăn xếp) mà không xóa nó.

return self.stack[0]

+ Hàng đợi (queue):

Hàm front trả về phần tử đầu tiên của danh sách (đầu hàng đợi) mà không xóa nó.

return self.queue[0]

Hàm rear trả về phần tử cuối cùng của danh sách (đuôi hàng đợi) mà không xóa nó.

return self.queue[-1]

Câu 2

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.

Xem đáp án

Lời giải

Nếu biểu diễn hàng đợi (queue) bằng một danh sách (list), lệnh dequeue(Q) thường được thực hiện bằng cách sử dụng phương thức pop(0), tức là lấy và loại bỏ phần tử đầu tiên của danh sách. Độ phức tạp thời gian của lệnh này là O(n)O(n)O(n), với nnn là số phần tử trong hàng đợi hiện thời. Để hiểu rõ tại sao lại như vậy, ta cần xem xét cách thức hoạt động của danh sách trong Python.

Hoạt động của lệnh pop(0)

1. Truy cập phần tử đầu tiên:

Truy cập phần tử đầu tiên của danh sách (phần tử có chỉ số 0) là O(1)O(1)O(1), vì Python có thể truy cập bất kỳ phần tử nào của danh sách theo chỉ số trong thời gian hằng số.

2. Loại bỏ phần tử đầu tiên:

- Khi phần tử đầu tiên bị loại bỏ, tất cả các phần tử còn lại trong danh sách phải được di chuyển về phía trước một vị trí để lấp chỗ trống. Cụ thể, phần tử thứ hai trở thành phần tử thứ nhất, phần tử thứ ba trở thành phần tử thứ hai, và cứ thế tiếp tục.

- Quá trình di chuyển tất cả các phần tử này có độ phức tạp là O(n)O(n)O(n), vì cần phải di chuyển n−1n-1n−1 phần tử trong danh sách (với nnn là tổng số phần tử ban đầu).

Độ phức tạp thời gian

- Việc di chuyển tất cả các phần tử về phía trước một vị trí có độ phức tạp thời gian là O(n−1)O(n-1)O(n−1), nhưng về mặt phân tích độ phức tạp, chúng ta bỏ qua hằng số và bậc thấp, do đó kết quả là O(n)O(n)O(n).

Vì lý do này, lệnh dequeue(Q) thực hiện bằng Q.pop(0) có độ phức tạp thời gian là O(n)O(n)O(n).

Lựa chọn thay thế

Để cải thiện hiệu suất có thể sử dụng collections.deque trong Python, một cấu trúc dữ liệu được thiết kế cho việc thêm và loại bỏ phần tử ở cả hai đầu với độ phức tạp thời gian là O(1)O(1)O(1):

from collections import deque

Q = deque([1, 2, 3, 4, 5])

Q.popleft() # Loại bỏ phần tử đầu tiên, độ phức tạp là O(1)

Với deque , lệnh dequeue(Q) sẽ có độ phức tạp thời gian là O(1)O(1)O(1), hiệu quả hơn rất nhiều so với việc sử dụng danh sách.

Câu 3