Java: weird queue order from priority queue

Question

I wrote a maze solution program that should support DFS, BFS, A *, Dijkstra's and a greedy algorithm. In any case, I chose PriorityQueue for my border data structure, since I thought that priority could behave like a queue, a stack or a priority queue, depending on the implementation of the comparator.

Here's how I applied my comparator to turn a priority queue into a queue:

/ Since the "natural order" of the priority queue has the smallest element in the head, and the usual comparator returns -1 when the first is less than the second, the hacked comparator always returns 1, so the current (last) square will be placed in the tail (this should work recursively) /

public int compare(Square square1, Square square2) { return 1; } 

However, my solution for the maze was not optimal after I made BFS.

The maze begins in the upper right corner with the coordinate (35.1), and my program checks the left, then up, then down, then the right neighbor. Here is the listing I made:

interviewed (35.1)

added (34.1)

added (35.2)

interviewed (34.1)

added (33.1)

added (34.2)

survey (35.2)

added (35.3)

survey (33.1)

Added

(32.1)

added (33.2)

interviewed (34.2)

add (34.3)

survey (32.1)

......

The notification in BFS (35.3) should be polled before (32.1), since the first is added to the queue before the last. What really confused me was that the data structure behaved like a queue - all new members were added from the back - until I added (32.1), which was placed at the head of the queue.

I thought that my comparator should force a priority queue to put new players in the back. I’m even unfamiliar that the data structure has changed its nature from the queue to the stack in the middle.

Thank you so much guys forward and sorry for my poor English, Regards, Sean

Answer 1

The way you implemented compare is erroneous, and will only work if it is called only in the specific way you assume. However, you do not know in what context PriorityQueue actually calls compare . The compare function may well be called on an existing element within the data structure, and not on a new one, or vice versa.

(Even if you read the source code and traced it and found that this particular implementation works in a certain way, you should not depend on it if you want your code to be supported. At least you do yourself more work by explaining why it works.)

You can simply use some kind of counter and assign it as a value for each added item, and then implement compare correctly based on the value.

The correct compare implementation might look like this:

 int compare(Object x, Object y){ return x.getSomeProperty() - y.getSomeProperty(); } 

Please note that if you change the order of the parameters, the answer will also change. No, the return value does not have to be from {-1, 0, 1}. The spectrum causes 0 or a negative or positive integer. You can use whatever you want as long as it is correct.