Comparing "Queue" objects in Java

I think the documentation is stating that Queue implementations do not generally override the default equals method from the Object class as the ordering of elements within a Queue can greatly differ for each implementation and thus comparing them in a generic way may give unexpected results.

If you want to compare Queue objects based on your own criteria you can implement a Comparator<Queue> class (specifically the compare method). You can then use this method to directly compare two Queues, or use it to sort a collection of Queues etc.

See the javadoc for Comparator

The difficulty here is that Queues do have the semantics of being ordered, but that ordering isn't always manifest in the iteration order of the queue. Defining equals() and hashCode() for an ordered collection pretty much requires iterating the elements in their semantic order. If you can't iterate elements in their semantic order, you can't define a reasonable equals() or hashCode() contract.

PriorityQueue is a good example of this. The elements' semantic order is defined by the provided comparator or by the elements' natural ordering. However, the iteration order of a PriorityQueue is undefined!

The iterator does not return the elements in any particular order.

The reason is that a PriorityQueue is heap data structure stored in an array. The elements aren't stored in order. They're stored in a way that meets the heap invariant, which is weaker than total ordering. There are many different ways the same elements can be stored in a heap representing the same semantic ordering. You can get the elements of a PriorityQueue in their semantic order by extracting them from the queue -- which has the side effect of destroying the queue.

I suppose one could define equals() and hashCode() of a queue by using the semantic order and applying rules similar to that of List. For PriorityQueue, this would require creating a temporary copy of the array and sorting it on each call. I suspect this is too onerous; many programmers would be surprised to learn that computing a hash code of a PriorityQueue would take O(n log n) time and O(n) temporary space. For this reason I suspect equals() and hashCode() for Queue were left unspecified, to inherit the identity-based versions from Object.

Queues in the default implementation are compared via references (default implementation in Object class). So you'll have to override equals if you want to compare queues, or you can convert queues to some other collection (say, list or set, or array) and compare those, that would be a bit easier from implementation perspective.

The reason for this behavior (not overriding equals) is stated in the javadoc (you already quoted it), which means something like: we can't tell if 1 2 3 is the same as 3 2 1 because ordering of the elements in the queue might be important so please go figure it out yourself.