PriorityQueue

案例

package com.kevin.container;

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

public class PriorityQueueCase {

    public static void main(String[] args) {
        PriorityQueue priorityQueue = new PriorityQueue();
        int count = 10;
        for (int i = 0; i < count; i++) {
            priorityQueue.add(new Item());
        }

        while (!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.poll());
        }
    }
}

class Item implements Comparable<Item> {
    private int id;

    public Item(int id) {
        this.id = id;
    }

    public Item() {
        this.id = new Random().nextInt(100);
    }

    @Override
    public int compareTo(Item item) {
        return this.id - item.id;
    }

    @Override
    public String toString() {
        return "Item{" +
                "id=" + id +
                '}';
    }
}

源码解析

• add

  • 优先级队列中维护有一个有序的Object 数组
  • 在向优先级队列添加元素时
    • 倒序遍历数组中的元素并和添加的对象进行比较
    • 如果当前元素比较后小于数组中该索引位置的元素，则将该索引的元素后置一位，并继续向前遍历
    • 当遍历到当前元素不小于索引位置元素时，记录位置，结束遍历，并将该对象保存至该索引位置

• poll

  • 返回队列数组的第0索引位置上的元素
  • 如果返回元素后队列不为空，则将剩下的元素均前置一位

PriorityBlockingQueue

PriorityBlockingQueue priorityQueue = new PriorityBlockingQueue<>();

int count = 10;
for (int i = 0; i < count; i++) {
    priorityQueue.add(new Item());
}

while (!priorityQueue.isEmpty()) {
    System.out.println(priorityQueue.poll());
}
priorityQueue.poll();
System.out.println("end");

• PriorityBlockingQueue与PriorityQueue基本一致
• 区别为在add和poll等方法中添加了ReentrantLock锁，如果有其它线程竞争，则阻塞当前程序
• 当队列为空时，再将poll，并不会阻塞，而会返回null