Java Queue系列之PriorityQueue

今天药忘吃喽~ 2022-06-05 01:30 154阅读 0赞

在上一篇中我用一张图来梳理了一下[Java中的各种Queue][Java_Queue]之间的关系。这里介绍下PriorityQueue。PriorityQueue位于Java util包中，观其名字前半部分的单词Priority是优先的意思，实际上这个队列就是具有“优先级”。既然具有优先级的特性，那么就得有个前后排序的“规则”。所以其接受的类需要实现Comparable 接口。

## API ##

### 1.构造函数 ###

PriorityQueue() PriorityQueue(Collection<? extends E> c) PriorityQueue(int initialCapacity) PriorityQueue(int initialCapacity, Comparator<? super E> comparator) PriorityQueue(PriorityQueue<? extends E> c) PriorityQueue(SortedSet<? extends E> c)

### 2.常用功能函数 ###

<table style="margin:0px; padding:0px; border-collapse:collapse; border-spacing:0px; border:1px solid silver; word-break:break-word; color:rgb(0,0,0); font-family:Verdana,Arial,Helvetica,sans-serif; font-size:14px; line-height:21px"> 
 <thead style="margin:0px; padding:0px"> 
  <tr style="margin:0px; padding:0px"> 
   <th style="margin:0px; padding:3px; border:1px solid silver; border-collapse:collapse"> 方法名</th> 
   <th style="margin:0px; padding:3px; border:1px solid silver; border-collapse:collapse"> 功能描述</th> 
  </tr> 
 </thead> 
 <tbody style="margin:0px; padding:0px"> 
  <tr style="margin:0px; padding:0px"> 
   <td style="margin:0px; padding:3px; border:1px solid silver; border-collapse:collapse"> add(E e)</td> 
   <td style="margin:0px; padding:3px; border:1px solid silver; border-collapse:collapse"> 添加元素</td> 
  </tr> 
  <tr style="margin:0px; padding:0px"> 
   <td style="margin:0px; padding:3px; border:1px solid silver; border-collapse:collapse"> clear()</td> 
   <td style="margin:0px; padding:3px; border:1px solid silver; border-collapse:collapse"> 清空</td> 
  </tr> 
  <tr style="margin:0px; padding:0px"> 
   <td style="margin:0px; padding:3px; border:1px solid silver; border-collapse:collapse"> contains(Object o)</td> 
   <td style="margin:0px; padding:3px; border:1px solid silver; border-collapse:collapse"> 检查是否包含当前参数元素</td> 
  </tr> 
  <tr style="margin:0px; padding:0px"> 
   <td style="margin:0px; padding:3px; border:1px solid silver; border-collapse:collapse"> offer(E e)</td> 
   <td style="margin:0px; padding:3px; border:1px solid silver; border-collapse:collapse"> 添加元素</td> 
  </tr> 
  <tr style="margin:0px; padding:0px"> 
   <td style="margin:0px; padding:3px; border:1px solid silver; border-collapse:collapse"> peek()</td> 
   <td style="margin:0px; padding:3px; border:1px solid silver; border-collapse:collapse"> 读取元素，（不删除）</td> 
  </tr> 
  <tr style="margin:0px; padding:0px"> 
   <td style="margin:0px; padding:3px; border:1px solid silver; border-collapse:collapse"> poll()</td> 
   <td style="margin:0px; padding:3px; border:1px solid silver; border-collapse:collapse"> 取出元素，（删除）</td> 
  </tr> 
  <tr style="margin:0px; padding:0px"> 
   <td style="margin:0px; padding:3px; border:1px solid silver; border-collapse:collapse"> remove(Object o)</td> 
   <td style="margin:0px; padding:3px; border:1px solid silver; border-collapse:collapse"> 删除指定元素</td> 
  </tr> 
  <tr style="margin:0px; padding:0px"> 
   <td style="margin:0px; padding:3px; border:1px solid silver; border-collapse:collapse"> size()</td> 
   <td style="margin:0px; padding:3px; border:1px solid silver; border-collapse:collapse"> 返回长度</td> 
  </tr> 
 </tbody> 
</table>

## 用法示例 ##

上面提到具有优先级，那么这里举个例子。我在上高中的时候，每月分一次班级，老师会按照本月月考的成绩来让每位同学优先选择自己心仪的座位。这里所有的同学便是一个队列；每次喊一个人进来挑选座位，这便是出对的操作；成绩由前至后，这边是优先的策略。

>  *  代码示例如下：

public class PriorityQueueTest { public static void main(String[] args) { final PriorityQueue<Student> queue=new PriorityQueue<>(); Student p1=new Student(95,"张三"); Student p2=new Student(89,"李四"); Student p3=new Student(89,"李四"); Student p4=new Student(67,"王五"); Student p5=new Student(92,"赵六"); queue.add(p1); queue.add(p2); queue.add(p3);//add 和offer效果一样。 queue.offer(p4);//add 方法实现，其实就是调用了offer queue.offer(p5) for (Student Student : queue) { System.out.println(Student.toString()); } System.out.println("---------------------"); while(!queue.isEmpty()){ System.out.println(queue.poll()); } } } class Student implements Comparable{ private int score; private String name; public Student(int age,String name){ this.score=age; this.name=name; } public int getScore() { return score; } public void setScore(int score) { this.score = score; } public String getName() { return name; } public void setName(String name) { this.name = name; } public String toString(){ return "姓名："+name+"-"+score+"分"; } @Override public int compareTo(Object o) { Student current=(Student)o; if(current.getScore()>this.score){ return 1; }else if(current.getScore()==this.score){ return 0; } return -1; } }

>  *  运行结果：  
>     姓名：张三-95分  
>     姓名：赵六-92分  
>     姓名：王五-67分  
>     姓名：李四-89分  
>     \---------按顺序出队选座位------------  
>     姓名：张三-95分  
>     姓名：赵六-92分  
>     姓名：李四-89分  
>     姓名：李四-89分  
>     姓名：王五-67分

从第一部分输出可以看出，学生入队并不是 按顺序的，而在poll出来的时候是按顺序出队的，这里确实实现了分数高这优先选座位的效果，poll方法返回的总是队列剩余学生中分数最高的。

## 安全性 ##

查看PriorityQueue类的源码，会发现增加操作，并不是原子操作。没有使用任何锁。那么，如果是在多线程环境，肯定是不安全的。下面给出例子，开启多个线程，调用同一个方法对Queue进行添加元素。然后输出结果。

public class PriorityQueueTest { static final PriorityQueue<Integer> queue=new PriorityQueue<>(); /** * 向队列中插入元素 * @param number */ public void add(int number){ if(!queue.contains(number)){ System.out.println(Thread.currentThread()+"："+number); queue.add(number); } } public static void main(String[] args) throws InterruptedException { final PriorityQueueTest qt=new PriorityQueueTest(); final Random r=new Random(); Thread t1=new Thread(){ public void run(){ System.out.println("t1开始运行..."); for(int i=0;i<10;i++){ qt.add(r.nextInt(10)); } } }; Thread t2=new Thread(){ public void run(){ System.out.println("t2开始运行..."); for(int i=0;i<10;i++){ qt.add(r.nextInt(10)); } } }; Thread t3=new Thread(){ public void run(){ System.out.println("t3开始运行..."); for(int i=0;i<10;i++){ qt.add(r.nextInt(10)); } } }; t1.start(); t2.start(); t3.start(); t1.join(); t2.join(); t3.join(); System.out.println("------ 运行结果 ---------"); while(!queue.isEmpty()){ System.out.println(queue.poll()); } } }

>  *  运行结果  
>     t2开始运行...  
>     t3开始运行...  
>     t1开始运行...  
>     \------ 运行结果 ---------  
>     0  
>     1  
>     1  
>     2  
>     3  
>     4  
>     5  
>     6  
>     7  
>     8  
>     9  
>     9

结果中我们可以看到，具有两个1，两个9.这是不符合我们预期的，我们预期的是not contains 才插入，现在的出现的了重复的。上面的例子只需要在add方法上加锁，才可以达到我们预期的效果。所以说，PriorityQueue是非线程安全的。

[Java_Queue]: http://www.cnblogs.com/demingblog/p/6474865.html