CODEWITHSUNDEEP
javaqueuepriority-queuecomparator
KKKK
KKKK

Reputation: 347

Queue interface confusion

Question1:

The following output is 1,2,3

Queue<Integer> q1 = new PriorityQueue<Integer>();
    q1.add(1);
    q1.add(3);
    q1.add(2);
    System.out.print(pq.poll());
    System.out.print(pq.poll());
    System.out.print(pq.poll());

The following output is 1,3,2

Queue<Integer> q2 = new LinkedList<Integer>();
    q3.add(1);
    q3.add(3);
    q3.add(2);
    System.out.print(q3.poll());
    System.out.print(q3.poll());
    System.out.print(q3.poll());

Why? Since they are both implementing the Queue interface but has a different behavior? I think that no matter what the implementing class is, it's behavior has to be the same if they are implementing the same interface.

Question2:

Suppose I define a class with the following

class process {
  int exeTime;
  int arrTime;
  process(int, arr, int exe) {
    arrTime=arr;
    exeTime = exe;
  }
}

What is the effect of overriding the compare method in this following line of code and why?

PriorityQueue<process> pq2 = new PriorityQueue<process>(new Comparator<process>() {
        @Override
        public int compare(process p1, process p2) {
            if (p1.exeTime == p2.exeTime)
                return p1.arrTime - p2.arrTime;
            return p1.exeTime - p2.exeTime;
        }
    });

Upvotes: 1

Views: 146

Answers (3)

Paul Boddington
Paul Boddington

Reputation: 37655

I think that no matter what the implementing class is, it's behavior has to be the same if they are implementing the same interface.

This is not correct. All an implementation has to do is satisfy the contract for the interface. For the Queue interface, the behaviour can be like a stack (first in, last out), like a traditional queue (first in, first out), or return elements based on some other system.

A PriorityQueue returns elements based on their priority, given by a Comparator. If compare(a, b) returns a negative integer, a has a higher priority than b. If compare(a, b) returns a positive integer, it's the other way around. If compare(a, b) returns 0, a and b have equal priority.

Upvotes: 2

Louis Wasserman
Louis Wasserman

Reputation: 198211

Not at all. Read the Queue interface documentation:

Queues typically, but do not necessarily, order elements in a FIFO (first-in-first-out) manner. Among the exceptions are priority queues, which order elements according to a supplied comparator, or the elements' natural ordering, and LIFO queues (or stacks) which order the elements LIFO (last-in-first-out). Whatever the ordering used, the head of the queue is that element which would be removed by a call to remove() or poll(). In a FIFO queue, all new elements are inserted at the tail of the queue. Other kinds of queues may use different placement rules. Every Queue implementation must specify its ordering properties.

An implementation of Queue can use any ordering it chooses.

2) The queue will be ordered first by exeTime, then by arrTime if there is a tie in exeTime.

Upvotes: 2

rgettman
rgettman

Reputation: 178293

  1. Yes, the two classes have different behavior, but it doesn't contradict the Queue interface.

The Javadocs for add in Queue don't state any particular order:

Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions, returning true upon success and throwing an IllegalStateException if no space is currently available.

The Javadocs for poll in Queue may state that it takes from the head of the queue, but add doesn't say what element should be at the head.

Retrieves and removes the head of this queue, or returns null if this queue is empty.

Because Queue doesn't specify any particular order, each implementing class is free to define it for itself.

  1. You aren't overriding anything; you are specifying a Comparator class to be used to order elements in the PriorityQueue, according to the Javadocs for that constructor.

Creates a PriorityQueue with the default initial capacity and whose elements are ordered according to the specified comparator.

Upvotes: 2

Related Questions