In Java, How to use basic functioning of Queue using Predefined library available such as PriorityQueue class?

general
, ,
1

i want to get out elements from a queue in order in which they inserted in the queue
for example Basic functioning of Queue as—

add(10);
add(100);
add(25);
add(78);
add(50);

whenever i poll() elements from queue they must be in same order in which they were inserted 10, 100 , 25, 78, 50
Have a look at what i tried

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;

    class NewClass {

    public static void main(String[] args) {

        Queue<Integer> q1 = new PriorityQueue<>();
        Queue<Integer> q2 = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                if (o1 <= o2) {
                    return 1;
                } else {
                    return -1;
                }
            }
        });

        Queue q = new PriorityQueue(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return 1;
            }
        });

        Random r = new Random();
        for (int i = 0; i < 10; i++) {
            int no = r.nextInt(20);
            System.out.print(no + " ");
            q.add(no);
            q1.add(no);
            q2.add(no);
        }

        System.out.println();
        System.out.println("poll from queue in default sorting oredr");
        while (!q1.isEmpty()) {
            System.out.print(q1.poll() + " ");
        }

        System.out.println();
        System.out.println("poll from queue in descending oredr");
        while (!q2.isEmpty()) {
            System.out.print(q2.poll() + " ");
        }

        System.out.println("");
        System.out.println("poll from queue in oreder in which we insert in queue");
        while (!q.isEmpty()) {
            System.out.print(q.poll() + " ");
        }
    }
}

Below is what output i got:–
![alt text][1]

It worked for Default Sorting Order and for descending Order but dont know why it is not working for basic Queue functioning as poll() in same order in which it was inserted

My Main concern here is use priorityQueue predefine functions to implement above… i did it using arrayList, LinkedList already…

other suggestion will also be appriciated
Thanks in Advance
[1]: https://discuss.codechef.com/upfiles/Capture_esnCNGN.PNG

2

You need a simple queue.
Queue< Integer > q=new LinkedList< Integer >(); will work for you
Edit: Don’t forget to include LinkedList from java.util

Edit 2: From java docs( https://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html), the head of this queue is the least element with respect to the specified ordering. If multiple elements are tied for least value, the head is one of those elements – ties are broken arbitrarily

There is a way though. You want to keep track of insertion order(index). I did with a user-defined class

class Pair implements Comparable<Pair> { int val,priority; Pair(int a,int b) { val=a; priority=b; } public int compareTo(Pair p) { return priority-p.priority; } }
Then my code looks like `Queue q=new PriorityQueue();

    Random r = new Random();
    for (int i = 0; i < 10; i++) {
        int no = r.nextInt(20);
        System.out.print(no + " ");
        q.add(new Pair(no,i));
        q1.add(no);
        q2.add(no);
    }`  
I insert elements with their index and comparator uses index for comparison
1 Like
3

First of all, why are you using a PriorityQueue for such simple queue operations ? A simple, straight-forward deque should solve your task with ease…

alt text

You can use a LinkedList for the same purpose, but it’s a bit slower.

Secondly, PriorityQueue implements heap structure. So, the original ordering is lost anyway. “return 1” in Comparator compare method just causes ambiguity, and does not preserve ordering.

Thirdly, you need not write the entire Comparator method for reverse sorting.
You can, instead, simply use the Comparator.reverseOrder() method.

Eg.

alt text

PS: Extremely sorry!!! I had to upload screenshots, because, I don’t know why, but the diamond operator “<>” shows something else when typed!!!

1 Like