# Java Queue系列之PriorityQueue

在上一篇中我用一張圖來梳理了一下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.常用功能函數

方法名	功能描述
add(E e)	添加元素
clear()	清空
contains(Object o)	檢查是否包含目前參數元素
offer(E e)
peek()	讀取元素，（不删除）
poll()	取出元素，（删除）
remove(Object o)	删除指定元素
size()	傳回長度

用法示例

上面提到具有優先級，那麼這裡舉個例子。我在上高中的時候，每月分一次班級，老師會按照本月月考的成績來讓每位同學優先選擇自己心儀的座位。這裡所有的同學便是一個隊列；每次喊一個人進來挑選座位，這便是出對的操作；成績由前至後，這邊是優先的政策。

• 代碼示例如下：

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分

  ---------按順序出隊選座位------------

從第一部分輸出可以看出，學生入隊并不是 按順序的，而在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開始運作...

  ------ 運作結果 ---------

  1

  2

  3

  4

  5

  6

  7

  8

  9

結果中我們可以看到，具有兩個1，兩個9.這是不符合我們預期的，我們預期的是not contains 才插入，現在的出現的了重複的。上面的例子隻需要在add方法上加鎖，才可以達到我們預期的效果。是以說，PriorityQueue是非線程安全的。

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

工作6年，失業19天

Java8系列- 如何用Java8 Stream API找到心儀的女朋友

Java8系列- 何用Java8 Stream API進行資料抽取與收集

spring如何啟動的？這裡結合spring源碼描述了啟動過程

SpringMVC是怎麼工作的,SpringMVC的工作原理

spring 異常處理。結合spring源碼分析400異常處理流程及解決方法

Mybatis Mapper接口是如何找到實作類的-源碼分析

使用Netty實作HTTP伺服器

Netty實作心跳機制

Netty系列

感謝您的閱讀，歡迎您評論交流。PS:部落格園已停更，後續請通過郵件或者公衆号聯系