Java：由优先级队列组成的奇怪队列顺序

Question

我写了一个迷宫求解程序，该程序应该支持DFS、BFS、a*、Dijkstra和贪婪算法。无论如何，我选择PriorityQueue作为我的frontier数据结构，因为我认为优先级可以表现为队列、堆栈或优先级队列，这取决于比较器的实现。

这就是我如何实现比较器以将优先级队列转换为队列：

/由于优先级队列的“自然排序”在队列的头部具有最小的元素，并且当第一个元素小于第二个元素时，传统比较器返回-1，因此被黑客攻击的比较器总是返回1，以便当前（最后一个）方将被置于尾部（这应该递归工作）/

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

然而，在我做了BFS之后，我对迷宫的解决方案并不是最优的。

迷宫从右上角的坐标（35,1）开始，我的程序检查左边，然后向上，然后向下，然后是右边。以下是我所做的打印：

民调结果（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

您实现比较的方式是错误的，并且只有在以您假设的非常特定的方式调用时才会起作用。但是，您不知道PriorityQueue实际上在什么上下文中调用比较。可以在数据结构中的现有元素上调用比较函数，而不是在新元素上调用，反之亦然。

（即使您确实阅读了源代码并对其进行了跟踪，发现此特定实现以某种方式工作，但如果您希望代码可维护，也不应该依赖于此。至少，您需要解释其工作原理，从而使自己的工作更为繁重。）

您可以使用某种计数器并将其指定为每个添加项的值，然后根据该值正确执行compare。

compare的正确实现可能如下所示：

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

请注意，如果切换参数的顺序，答案也会改变。不，返回的int不一定来自{-1,0,1}。该规范调用0或负整数或正整数。只要符号正确，你可以用任何一个。