什么是隊列？隊列詳解和面試題匯總
隊列（Queue）：與棧相對的一種數據結構， 集合（Collection）的一個子類。隊列允許在一端進行插入操作，而在另一端進行刪除操作的線性表，棧的特點是后進先出，而隊列的特點是先進先出。隊列的用處很大，比如實現(xiàn)消息隊列。Queue 類關系圖，如下圖所示：
注：為了讓讀者更直觀地理解，上圖為精簡版的 Queue 類關系圖。本文如無特殊說明，內容都是基于 Java 1.8 版本。
隊列（Queue）
1）Queue 分類
從上圖可以看出 Queue 大體可分為以下三類。
雙端隊列：雙端隊列（Deque）是 Queue 的子類也是 Queue 的補充類，頭部和尾部都支持元素插入和獲取。
阻塞隊列：阻塞隊列指的是在元素操作時（添加或刪除），如果沒有成功，會阻塞等待執(zhí)行。例如，當添加元素時，如果隊列元素已滿，隊列會阻塞等待直到有空位時再插入。
非阻塞隊列：非阻塞隊列和阻塞隊列相反，會直接返回操作的結果，而非阻塞等待。雙端隊列也屬于非阻塞隊列。
2）Queue 方法說明
add(E)：添加元素到隊列尾部，成功返回 true，隊列超出時拋出異常；
offer(E)：添加元素到隊列尾部，成功返回 true，隊列超出時返回 false；
remove()：刪除元素，成功返回 true，失敗返回 false；
poll()：獲取并移除此隊列的第一個元素，若隊列為空，則返回 null；
peek()：獲取但不移除此隊列的第一個元素，若隊列為空，則返回 null；
element()：獲取但不移除此隊列的第一個元素，若隊列為空，則拋異常。
阻塞隊列
1）BlockingQueue
BlockingQueue 在 java.util.concurrent 包下，其他阻塞類都實現(xiàn)自 BlockingQueue 接口，BlockingQueue 提供了線程安全的隊列訪問方式，當向隊列中插入數據時，如果隊列已滿，線程則會阻塞等待隊列中元素被取出后再插入；當從隊列中取數據時，如果隊列為空，則線程會阻塞等待隊列中有新元素再獲取。BlockingQueue 核心方法插入方法：
add(E)：添加元素到隊列尾部，成功返回 true，隊列超出時拋出異常；
offer(E)：添加元素到隊列尾部，成功返回 true，隊列超出時返回 false ；
put(E)：將元素插入到隊列的尾部，如果該隊列已滿，則一直阻塞。
刪除方法：
remove(Object)：移除指定元素，成功返回 true，失敗返回 false；
poll()： 獲取并移除隊列的第一個元素，如果隊列為空，則返回 null；
take()：獲取并移除隊列第一個元素，如果沒有元素則一直阻塞。
檢查方法：
peek()：獲取但不移除隊列的第一個元素，若隊列為空，則返回 null。
2）LinkedBlockingQueue
LinkedBlockingQueue 是一個由鏈表實現(xiàn)的有界阻塞隊列，容量默認值為 Integer.MAX_VALUE，也可以自定義容量，建議指定容量大小，默認大小在添加速度大于刪除速度情況下有造成內存溢出的風險，LinkedBlockingQueue 是先進先出的方式存儲元素。
3）ArrayBlockingQueue
ArrayBlockingQueue 是一個有邊界的阻塞隊列，它的內部實現(xiàn)是一個數組。它的容量是有限的，我們必須在其初始化的時候指定它的容量大小，容量大小一旦指定就不可改變。ArrayBlockingQueue 也是先進先出的方式存儲數據，ArrayBlockingQueue 內部的阻塞隊列是通過重入鎖 ReenterLock 和 Condition 條件隊列實現(xiàn)的，因此 ArrayBlockingQueue 中的元素存在公平訪問與非公平訪問的區(qū)別，對于公平訪問隊列，被阻塞的線程可以按照阻塞的先后順序訪問隊列，即先阻塞的線程先訪問隊列。而非公平隊列，當隊列可用時，阻塞的線程將進入爭奪訪問資源的競爭中，也就是說誰先搶到誰就執(zhí)行，沒有固定的先后順序。
4）DelayQueue
DelayQueue 是一個支持延時獲取元素的無界阻塞隊列，隊列中的元素必須實現(xiàn) Delayed 接口，在創(chuàng)建元素時可以指定延遲時間，只有到達了延遲的時間之后，才能獲取到該元素。實現(xiàn)了 Delayed 接口必須重寫兩個方法 ，getDelay(TimeUnit) 和 compareTo(Delayed)，
非阻塞隊列
ConcurrentLinkedQueue 是一個基于鏈接節(jié)點的無界線程安全隊列，它采用先進先出的規(guī)則對節(jié)點進行排序，當我們添加一個元素的時候，它會添加到隊列的尾部；當我們獲取一個元素時，它會返回隊列頭部的元素。它的入隊和出隊操作均利用 CAS（Compare And Set）更新，這樣允許多個線程并發(fā)執(zhí)行，并且不會因為加鎖而阻塞線程，使得并發(fā)性能更好。
優(yōu)先級隊列
PriorityQueue 一個基于優(yōu)先級堆的無界優(yōu)先級隊列。優(yōu)先級隊列的元素按照其自然順序進行排序，或者根據構造隊列時提供的 Comparator 進行排序，具體取決于所使用的構造方法。優(yōu)先級隊列不允許使用 null 元素。
PriorityQueue 注意的點：
PriorityQueue 是非線程安全的，在多線程情況下可使用 PriorityBlockingQueue 類替代；
PriorityQueue 不允許插入 null 元素。
相關面試題
1.ArrayBlockingQueue 和 LinkedBlockingQueue 的區(qū)別是什么？
答：ArrayBlockingQueue 和 LinkedBlockingQueue 都實現(xiàn)自阻塞隊列 BlockingQueue，它們的區(qū)別主要體現(xiàn)在以下幾個方面：
ArrayBlockingQueue 使用時必須指定容量值，LinkedBlockingQueue 可以不用指定；
ArrayBlockingQueue 的最大容量值是使用時指定的，并且指定之后就不允許修改；而 LinkedBlockingQueue 最大的容量為 Integer.MAX_VALUE；
ArrayBlockingQueue 數據存儲容器是采用數組存儲的；而 LinkedBlockingQueue 采用的是 Node 節(jié)點存儲的。
2.LinkedList 中 add() 和 offer() 有什么關系？
答：add() 和 offer() 都是添加元素到隊列尾部。offer 方法是基于 add 方法實現(xiàn)的。
3.Queue 和 Deque 有什么區(qū)別？
答：Queue 屬于一般隊列，Deque 屬于雙端隊列。一般隊列是先進先出，也就是只有先進的才能先出；而雙端隊列則是兩端都能插入和刪除元素。
4.LinkedList 屬于一般隊列還是雙端隊列？
答：LinkedList 實現(xiàn)了 Deque 屬于雙端隊列，因此擁有 addFirst(E)、addLast(E)、getFirst()、getLast() 等方法。
5.Java 中常見的阻塞隊列有哪些？
答：Java 中常見的阻塞隊列如下：
ArrayBlockingQueue，由數組結構組成的有界阻塞隊列；
PriorityBlockingQueue，支持優(yōu)先級排序的無界阻塞隊列；
SynchronousQueue，是一個不存儲元素的阻塞隊列，會直接將任務交給消費者，必須等隊列中的添加元素被消費后才能繼續(xù)添加新的元素；
LinkedBlockingQueue，由鏈表結構組成的阻塞隊列；
DelayQueue，支持延時獲取元素的無界阻塞隊列。
6.有界隊列和無界隊列有哪些區(qū)別？
答：有界隊列和無界隊列的區(qū)別如下：
有界隊列：有固定大小的隊列叫做有界隊列，比如：new ArrayBlockingQueue(6)，6 就是隊列的大小。
無界隊列：指的是沒有設置固定大小的隊列，這些隊列的特點是可以直接入列，直到溢出。它們并不是真的無界，它們最大值通常為 Integer.MAXVALUE，只是平常很少能用到這么大的容量（超過 Integer.MAXVALUE），因此從使用者的體驗上，就相當于 “無界”。
總結
隊列（Queue）按照是否阻塞可分為：阻塞隊列 BlockingQueue 和 非阻塞隊列。其中，雙端隊列 Deque 也屬于非阻塞隊列，雙端隊列除了擁有隊列的先進先出的方法之外，還擁有自己獨有的方法，如 addFirst()、addLast()、getFirst()、getLast() 等，支持首未插入和刪除元素。隊列中比較常用的兩個隊列還有 PriorityQueue（優(yōu)先級隊列）和 DelayQueue（延遲隊列），可使用延遲隊列來實現(xiàn)延遲消息隊列，這也是面試中比較?？嫉膯栴}之一。需要面試朋友對延遲隊列一定要做到心中有數，動手寫一個消息隊列也是非常有必要的。
