VedhaR VedhaR - 1 month ago 13
Java Question

PriorityQueue is removing last element added (acting like a lifo)

I need another pair of eyes to look at this problem. I have implemented both a Depth first Search and Breadth First Search for a problem I am trying to solve. The Queue/stack used based on the search uses Node objects.

The problem is, both search algorithms are returning the same sequence. After looking into it more, it seems that the Priority Queue in the BFS algorithm is making the newest element that is added the HEAD of the queue.

Note
I have also tried changing the datastructure as follow as it still gives the same result.

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


I am following the conventional add and remove/poll method supplied by the interface. Below is the code for the BFS algorithm.

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);
}
}
}

}


As Cody from below pointed out

All I was passing the fifo variable into a method in which I was using the poll function. This caused the issue.

So I got rid of the polling I did in the function and just iterated through the queue.

Problem Solved!

Answer

Modify your method. Remove poll because it is removing from original list. You can directly use equals method, which you can generate in your Node class.

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;
}
Comments