Java：從優先級隊列中產生奇怪的隊列順序

Question

我寫了一個應該支持DFS，BFS，A *，Dijkstra和貪婪算法的迷宮求解程序。無論如何，我選擇PriorityQueue作爲我的前沿數據結構，因爲我認爲優先級可以像隊列，堆棧或優先級隊列一樣依賴於比較器的實現。

這是我如何實現我的比較器把優先級隊列到隊列：

/由於優先級隊列的「自然排序」具有在頭一個現有的比較收益的最小元素和-1當第一小於第二，被黑比較始終返回1，使得當前（最後）方將被放置在尾（這應該遞歸工作）/

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

然而，我的解決方案用於我做了BFS後，迷宮並不是最理想的。

迷宮從座標（35,1）的右上角開始，我的程序檢查左邊，然後向上，然後向下，然後右邊的鄰居。 這裏是我的println那樣：

調查了（35,1）

加入（34,1）

加入（35,2）

調查了（34,1）

加入（33,1）

加入（34,2）

輪詢出（35,2）

加入（35,3）

輪詢出（33,1）

加入（32,1）

加入（33,2）

調查了（34,2）

加（34,3）

調查了（32,1）

......在一個BFS（35,3）

通知應之前的輪詢（32,1），因爲前者是之前後者加入到隊列中。讓我困惑的是數據結構的行爲像一個隊列 - 所有新成員都是從後面添加的 - 直到我添加（32,1），這是放在隊列的頭部。

我認爲我的比較者應該強制優先隊列將新來者放在後面。更奇怪的是，數據結構的性質從隊列變成了中間的棧。

非常感謝你們進取，對不起我的英語不好， 真誠， 肖恩

Answer 1

你已經實現compare的方式是錯誤的，只會工作，如果它被稱爲只有在非常特殊的方式，你在假設。但是，您不知道在PriorityQueue實際上稱爲compare的情況下。 compare函數可能在數據結構中的現有元素上調用，而不是新的元素，反之亦然。 （即使你讀過源代碼並追蹤它，發現這個特定的實現以某種方式工作，如果你希望你的代碼是可維護的，你不應該依賴它），至少， d）通過解釋其工作原理，讓自己做更多的工作。）

您可以使用某種計數器並將其分配爲每個添加項的值，然後根據該值正確執行compare。

正確的實施compare可能是這樣的：

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

請注意，如果您切換參數的順序，答案也將改變。不，int返回的確不是而是必然必須來自{-1,0,1}。該規範要求0，或者一個負數或正整數。你可以使用任何你想要的，只要它是正確的標誌。