隊列在線程池等有限資源池中的應用
一 概述
CPU的資源是有限的，任務的處理速度與線程個數並不是完全線性正相關的。相反，過多的線程反而會導致CPU資源頻繁的切換，處理性能下降。所以，線程池的大小一般都是綜合考慮要處理任務的特點和硬件環境，來事先設置的。
二 隊列
隊列的概念非常好理解，你可以把它想象成排隊買票，先來的先買，後來的人只能站末尾，不允許插隊。先進者先出，這就是典型的"隊列"。隊列是一種操作受限的線程表數據結構，存在兩個基本操作：入隊enqueue()，放一個數據到隊列尾部；出隊dequeue()，從隊列頭部取一個元素。
對了作爲一種非常基礎的數據結構，隊列的應用也非常廣泛，特別是一些具有某些額外特性的隊列，比如循環隊列，阻塞隊列，併發隊列。其實隊列是很多偏底層系統的，框架，中間件開發的重要底層數據結構。比如高性能隊列Disruptor，Linux環型緩存，都用到了循環併發隊列；此外Java concurrent併發包利用ArrayBlockingQueue來實現公平鎖等。
三 順序隊列和鏈式隊列
隊列和棧一樣，也是一種抽象的數據結構。它具有先進先出的特性，支持在隊尾插入元素，在對頭刪除元素。我們可以用數組來實現，也可以用鏈表來實現。用數組實現的隊列叫做順序隊列，用鏈表實現的隊列叫作鏈式隊列。
順序隊列
棧的出棧入棧都是操作同一個頭結點，隊列的入隊和出隊分別操作隊尾和隊頭。
當我們調用兩次出隊操作之後，隊列中的head指針指向下標爲2的位置，tail指針仍然指向下標爲4的位置。
隨着不停地進行入隊，出隊操作，head和tail都會持續往後移動。當tail移動到最右邊，即使數組中還有空閒空間，也無法繼續往隊列中添加數據。此時可以通過數據搬移，使得每次出隊操作都相當於刪除數組下標爲0的數據，要搬移整個隊列中的數據，這樣出隊操作的時間複雜度就會從原來的O(1)變爲O(n)，實際上，我們在出隊時可以不用搬移數據，如果沒有空閒時間了，我們只需要在入隊時，再集中觸發一次數據的搬移操作。
當隊列的tail指針移動到數組的最右邊後，如果有新的數據入隊，我們可以將head到tail之間的數據，整體搬移到數組下標爲0的位置。
鏈式隊列
基於鏈表的實現的隊列中，同樣需要兩個指針：head指針和tail指針。它們分別指向鏈表的第一個結點和最後一個結點。
入隊時：tail ->next = new node（增加結點）， tail = tail->next（增加的結點爲尾部結點）；
出隊時：head = head->next（將刪除前的頭節點下一個作爲新的頭結點）。
四 循環隊列
當通過數組實現循環隊列的時候，再tail = n的時候，會有數據搬移操作，這樣入隊的性能就會收到影響。爲了解決數據搬移的問題，我們可以通過循環隊列來解決問題。
循環隊列，顧名思義，他長得像一個環。原來數組時有頭有尾的，時一條直線。現在我們把首尾相連，組成一個隊列環。
圖中的隊列的大小爲8，當前head爲4，tail爲7。當有一個新的元素a入隊時，我們放入下標爲7的位置。但這個時候，我們並不把tail更新爲8，而是將其在環中後移一位，到下標爲0 的位置。當再有一個元素b入隊時，我們將b放入下標爲0的位置。然後tail加1更新爲1。所以，在a，b依次入隊之後的樣子。
通過這樣的方法，我們成功避免了數據搬移操作。看起來不難理解，但是循環隊列的代碼實現難度要比前面講的非循環隊列難多了。要像寫出沒有bug的循環隊列的實現代碼，最關鍵的時，確定好隊空和隊滿的判定條件。
在用數組實現的非循環隊列中，隊滿的判斷條件是tail == n，隊空的判斷條件是head == tail。在循環隊列中，隊列爲空的判斷條件仍然是head == tail，但隊列滿的判斷條件就稍微有點複雜了。
如圖爲隊滿的情況，tail = 3，head = 4，n = 8；有數據發現(3+1)%8=4。根據規律，隊列滿時，可以得到隊滿的公式爲(tail +1)%n = head。
當隊列滿時，圖中的tail指向的位置實際上是沒有存儲數據的。所以，循環隊列會浪費一個數組的內存空間。
五 阻塞隊列和併發隊列
阻塞隊列
阻塞隊列其實就是在隊列的基礎上增加了阻塞操作。簡單來說，就是在隊列爲空的時候，從隊頭取數據會被阻塞。因爲此時還沒有數據可取，直到隊列中有了數據才能返回；如果隊列已經滿了，那麼插入數據的操作就會被阻塞，直到隊列中有空閒的位置後再插入數據，然後再返回。
"生產者-消費者模型"可以通過阻塞隊列來完成。這種基於阻塞隊列實現的"生產者-消費者模型"，可以有效的協調生產和消費的速度。當"生產者"生產數據的速度過快，"消費者"來不及消費時，存儲數據的隊列很快就會滿了。這個時候，生產者就阻塞等待，直到"消費者"消費了數據，"生產者"纔會被喚醒繼續"生產"。
不僅如此，基於阻塞隊列，我們還可以通過協調"生產者"和"消費者"的個數，來提高數據的處理效率。
在多線程情況下，會有多個線程同時操作隊列，這個時候就會存在線程安全問題。線程安全的隊列叫作併發隊列。最簡單直接的實現方式是直接在enqueue()，dequeue()方法上加鎖，但是鎖粒度大併發度比較低，同一時刻僅允許一個存或者取操作。實際上，基於數組的循環隊列，利用CAS原子操作，可以實現非常高效的併發隊列。這也是循環隊列比鏈式隊列應用更加廣泛的原因。
六 隊列在線程池等有限資源池中的應用
當線程池沒有空閒線程時，處理新的任務請求資源時，線程池存在兩種處理策略：
- 第一種是非阻塞的處理方式，直接拒絕任務請求；
- 第二種是阻塞的處理方式，將請求排隊，等到有空閒線程時，取出排隊的請求繼續處理。
我們希望公平地處理每個排隊的請求，先進者先服務，所以隊列這種數據很適合來存儲排隊請求。我們前面說過，隊列有基於鏈表和基於數組這兩種實現方式。
基於鏈表的實現方式，可以實現一個支持無限隊列的無界隊列（unbounded queue），但是可能會導致過多的請求排隊等待，請求處理的響應時間過長。所以，針對響應時間比較敏感的系統，基於鏈表實現的無線排隊的線程池時不合適的。
基於數組實現的有界隊列（bounded queue），隊列的大小有限，所以線程池中排隊的請求超過隊列大小時，接下來的請求就會被拒絕，這種方式對響應時間銘感的系統來說，就相對更加合理。不過，設置一個合理的隊列大小，也是非常有講究的。隊列太大導致等待的請求太多，隊列太小會導致無法充分利用系統資源，發揮最大性能。
實際上，對於大部分資源有限的場景，當沒有空閒資源時，基本上都可以通過"隊列"這種數據結構來實現請求排隊。