Câu hỏi:

13/07/2024 156

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:

a) Có thể cài đặt hàng đợi bằng mảng một chiều tương tự như ngăn xếp được không?

b) Khi cài đặt hàng đợi bằng mảng một chiều, cần có thông tin nào để thực hiện 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

a) Có thể cài đặt hàng đợi bằng mảng một chiều tương tự như ngăn xếp được không?

Có, có thể cài đặt hàng đợi (queue) bằng mảng một chiều tương tự như ngăn xếp (stack) bằng cách sử dụng danh sách (list) trong Python. Tuy nhiên, hàng đợi và ngăn xếp có cách thức hoạt động khác nhau. Trong khi ngăn xếp tuân theo nguyên tắc LIFO (Last In, First Out - Vào sau, ra trước), hàng đợi tuân theo nguyên tắc FIFO (First In, First Out - Vào trước, ra trước). Để cài đặt hàng đợi bằng mảng một chiều, ta cần phải quản lý việc 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).

b) Khi cài đặt hàng đợi bằng mảng một chiều, cần có thông tin nào để thực hiện phép toán thêm vào và lấy ra?

Khi cài đặt hàng đợi bằng mảng một chiều, cần phải quản lý hai chỉ số chính:

1. Front (đầu hàng đợi): Chỉ số này 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í này 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): Chỉ số này 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 chỉ số rear, và chỉ số rear sẽ được cập nhật để trỏ đến vị trí cuối mới của hàng đợi.

Ngoài ra, còn cần thêm thông tin về kích thước của mảng để quản lý việc tràn (overflow) khi hàng đợi đầy và để tránh lấy ra từ hàng đợi rỗng (underflow). Một số cách quản lý thông tin bổ sung có thể bao gồm:

- Size (kích thước hiện tại): Số lượng phần tử hiện có trong hàng đợi.

- Capacity (dung lượng tối đa): Dung lượng tối đa của mảng được sử dụng để cài đặt hàng đợi.

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