Queues in general should not accept null elements because null is used as a sentinel value for poll and
peek to indicate an empty queue.
The LinkedList class provides the simplest implementation of Queue. For historical reasons the
LinkedList class accepts null elements, but you should avoid inserting null elements when using a
LinkedList instance as a queue.
21.7.1. PriorityQueue
The other Queue implementation is PriorityQueue, an unbounded queue, based on a priority heap. The
head of the queue is the smallest element in it, where smallest is determined either by the elements' natural
order or by a supplied comparator. A PriorityQueue is not a sorted queue in the general senseyou can't
pass it to a method expecting a sorted collectionbecause the iterator returned by iterator is not guaranteed
to traverse the elements in priority order; rather it guarantees that removing elements from the queue occurs in
a given order. The iterator can traverse the elements in any order. If you need ordered traversal you could
extract the elements to an array and then sort the array (see "The Arrays Utility Class" on page 607).
Whether the smallest element represents the element with the highest or lowest "priority" depends on how the
natural order or the comparator is defined. For example, if queuing Thread objects according to their
execution priority, then the smallest element represents a Thread with the lowest execution priority.
The performance characteristics of a PriorityQueue are unspecified. A good implementation based on a
priority heap would provide 0(1)operations on the head, with 0(logn) for general insertion. Anything that
requires traversing, such as removing a specific element or searching for one, would be 0(n)
There are six constructors:
publicPriorityQueue(int initialCapacity)Creates a new PriorityQueue that can store initialCapacity
elements without resizing and that orders the elements according to their
natural order.publicPriorityQueue()Creates a new PriorityQueue with the default initial capacity, and that
orders the elements according to their natural order.publicPriorityQueue(int initialCapacity, Comparator<? super E>
comp)Creates a new PriorityQueue that can initially store
initialCapacity elements without resizing, and that orders the
elements according to the supplied comparator.publicPriorityQueue(Collection<? extends E> coll)Creates a new PriorityQueue whose initial contents are the contents of
coll. The capacity of the queue is initially 110% of the size of coll to
allow for some growth without resizing. If coll is a SortedSet or
another PriorityQueue, then this queue will be ordered the same way;
otherwise, the elements will be sorted according to their natural order. If any
element in coll can't be compared, a ClassCastException is thrown.