一、什么是隊(duì)列？
1.先進(jìn)先出（FIFO）
2.支持兩個(gè)操作：入隊(duì)enqueue()，放一個(gè)數(shù)據(jù)到隊(duì)尾；出隊(duì)dequeue()，從隊(duì)頭取一個(gè)元素。
3.棧一樣，隊(duì)列也是一種操作受限的線性表。
二、如何實(shí)現(xiàn)隊(duì)列？
隊(duì)列API
public interface Queue<T> {
public void enqueue(T item); //入隊(duì)
public T dequeue(); //出隊(duì)
public int size(); //統(tǒng)計(jì)元素?cái)?shù)量
public boolean isNull(); //是否為空
public boolean isFull(); //是否已滿
}
實(shí)現(xiàn)方法
1.數(shù)組實(shí)現(xiàn)
2.鏈表實(shí)現(xiàn)
三、隊(duì)列的分類
順序隊(duì)列
基于數(shù)組實(shí)現(xiàn)的順序的隊(duì)列
時(shí)間復(fù)雜度
入隊(duì)：O(1)
出隊(duì)：O(n) 因?yàn)橐罄m(xù)元素移動數(shù)據(jù)
循環(huán)隊(duì)列
可以解決假溢出的問題，但是操作更加復(fù)雜，需要區(qū)分隊(duì)列滿和隊(duì)列空的情況，因?yàn)檫@個(gè)時(shí)候隊(duì)頭和隊(duì)尾坐標(biāo)一樣。
時(shí)間復(fù)雜度
入隊(duì)：O(1)
出隊(duì)：O(1)
若是用鏈表實(shí)現(xiàn)，就無上面問題，且入出隊(duì)列時(shí)間復(fù)雜度都是O(1);但是數(shù)組實(shí)現(xiàn)在并發(fā)隊(duì)列有應(yīng)用。
四、隊(duì)列的應(yīng)用
阻塞隊(duì)列
1.可以隊(duì)列的基礎(chǔ)上增加阻塞操作，就成了阻塞隊(duì)列。
2.阻塞隊(duì)列就是在隊(duì)列為空的時(shí)候，從隊(duì)頭取數(shù)據(jù)會被阻塞，因?yàn)榇藭r(shí)還沒有數(shù)據(jù)可取，直到隊(duì)列中有了數(shù)據(jù)才能返回；如果隊(duì)列已經(jīng)滿了，那么插入數(shù)據(jù)的操作就會被阻塞，直到隊(duì)列中有空閑位置后再插入數(shù)據(jù)，然后在返回。
阻塞隊(duì)列的操作方法
拋出異常 返回特殊值 一直阻塞 超時(shí)退出
插入方法 add（e） offer(e) put(e) offer(e,time,unit)
移除方法 remove() poll() take() poll(time,unit)
檢查方法 element() peek()
JDK提供的阻塞隊(duì)列有
ArrayBlockingQueue: 數(shù)組結(jié)構(gòu)組成的有界阻塞隊(duì)列,需要初始化隊(duì)列的容量，初始化后容量不能修改。FIFO
LinkedBlockingQueue: 鏈表結(jié)構(gòu)組成的有界（無界的是MAX.INTEGER）阻塞隊(duì)列，F(xiàn)IFO
PriorityBlockingQueue: 支持優(yōu)先級排序的無界阻塞隊(duì)列 ，有擴(kuò)容機(jī)制
DelayQueue: 使用優(yōu)先級隊(duì)列實(shí)現(xiàn)的無界阻塞可延遲隊(duì)列
SysnchronousQueue: 一個(gè)元素的阻塞隊(duì)列，單個(gè)元素
LinkedTransferQueue: 一個(gè)由鏈表組成的無界阻塞隊(duì)列
LinkedBlockingDeque: 一個(gè)由鏈表組成的雙向阻塞隊(duì)列
被阻塞的情況主要有如下兩種
當(dāng)隊(duì)列滿了的時(shí)候進(jìn)行入隊(duì)列操作
當(dāng)隊(duì)列空了的時(shí)候進(jìn)行出隊(duì)列操作
并發(fā)隊(duì)列
1.在多線程的情況下，會有多個(gè)線程同時(shí)操作隊(duì)列，會存在線程安全問題；這時(shí)需要使用并發(fā)隊(duì)列。
2.簡單實(shí)現(xiàn)就是在入、出方法上加鎖，但是鎖粒度大并發(fā)度會比較低，同一時(shí)刻僅允許一個(gè)存或取操作。
3.高效的并發(fā)隊(duì)列基于數(shù)組的循環(huán)隊(duì)列利用CAS原子操作。
3.線程池的使用的場景
JDK提供了兩套實(shí)現(xiàn)
1.以ConcurrentLinkedQueue為代表的高性能隊(duì)列非阻塞隊(duì)列
2.以BlockingQueue接口為代表的阻塞隊(duì)列，無論哪種都繼承自Queue
ConcurrentLinkedDeque 非阻塞式隊(duì)列
無界線程安全隊(duì)列
先進(jìn)先出的原則
不允許null元素
add() 和 offer() 都是加入元素的方法
poll() 和 peek() 都是取頭元素節(jié)點(diǎn)，區(qū)別在于前者會刪除元素，后者不會
