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)機制土全。
下表顯示了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 元素束倍。
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 鎖殃恒。