2012-05-02 32 views
6

Tôi đang sử dụng PriorityBlockingQueue với trường ưu tiên. Trong thử nghiệm của tôi, tôi sử dụng System#currentTime() cho các ưu tiên — các ưu tiên tương tự được thu được bởi máy tính quá nhanh đến mức mili giây giống nhau (hoặc nhiều hơn mili giây trên PC có sai số).Tại sao PriorityQueue không hoạt động như một Hàng đợi?

Khi mức độ ưu tiên giống như hàng đợi hoạt động như thể đó là một chồng, điều này có vẻ lạ. Có cách nào khác để làm cho hàng đợi hoạt động như thể đó là hàng đợi bình thường (có nghĩa là, FIFO hơn là hành vi LIFO) khi các ưu tiên của các phần tử giống nhau không?

Trả lời

11

Hoạt động trên lớp này không đảm bảo về thứ tự các phần tử có mức độ ưu tiên như nhau. Nếu bạn cần thực thi một thứ tự, bạn có thể định nghĩa các lớp tùy chỉnh hoặc các bộ so sánh sử dụng khóa thứ cấp để phá vỡ các mối quan hệ trong các giá trị ưu tiên chính.

PriorityBlockingQueue tài liệu themselves cho bạn biết điều này và cách thực hiện nó nếu bạn cần.

+1

Đã thấy tài liệu, nhưng dự kiến ​​rằng sẽ có một lớp tiện ích để tạo hàng đợi không phải là một ngăn xếp. Nếu tôi đặt trên hàng đợi, nó sẽ đi đến phía sau và nhảy hàng đợi nếu nó là một ưu tiên cao hơn. – Ben

+2

Tại sao? Hầu hết người dùng sử dụng 'PriorityBlockingQueue' _with priority priorities._ –

+2

vì Stack không phải là một Queue hay chỉ là Semantics? – Ben

2

Tôi không nghĩ hàng đợi ưu tiên đảm bảo thứ tự nhận các phần tử bằng nhau. Một lựa chọn là có mức độ ưu tiên phức tạp hơn - đẩy tiêu cực của kích thước của hàng đợi khi đẩy phần tử cùng với mức độ ưu tiên của nó và so sánh các giá trị này cho các phần tử ưu tiên bằng nhau.

1

Chỉ cần tạo PriorityBlockingQueue bằng Bộ so sánh của riêng bạn, tính thời gian tạo tài khoản (xem http://docs.oracle.com/javase/6/docs/api/java/util/concurrent/PriorityBlockingQueue.html#PriorityBlockingQueue(int, java.util.Comparator)). Bạn có thể phải thay đổi các phím của bạn từ Ngày đơn giản thành một lớp Ngày tháng và bộ đếm, nơi sau này sẽ được tăng lên trên toàn cầu với mọi sáng tạo (trường tĩnh của lớp khóa mới của bạn); nó không thực sự là FIFO mà là First First Out.

Hoặc, chỉ cần triển khai lớp PriorityQueueFifo của riêng bạn.

0

Một giải pháp khác là duy trì bộ đếm trong các thử nghiệm mà bạn sử dụng cho mức độ ưu tiên và bạn tăng trên mỗi lần chèn. Bằng cách đó, hàng đợi ưu tiên của bạn sẽ có thứ tự FIFO trong các thử nghiệm của bạn, nhưng nó sẽ trông giống như một hàng đợi ưu tiên tùy ý.

Các vấn đề liên quan