java隊列——queue詳細分析

Queue：基本上，一個隊列就是一個先入先出（FIFO）的數(shù)據(jù)結(jié)構(gòu)

Queue接口與List瓢湃、Set同一級別村怪，都是繼承了Collection接口剩彬。LinkedList實現(xiàn)了Deque接口。

Queue的實現(xiàn)

1、沒有實現(xiàn)的阻塞接口的LinkedList：實現(xiàn)了java.util.Queue接口和java.util.AbstractQueue接口
　　內(nèi)置的不阻塞隊列： PriorityQueue 和 ConcurrentLinkedQueue
　　PriorityQueue 和 ConcurrentLinkedQueue 類在 Collection Framework 中加入兩個具體集合實現(xiàn)否淤。
　　PriorityQueue 類實質(zhì)上維護了一個有序列表悄但。加入到 Queue 中的元素根據(jù)它們的天然排序（通過其 java.util.Comparable 實現(xiàn)）或者根據(jù)傳遞給構(gòu)造函數(shù)的 java.util.Comparator 實現(xiàn)來定位。
　　ConcurrentLinkedQueue 是基于鏈接節(jié)點的石抡、線程安全的隊列檐嚣。并發(fā)訪問不需要同步。因為它在隊列的尾部添加元素并從頭部刪除它們啰扛，所以只要不需要知道隊列的大小嚎京，　　　　　　ConcurrentLinkedQueue 對公共集合的共享訪問就可以工作得很好。收集關(guān)于隊列大小的信息會很慢隐解，需要遍歷隊列鞍帝。

2)實現(xiàn)阻塞接口的：
　　java.util.concurrent 中加入了 BlockingQueue 接口和五個阻塞隊列類。它實質(zhì)上就是一種帶有一點扭曲的 FIFO 數(shù)據(jù)結(jié)構(gòu)厢漩。不是立即從隊列中添加或者刪除元素膜眠，線程執(zhí)行操作阻塞，直到有空間或者元素可用溜嗜。
五個隊列所提供的各有不同：
　　* ArrayBlockingQueue ：一個由數(shù)組支持的有界隊列宵膨。
　　* LinkedBlockingQueue ：一個由鏈接節(jié)點支持的可選有界隊列。
　　* PriorityBlockingQueue ：一個由優(yōu)先級堆支持的無界優(yōu)先級隊列炸宵。
　　* DelayQueue ：一個由優(yōu)先級堆支持的辟躏、基于時間的調(diào)度隊列。
　　* SynchronousQueue ：一個利用 BlockingQueue 接口的簡單聚集（rendezvous）機制土全。

image.png

下表顯示了jdk1.5中的阻塞隊列的操作：

　　add 增加一個元索如果隊列已滿捎琐，則拋出一個IIIegaISlabEepeplian異常
　　remove 移除并返回隊列頭部的元素如果隊列為空，則拋出一個NoSuchElementException異常
**　　element **返回隊列頭部的元素如果隊列為空裹匙，則拋出一個NoSuchElementException異常
　　offer 添加一個元素并返回true 如果隊列已滿瑞凑，則返回false
　　poll 移除并返問隊列頭部的元素如果隊列為空，則返回null
　　peek 返回隊列頭部的元素如果隊列為空概页，則返回null
　　put 添加一個元素如果隊列滿籽御，則阻塞
　　take 移除并返回隊列頭部的元素如果隊列為空，則阻塞

**remove惰匙、element技掏、offer 、poll项鬼、peek 其實是屬于Queue接口哑梳。 **

阻塞隊列的操作可以根據(jù)它們的響應(yīng)方式分為以下三類：aad、removee和element操作在你試圖為一個已滿的隊列增加元素或從空隊列取得元素時拋出異常绘盟。當(dāng)然鸠真，在多線程程序中悯仙，隊列在任何時間都可能變成滿的或空的，所以你可能想使用offer弧哎、poll雁比、peek方法。這些方法在無法完成任務(wù)時只是給出一個出錯示而不會拋出異常撤嫩。

注意：poll和peek方法出錯進返回null偎捎。因此，向隊列中插入null值是不合法的

最后序攘，我們有阻塞操作put和take茴她。put方法在隊列滿時阻塞，take方法在隊列空時阻塞程奠。

LinkedBlockingQueue的容量是沒有上限的（說的不準(zhǔn)確丈牢，在不指定時容量為Integer.MAX_VALUE，不要然的話在put時怎么會受阻呢）瞄沙，但是也可以選擇指定其最大容量己沛，它是基于鏈表的隊列，此隊列按 FIFO（先進先出）排序元素距境。

ArrayBlockingQueue在構(gòu)造時需要指定容量申尼，并可以選擇是否需要公平性，如果公平參數(shù)被設(shè)置true垫桂，等待時間最長的線程會優(yōu)先得到處理（其實就是通過將ReentrantLock設(shè)置為true來達到這種公平性的：即等待時間最長的線程會先操作）师幕。通常，公平性會使你在性能上付出代價诬滩，只有在的確非常需要的時候再使用它霹粥。它是基于數(shù)組的阻塞循環(huán)隊列，此隊列按 FIFO（先進先出）原則對元素進行排序疼鸟。

PriorityBlockingQueue是一個帶優(yōu)先級的隊列后控，而不是先進先出隊列。元素按優(yōu)先級順序被移除空镜，該隊列也沒有上限（看了一下源碼忆蚀，PriorityBlockingQueue是對 PriorityQueue的再次包裝，是基于堆數(shù)據(jù)結(jié)構(gòu)的姑裂，而PriorityQueue是沒有容量限制的，與ArrayList一樣男旗，所以在優(yōu)先阻塞隊列上put時是不會受阻的舶斧。雖然此隊列邏輯上是無界的，但是由于資源被耗盡察皇，所以試圖執(zhí)行添加操作可能會導(dǎo)致 OutOfMemoryError）茴厉，但是如果隊列為空泽台，那么取元素的操作take就會阻塞，所以它的檢索操作take是受阻的矾缓。另外怀酷，往入該隊列中的元素要具有比較能力。

DelayQueue（基于PriorityQueue來實現(xiàn)的）是一個存放Delayed 元素的無界阻塞隊列嗜闻，只有在延遲期滿時才能從中提取元素蜕依。該隊列的頭部是延遲期滿后保存時間最長的 Delayed 元素。如果延遲都還沒有期滿琉雳，則隊列沒有頭部样眠，并且poll將返回null。當(dāng)一個元素的 getDelay(TimeUnit.NANOSECONDS) 方法返回一個小于或等于零的值時翠肘，則出現(xiàn)期滿檐束，poll就以移除這個元素了。此隊列不允許使用 null 元素束倍。

image.png

package com.yao;
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
public class BlockingQueueTest {
 /**
 定義裝蘋果的籃子
  */
 public static class Basket{
  // 籃子被丧，能夠容納3個蘋果
  BlockingQueue<String> basket = new ArrayBlockingQueue<String>(3);

  // 生產(chǎn)蘋果，放入籃子
  public void produce() throws InterruptedException{
   // put方法放入一個蘋果绪妹，若basket滿了甥桂，等到basket有位置
   basket.put("An apple");
  }
  // 消費蘋果，從籃子中取走
  public String consume() throws InterruptedException{
   // get方法取出一個蘋果喂急，若basket為空格嘁，等到basket有蘋果為止
   String apple = basket.take();
   return apple;
  }

  public int getAppleNumber(){
   return basket.size();
  }

 }
 //　測試方法
 public static void testBasket() {
  // 建立一個裝蘋果的籃子
  final Basket basket = new Basket();
  // 定義蘋果生產(chǎn)者
  class Producer implements Runnable {
   public void run() {
    try {
     while (true) {
      // 生產(chǎn)蘋果
      System.out.println("生產(chǎn)者準(zhǔn)備生產(chǎn)蘋果：" 
        + System.currentTimeMillis());
      basket.produce();
      System.out.println("生產(chǎn)者生產(chǎn)蘋果完畢：" 
        + System.currentTimeMillis());
      System.out.println("生產(chǎn)完后有蘋果："+basket.getAppleNumber()+"個");
      // 休眠300ms
      Thread.sleep(300);
     }
    } catch (InterruptedException ex) {
    }
   }
  }
  // 定義蘋果消費者
  class Consumer implements Runnable {
   public void run() {
    try {
     while (true) {
      // 消費蘋果
      System.out.println("消費者準(zhǔn)備消費蘋果：" 
        + System.currentTimeMillis());
      basket.consume();
      System.out.println("消費者消費蘋果完畢：" 
        + System.currentTimeMillis());
      System.out.println("消費完后有蘋果："+basket.getAppleNumber()+"個");
      // 休眠1000ms
      Thread.sleep(1000);
     }
    } catch (InterruptedException ex) {
    }
   }
  }

  ExecutorService service = Executors.newCachedThreadPool();
  Producer producer = new Producer();
  Consumer consumer = new Consumer();
  service.submit(producer);
  service.submit(consumer);
  // 程序運行10s后，所有任務(wù)停止
  try {
   Thread.sleep(10000);
  } catch (InterruptedException e) {
  }
  service.shutdownNow();
 }
 public static void main(String[] args) {
  BlockingQueueTest.testBasket();
 }
}

非阻塞隊列：ConcurrentLinkedQueue(無界線程安全)廊移，采用CAS機制（compareAndSwapObject原子操作）糕簿。
阻塞隊列：ArrayBlockingQueue(有界)、LinkedBlockingQueue（無界）狡孔、DelayQueue懂诗、PriorityBlockingQueue，采用鎖機制苗膝；使用 ReentrantLock 鎖殃恒。