Gần đây, trong một cuộc phỏng vấn, tôi đã được hỏi những bất lợi của việc sử dụng hàng đợi hình tròn. Tôi không thể nghĩ ra được. Tìm kiếm trên Internet câu trả lời duy nhất tôi thấy là khó thực hiện hơn hàng đợi tuyến tính :). Có bất kỳ bất lợi nào khác không?Bất lợi của hàng đợi tròn?
Dường như với tôi rằng bất kỳ mã nào đi qua hàng đợi sẽ phải theo dõi nút đầu tiên để phát hiện kết thúc hoạt động. Nhưng trong môi trường đa luồng, một luồng khác có thể loại bỏ nút đầu tiên, điều này sẽ làm cho luồng đi qua đi vào một vòng lặp vô hạn. Vì vậy, luồng vượt qua sẽ phải giữ nút đầu tiên bị khóa trong suốt chu kỳ của nó thông qua hàng đợi.
Sau đó, một lần nữa, thường có nguy cơ sử dụng bất kỳ loại danh sách nào trong quá trình điều tra. Ví dụ, đuôi của một danh sách liên kết thông thường có thể bị xóa và di chuyển đến đầu (không phổ biến khi giao dịch với hàng đợi), có thể phá vỡ một trình lặp. – nneonneo
Điều đó sẽ không xảy ra trong trường hợp bộ nhớ dùng chung giữa nhiều tiến trình? Tôi hỏi khi bạn đề cập rõ ràng * chủ đề * – asheeshr
@AshRj Có, nó chắc chắn có thể xảy ra với nhiều quy trình. –
Tôi sẽ nói nhược điểm lớn nhất đối với hàng đợi hình tròn là bạn chỉ có thể lưu trữ các phần tử queue.length. Nếu bạn đang sử dụng nó như một bộ đệm, bạn đang hạn chế chiều sâu lịch sử của bạn.
Một bất lợi nhỏ hơn là khó để nói một hàng đợi trống từ hàng đợi đầy đủ mà không giữ lại thông tin bổ sung.
Không quá khó. Xem nhận xét về Câu hỏi. Có ít nhất 2 cách để làm điều đó ... –
Câu trả lời mà người phỏng vấn đang tìm kiếm có thể phụ thuộc vào một số ngữ cảnh bổ sung không có trong câu hỏi trên.
Ví dụ, thường hàng đợi hình tròn được xem xét cho các hệ thống sản xuất/tiêu dùng đồng thời cao. Khi hàng đợi đầy, các hoạt động ở mặt trước và mặt sau của hàng đợi có thể cho các dòng bộ nhớ cache giống nhau, và đó có thể là một vấn đề trong các ngữ cảnh như thế này. Hoặc có thể người phỏng vấn muốn bạn nói về việc nó dễ dàng hơn bao nhiêu trong một ngôn ngữ được thu gom rác để tạo ra một hàng đợi liên kết không có khóa so với hàng đợi dựa trên mảng tròn. Hoặc có lẽ nó chỉ là về cách bạn có thể sử dụng tốt hơn các container vector được cung cấp bởi ngôn ngữ của bạn nếu bạn sử dụng một hàng đợi tuyến tính với chuyển dịch định kỳ thay vì một hàng đợi hình tròn.
Tùy thuộc vào việc triển khai, bạn có thể phải để trống một nút trong hàng đợi hình tròn trong khi một hàng đợi tuyến tính được điền hoàn toàn. Không có nhiều bất lợi, trừ khi mỗi nút là khổng lồ! – asheeshr
tại sao một nút phải để trống? –
Tùy thuộc vào cách bạn triển khai hàng đợi hình tròn. Nếu bạn lưu trữ dữ liệu trong mỗi nút, thì không có cách nào dễ dàng để phân biệt giữa một danh sách trống và đầy đủ. – asheeshr