队列接口混乱

Question

问题一：

下面的输出是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());

下面的输出是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());

为什么？因为它们都实现了 Queue 接口但具有不同的行为？我认为无论实现 class 是什么，如果它们实现相同的接口，它的行为就必须相同。

问题2：

假设我用下面的

定义了一个class

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

在下面这行代码中覆盖比较方法的效果是什么？为什么？

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

Answer 1

是的，这两个 classes 有不同的行为，但这并不与 Queue 界面相矛盾。

Javadocs for add in Queue 未说明任何特定顺序：

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.

Javadocs for poll in Queue可能会说它从队列的头部获取，但是add并没有说什么元素应该在头部。

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

因为 Queue 没有指定任何特定的顺序，每个实现 class 的人都可以自由地为自己定义它。

你没有覆盖任何东西；您指定 Comparator class 用于根据 Javadocs for that constructor.

PriorityQueue

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

Answer 2

完全没有。阅读 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.

Queue 的实现可以使用它选择的任何顺序。

2) 队列将首先按 exeTime 排序，如果在 exeTime.

中出现平局，则按 arrTime 排序

Answer 3

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.

这是不正确的。一个实现所要做的就是满足接口的约定。对于 Queue 接口，行为可以像堆栈（先进后出）、传统队列（先进先出）或基于其他系统的 return 元素。

A PriorityQueue returns 个元素基于它们的优先级，由 Comparator 给出。如果 compare(a, b) return 是负整数，则 a 的优先级高于 b。如果 compare(a, b) return 是正整数，则相反。如果compare(a, b)returns 0，a和b具有同等优先级。

队列接口混乱

Queue interface confusion

java

queue

priority-queue

comparator