Java look at elements in queue

Question

So I'm making a search algorithm. I'm using a queue to store all of my objects

This is how I initialised it

Queue<Node> queue = new LinkedList<Node>();

I want to compare a variable in each object and order to queue. My plan is to use a for loop to compare the first object with each of the other objects and whichever object has the lowest variable is sent to the front of the queue. Then move onto the next object and repeat the process. My issue is I'm not sure how to retrieve an object from the queue that isn't the first object in the queue....

Answer 1

You could do a for loop through the Queue:

for (Node n : queue) {
     do stuff with n   
}

However, you aren't going to be able to remove items from the middle of the queue. Might I suggest a structure like an ArrayList?

Answer 2

In my opinion the best way is to use PriorityQueue. You can specify implementation of Comparator interface that will impose how elements should be sorted inside of queue.

Here is an example:

Let's say that this is your Node class:

public class Node {

  // this field will be used to sort in queue
  private int value;

  public Node(int value) {
    this.value = value;
  }

  public int getValue() {
    return value;
  }

  @Override
  public String toString() {
    return "My value is: " + value;
  }
}

And here is example of adding Nodes into queue:

import java.util.PriorityQueue;
import java.util.Random;

public class QueueExample {

    public static void main(String[] args) {

        Random r = new Random(); 

        // Priority queue with custom comparator
        PriorityQueue<Node> queue = new PriorityQueue<Node>(10, new SampleNodeComparator());

        // adding 100 nodes with random value
        for(int i = 0; i < 100; ++i) {
            queue.add( new Node(r.nextInt(1000)));
        }

        // nodes will be removed from queue in order given by comparator
        while(queue.size() != 0) {
            System.out.println(queue.remove());
        }
    }
}

And the most important part - implementation of our custom comparator

import java.util.Comparator;

// our comparator needs to implements Comparator interface
public class SampleNodeComparator implements Comparator<Node> {

    @Override
    public int compare(Node o1, Node o2) {

        /*
        value that should be return from compare method should follow rules:
        if o1 == o2 - return 0
        if o1 > o2 - return any positive value
        if o1 < 02 - return any negative value
         */
        return o1.getValue() - o2.getValue();
    }
}

When you run main method from QueueExample class you will see on console that values are removed from queue sorted by Node.value value.

Answer 3

Use Queue<E>#peek () to retrieve an object without removing it.

---

Some example code:

import java.util.*;
class Example {
    public static void main (String[] args) throws Exception {
        Queue<String> list = new PriorityQueue<>();
        {   // Initialize the Queue
            list.add ("Hello ");
            list.add ("Mrs. ");
            list.add ("DoubtFire! ");
        }

        System.out.println (list);

        // Iterating through the Queue
        String element;
        while ( (element = list.peek()) != null) {
            if (element.equals ("Mrs. ")) {
                System.out.println ("\"Mrs\" found!");
            }
            System.out.println (element);
            list.remove (element);
        }

        System.out.println (list); // Empty by now...
    }
}

Output:

[DoubtFire! , Mrs. , Hello ]
DoubtFire! 
Hello 
"Mrs" found!
Mrs. 
[]

Answer 4

Queue interface does not guarantee any particular order while iterating or polling so theoretically this task is impossible to implement with Queue.

Answer 5

Seeing your response to my comment, I think that in your case, you should use the PriorityQueue because it does what you need without needing you to reinvent the wheel, which is usually not recommended.

By default, the priority queue will use the default implementation of the compareTo method. Assuming that you have a composite type, you have two options:

You can make your custom class implement the Comparabale interface and have your sorting logic there.

Alternatively, you could pass your own comparator:

PriorityQueue<..> p = new PriorityQueue<..>(5, new Comparator<..>()
{
    @override
    public int compare(.. type1, .. type2)
    {
       //comparison logic done here.
    }
}

You can take a look at this short tutorial for more information.