java - PriorityQueue 正在移除最后添加的元素(就像后进先出)

Question

我需要另一双眼睛来看待这个问题。对于我要解决的问题，我已经实现了深度优先搜索和广度优先搜索。基于搜索使用的Queue/stack使用Node对象。

问题是，两种搜索算法都返回相同的序列。仔细研究后，似乎 BFS 算法中的优先级队列正在使最新添加的元素成为队列的 HEAD。

注意我也尝试过如下更改数据结构，因为它仍然给出相同的结果。

PriorityQueue <Node> fifo = new PriorityQueue <Node>();

我遵循接口(interface)提供的常规添加和删除/轮询方法。下面是 BFS 算法的代码。

public static void BFS(Node initial, char [][] grid){
    Queue <Node> fifo = new LinkedList <Node>();
    ArrayList<Node> explored = new ArrayList<Node>();
    int l = 0;
    fifo.add(initial);
    //Make a method to test if there is any dirt remaining on the grid for THIS node
    boolean dirtExists = testDirt(initial.dirtCoordinates);
    //System.out.println("complete boolean value is: " + dirtExists);
    if(!dirtExists){
        //If no dirt, then we are done
    }
    else{
        while(dirtExists){
         //Test whether there are any more elements in the queue. If not, then done
            if(fifo.isEmpty()){
                break;
            }else{
                //Grab the next element in the queue
                Node nextNode = fifo.poll();
                explored.add(nextNode);
                System.out.println("First element removed " + nextNode.stringBuilder);
                if(testDirt(nextNode.dirtCoordinates)){
                    dirtExists = true;
                }else{

                    dirtExists = false;
                    break;
                }
                //System.out.println(nextNode.stringBuilder);
                //System.out.println(dirtExists);
                List<Node> possibleMoves;
                possibleMoves = successor(nextNode, grid);
                //System.out.println(possibleMoves.size());

                for(int i=0; i<possibleMoves.size(); i++){
                        Node temp = possibleMoves.get(i);
                        System.out.println("About to enter the queue " + temp.stringBuilder);

                        //Need to make sure this nextNode does not exist in explored OR the fifo already
                        //Dont worry about this, it still adds new unique nodes to the fifo, i just dont know why its adding it to the head 
                        if(compareNodes(temp, fifo, explored)){
                            //Then do not add because it is a duplicate
                        }else{
                            System.out.println("Just got added to the queue " + temp.stringBuilder);
                            fifo.add(temp);
                        }
                }
                System.out.println("Head of the queue is: " + fifo.peek().stringBuilder);
            }
        }
    }

}

正如下方的 Cody 所指出的

我只是将 fifo 变量传递到一个使用 poll 函数的方法中。这导致了问题。

所以我摆脱了我在函数中所做的轮询，只是遍历队列。

问题解决了!

Answer 1

修改你的方法。删除民意调查，因为它正在从原始列表中删除。您可以直接使用 equals 方法，您可以在您的 Node 类中生成该方法。

private static boolean compareNodes(Node currentNode, Queue<Node> fifo, ArrayList<Node> explored){
    boolean exists = false;
    while(!fifo.isEmpty()){
        exists = fifo.contains(currentNode);
        if(exists){
            //System.out.println("Exists in fifo");
            break;
        }
    }
    if(exists){

    }else{
        for(Node n: explored){
            if(n.equals(currentNode)){
                //System.out.println("Exists in explored");
                exists = true;
                break;
            }else{
                //keep on going
            }
        }
    }

    return exists;
}