阻塞隊列BlokingQueue與雙向隊列Deque

Queue：基本上，一個隊列就是一個先入先出（FIFO）的資料結構

Queue接口與List、Set同一級别，都是繼承了Collection接口。LinkedList實作了Deque接口。

Queue的實作

1、沒有實作的阻塞接口的LinkedList：實作了java.util.Queue接口和java.util.AbstractQueue接口

　　内置的不阻塞隊列： PriorityQueue 和 ConcurrentLinkedQueue

　　PriorityQueue 和 ConcurrentLinkedQueue 類在 Collection Framework 中加入兩個具體集合實作。

　　PriorityQueue 類實質上維護了一個有序清單。加入到 Queue 中的元素根據它們的天然排序（通過其 java.util.Comparable 實作）或者根據傳遞給構造函數的 java.util.Comparator 實作來定位。

　　ConcurrentLinkedQueue 是基于連結節點的、線程安全的隊列。并發通路不需要同步。因為它在隊列的尾部添加元素并從頭部删除它們，是以隻要不需要知道隊列的大小，　　　　　　ConcurrentLinkedQueue 對公共集合的共享通路就可以工作得很好。收集關于隊列大小的資訊會很慢，需要周遊隊列。

2)實作阻塞接口的：

　　java.util.concurrent 中加入了 BlockingQueue 接口和五個阻塞隊列類。它實質上就是一種帶有一點扭曲的 FIFO 資料結構。不是立即從隊列中添加或者删除元素，線程執行操作阻塞，直到有空間或者元素可用。

五個隊列所提供的各有不同：

　　* ArrayBlockingQueue ：一個由數組支援的有界隊列。

　　* LinkedBlockingQueue ：一個由連結節點支援的可選有界隊列。

　　* PriorityBlockingQueue ：一個由優先級堆支援的無界優先級隊列。

　　* DelayQueue ：一個由優先級堆支援的、基于時間的排程隊列。

　　* SynchronousQueue ：一個利用 BlockingQueue 接口的簡單聚集（rendezvous）機制。

阻塞隊列BlokingQueue與雙向隊列Deque

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

　　add 增加一個元索如果隊列已滿，則抛出一個IIIegaISlabEepeplian異常

　　remove 移除并傳回隊列頭部的元素如果隊列為空，則抛出一個NoSuchElementException異常

　　element 傳回隊列頭部的元素如果隊列為空，則抛出一個NoSuchElementException異常

　　offer 添加一個元素并傳回true 如果隊列已滿，則傳回false

　　poll 移除并返問隊列頭部的元素如果隊列為空，則傳回null

　　peek 傳回隊列頭部的元素如果隊列為空，則傳回null

　　put 添加一個元素如果隊列滿，則阻塞

　　take 移除并傳回隊列頭部的元素如果隊列為空，則阻塞

remove、element、offer 、poll、peek 其實是屬于Queue接口。

阻塞隊列的操作可以根據它們的響應方式分為以下三類：aad、removee和element操作在你試圖為一個已滿的隊列增加元素或從空隊列取得元素時抛出異常。當然，在多線程程式中，隊列在任何時間都可能變成滿的或空的，是以你可能想使用offer、poll、peek方法。這些方法在無法完成任務時隻是給出一個出錯示而不會抛出異常。

注意：poll和peek方法出錯進傳回null。是以，向隊列中插入null值是不合法的

最後，我們有阻塞操作put和take。put方法在隊列滿時阻塞，take方法在隊列空時阻塞。

LinkedBlockingQueue的容量是沒有上限的（說的不準确，在不指定時容量為Integer.MAX_VALUE，不要然的話在put時怎麼會受阻呢），但是也可以選擇指定其最大容量，它是基于連結清單的隊列，此隊列按 FIFO（先進先出）排序元素。

ArrayBlockingQueue在構造時需要指定容量，并可以選擇是否需要公平性，如果公平參數被設定true，等待時間最長的線程會優先得到處理（其實就是通過将ReentrantLock設定為true來達到這種公平性的：即等待時間最長的線程會先操作）。通常，公平性會使你在性能上付出代價，隻有在的确非常需要的時候再使用它。它是基于數組的阻塞循環隊列，此隊列按 FIFO（先進先出）原則對元素進行排序。

PriorityBlockingQueue是一個帶優先級的隊列，而不是先進先出隊列。元素按優先級順序被移除，該隊列也沒有上限（看了一下源碼，PriorityBlockingQueue是對 PriorityQueue的再次包裝，是基于堆資料結構的，而PriorityQueue是沒有容量限制的，與ArrayList一樣，是以在優先阻塞隊列上put時是不會受阻的。雖然此隊列邏輯上是無界的，但是由于資源被耗盡，是以試圖執行添加操作可能會導緻 OutOfMemoryError），但是如果隊列為空，那麼取元素的操作take就會阻塞，是以它的檢索操作take是受阻的。另外，往入該隊列中的元素要具有比較能力。

DelayQueue（基于PriorityQueue來實作的）是一個存放Delayed 元素的無界阻塞隊列，隻有在延遲期滿時才能從中提取元素。該隊列的頭部是延遲期滿後儲存時間最長的 Delayed 元素。如果延遲都還沒有期滿，則隊列沒有頭部，并且poll将傳回null。當一個元素的 getDelay(TimeUnit.NANOSECONDS) 方法傳回一個小于或等于零的值時，則出現期滿，poll就以移除這個元素了。此隊列不允許使用 null 元素。

阻塞隊列BlokingQueue與雙向隊列Deque

package com.lx.bale;

import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.LinkedBlockingQueue;
import java.util.concurrent.PriorityBlockingQueue;

import org.junit.Test;

public class QueueTest {
	public static void main(String[] args) throws InterruptedException {
		final BlockingQueue<Object> queue = new LinkedBlockingQueue<Object>(3);
		queue.add("11");
		queue.add("22");
		queue.add("33");
		new Thread(new Runnable() {
			public void run() {
				try {
					Thread.sleep(3000);
				} catch (InterruptedException e) {
					e.printStackTrace();
				}
				System.out.println(queue.poll());
			}
		}).start();
		queue.put("44");
		System.out.println(queue.poll());
		System.out.println(queue.poll());
		System.out.println(queue.poll());

	}
	
	@Test
	public void fun01() throws InterruptedException{
		/**
		 * ArrayBlockingQueue 等待時間長的線程優先加入,但LinkedBlokingQueue貌似也是一樣 等待長的先加入
		 */
		final BlockingQueue<Object> queue = new ArrayBlockingQueue<Object>(1);
		queue.offer("baseData");
		
		//線程1
		final Thread t1 = new Thread(new Runnable() {
			@Override
			public void run() {
				int count = 0;
				while (true) {
					try {
						Thread.sleep(1000);
						count ++;
					} catch (InterruptedException e) {
						e.printStackTrace();
					}
					if (count > 8) {
						//System.out.println("跳出循環");
						break;
					}
				}
			}
		});
		t1.start();
		// 啟動線程2
		final Thread t2 = new Thread(new Runnable() {
			@Override
			public void run() {
				int count = 0;
				while (true) {
					try {
						Thread.sleep(1000);
						count ++;
					} catch (InterruptedException e) {
						e.printStackTrace();
					}
					if (count > 8) {
						//System.out.println("跳出循環");
						break;
					}
				}
			}
		});
		t2.start();
		
		
		//插入t1 阻塞
		Thread t1Insert = new Thread(new Runnable() {
			@Override
			public void run() {
				try {
					System.out.println("t1插入阻塞");
					queue.put(t1);
					System.out.println("t1插入成功");
				} catch (InterruptedException e) {
					e.printStackTrace();
				}
			}
		});
		t1Insert.start();
		Thread.sleep(1000);
		//插入t2 阻塞
		Thread t2Insert = new Thread(new Runnable() {
			@Override
			public void run() {
				try {
					System.out.println("t2插入阻塞");
					queue.put(t2);
					System.out.println("t2插入成功");
				} catch (InterruptedException e) {
					e.printStackTrace();
				}
			}
		});
		t2Insert.start();
		
		
		
		Thread.sleep(3000);
		System.out.println("取出原始對象"+queue.poll());
		
		/*while (true) {
			try {
				Thread.sleep(1000);
			} catch (InterruptedException e) {
				e.printStackTrace();
			}
			if (t1.isAlive()) {
				System.out.println("線程存活");
			}else{
				System.out.println("線程完畢");
			}
		}*/
		
	}
	@Test
	public void fun02(){
		PriorityBlockingQueue<Object> queue = new PriorityBlockingQueue<Object>();
		queue.put(new String());
	}
}

雙向隊列Deque

一.概述

　　Deque是Queue的子接口,我們知道Queue是一種隊列形式,而Deque則是雙向隊列,它支援從兩個端點方向檢索和插入元素,是以Deque既可以支援LIFO形式也可以支援LIFO形式.Deque接口是一種比Stack和Vector更為豐富的抽象資料形式,因為它同時實作了以上兩者.

二.主要方法

修飾符和傳回值	方法名	描述
添加功能
void	push(E)	向隊列頭部插入一個元素,失敗時抛出異常
void	addFirst(E)	向隊列頭部插入一個元素,失敗時抛出異常
void	addLast(E)	向隊列尾部插入一個元素,失敗時抛出異常
boolean	offerFirst(E)	向隊列頭部加入一個元素,失敗時傳回false
boolean	offerLast(E)	向隊列尾部加入一個元素,失敗時傳回false
擷取功能
E	getFirst()	擷取隊列頭部元素,隊列為空時抛出異常
E	getLast()	擷取隊列尾部元素,隊列為空時抛出異常
E	peekFirst()	擷取隊列頭部元素,隊列為空時傳回null
E	peekLast()	擷取隊列尾部元素,隊列為空時傳回null
删除功能
boolean	removeFirstOccurrence(Object)	删除第一次出現的指定元素,不存在時傳回false
boolean	removeLastOccurrence(Object)	删除最後一次出現的指定元素,不存在時傳回false
彈出功能
E	pop()	彈出隊列頭部元素,隊列為空時抛出異常
E	removeFirst()	彈出隊列頭部元素,隊列為空時抛出異常
E	removeLast()	彈出隊列尾部元素,隊列為空時抛出異常
E	pollFirst()	彈出隊列頭部元素,隊列為空時傳回null
E	pollLast()	彈出隊列尾部元素,隊列為空時傳回null
疊代器
Iterator<E>	descendingIterator()	傳回隊列反向疊代器

可以看出Deque在Queue的方法上新添了對隊列頭尾元素的操作,add,remove,get形式的方法會在有界隊列滿員和空隊列時抛出異常,offer,poll,peek形式的方法則會傳回false或null.

此外方法表中需要注意push = addFirst,pop = removeFirst,隻是使用了不同的方法名展現隊清單示棧結構時的特點.

三.實作

　　同Queue一樣Deque的實作也可以劃分成通用實作和并發實作.

　　通用實作主要有兩個實作類ArrayDeque和LinkedList.

　　ArrayDeque是個可變數組,它是在Java 6之後新添加的,而LinkedList是一種連結清單結構的list.LinkedList要比ArrayDeque更加靈活,因為它也實作了List接口的所有操作,并且可以插入null元素,這在ArrayDeque中是不允許的.

　　從效率來看,ArrayDeque要比LinkedList在兩端增删元素上更為高效,因為沒有在節點建立删除上的開銷.最适合使用LinkedList的情況是疊代隊列時删除目前疊代的元素.此外LinkedList可能是在周遊元素時最差的資料結構,并且也LinkedList占用更多的記憶體,因為LinkedList是通過連結清單連接配接其整個隊列,它的元素在記憶體中是随機分布的,需要通過每個節點包含的前後節點的記憶體位址去通路前後元素.

　　總體ArrayDeque要比LinkedList更優越,在大隊列的測試上有3倍與LinkedList的性能,最好的是給ArrayDeque一個較大的初始化大小,以避免底層數組擴容時資料拷貝的開銷.

　　LinkedBlockingDeque是Deque的并發實作,在隊列為空的時候,它的takeFirst,takeLast會阻塞等待隊列處于可用狀态

阻塞隊列BlokingQueue與雙向隊列Deque

雙向隊列Deque

一.概述

二.主要方法

三.實作

繼續閱讀

UVA - 210 Concurrency Simulator(雙端隊列)

STL源碼剖析筆記之四序列式容器

隊列（二）：Deque

隊列Queue、雙端隊列Deque源碼分析及底層原理隊列Queue優先隊列PriorityQueue雙端隊列Deque

雙端隊列Deque基本操作的C語言實作

STL學習--deque簡介特性面試題源碼（STL3.3）

stl标準庫系列之--deque

使用PriorityQueue實作大小根堆

劍指offer JZ29 最小的K個數

【Java-8-源碼-1】LinkedList、Queue、Deque

一文弄懂java中的Queue家族

leetcode1091. 二進制矩陣中的最短路徑（bfs）

爬蟲基礎利用xpath,requests,lxml,多線程爬取鬥圖啦表情包

從上到下列印二叉樹（Java）

Timer和TimerTask源碼解讀（面試題：雙重定時器）Timer和TimerTask源碼解讀

Python多線程和多程序Python多線程python多程序