資料結構之佇列
一、什麼是佇列？
1.先進先出（FIFO）
2.支援兩個操作：入隊enqueue()，放一個數據到隊尾；出隊dequeue()，從隊頭取一個元素。
3.棧一樣，佇列也是一種操作受限的線性表。
二、如何實現佇列？
佇列API
public interface Queue<T> {
public void enqueue(T item); //入隊
public T dequeue(); //出隊
public int size(); //統計元素數量
public boolean isNull(); //是否為空
public boolean isFull(); //是否已滿
}
實現方法
1.陣列實現
2.連結串列實現
三、佇列的分類
順序佇列
基於陣列實現的順序的佇列
時間複雜度
入隊：O(1)
出隊：O(n) 因為要後續元素移動資料
迴圈佇列
可以解決假溢位的問題，但是操作更加複雜，需要區分佇列滿和佇列空的情況，因為這個時候隊頭和隊尾座標一樣。
時間複雜度
入隊：O(1)
出隊：O(1)
若是用連結串列實現，就無上面問題，且入出佇列時間複雜度都是O(1);但是陣列實現在併發佇列有應用。
四、佇列的應用
阻塞佇列
1.可以佇列的基礎上增加阻塞操作，就成了阻塞佇列。
2.阻塞佇列就是在佇列為空的時候，從隊頭取資料會被阻塞，因為此時還沒有資料可取，直到佇列中有了資料才能返回；如果佇列已經滿了，那麼插入資料的操作就會被阻塞，直到佇列中有空閒位置後再插入資料，然後在返回。
阻塞佇列的操作方法
丟擲異常返回特殊值一直阻塞超時退出 插入方法add（e）offer(e)put(e)offer(e,time,unit) 移除方法remove()poll()take()poll(time,unit) 檢查方法element()peek()
JDK提供的阻塞佇列有
ArrayBlockingQueue: 陣列結構組成的有界阻塞佇列,需要初始化佇列的容量，初始化後容量不能修改。FIFO
LinkedBlockingQueue: 連結串列結構組成的有界（無界的是MAX.INTEGER）阻塞佇列，FIFO
PriorityBlockingQueue: 支援優先順序排序的無界阻塞佇列 ，有擴容機制
DelayQueue: 使用優先順序佇列實現的無界阻塞可延遲佇列
SysnchronousQueue: 一個元素的阻塞佇列，單個元素
LinkedTransferQueue: 一個由連結串列組成的無界阻塞佇列
LinkedBlockingDeque:一個由連結串列組成的雙向阻塞佇列
被阻塞的情況主要有如下兩種
當佇列滿了的時候進行入佇列操作
當佇列空了的時候進行出佇列操作
併發佇列
1.在多執行緒的情況下，會有多個執行緒同時操作佇列，會存線上程安全問題；這時需要使用併發佇列。
2.簡單實現就是在入、出方法上加鎖，但是鎖粒度大併發度會比較低，同一時刻僅允許一個存或取操作。
3.高效的併發佇列基於陣列的迴圈佇列利用CAS原子操作。
3.執行緒池的使用的場景
JDK提供了兩套實現
1.以ConcurrentLinkedQueue為代表的高效能佇列非阻塞佇列
2.以BlockingQueue介面為代表的阻塞佇列，無論哪種都繼承自Queue
ConcurrentLinkedDeque 非阻塞式佇列
無界執行緒安全佇列 先進先出的原則 不允許null元素 add() 和 offer() 都是加入元素的方法 poll() 和 peek() 都是取頭元素節點，區別在於前者會刪除元素，後者不會