隊(duì)列定義

先進(jìn)者先出，這就是典型的“隊(duì)列”。隊(duì)列跟棧一樣，也是一種操作受限的線性表數(shù)據(jù)結(jié)構(gòu)。

順序隊(duì)列和鏈?zhǔn)疥?duì)列

• 順序隊(duì)列：用數(shù)組實(shí)現(xiàn)的隊(duì)列

// 用數(shù)組實(shí)現(xiàn)的隊(duì)列 public class ArrayQueue {// 數(shù)組：items，數(shù)組大小：nprivate String[] items;private int n = 0;// head表示隊(duì)頭下標(biāo)，tail表示隊(duì)尾下標(biāo)private int head = 0;private int tail = 0;// 申請(qǐng)一個(gè)大小為capacity的數(shù)組public ArrayQueue(int capacity) {items = new String[capacity];n = capacity;}// 入隊(duì)public boolean enqueue(String item) {// 如果tail == n 表示隊(duì)列已經(jīng)滿了if (tail == n) return false;items[tail] = item;++tail;return true;}// 出隊(duì)public String dequeue() {// 如果head == tail 表示隊(duì)列為空if (head == tail) return null;// 為了讓其他語(yǔ)言的同學(xué)看的更加明確，把--操作放到單獨(dú)一行來(lái)寫了String ret = items[head];++head;return ret;} }

問題一：經(jīng)過(guò)不停的入隊(duì)，出隊(duì)操作，tail指針移動(dòng)到最右邊時(shí)如何處理？

數(shù)據(jù)搬移：每次出隊(duì)操作相當(dāng)于刪除數(shù)組下標(biāo)為0的數(shù)據(jù)，搬移一次，這樣操作的時(shí)間復(fù)雜度為O(n)；

優(yōu)化方案：如果沒有空閑空間了，我們只需要在入隊(duì)時(shí)，再集中觸發(fā)一次數(shù)據(jù)的搬移操作。操作時(shí)間復(fù)雜度為O（1）

數(shù)組實(shí)現(xiàn)的非循環(huán)隊(duì)列特征：在用數(shù)組實(shí)現(xiàn)的非循環(huán)隊(duì)列中，隊(duì)滿的判斷條件是 tail == n，隊(duì)空的判斷條件是 head == tail。

// 入隊(duì)操作，將item放入隊(duì)尾public boolean enqueue(String item) {// tail == n表示隊(duì)列末尾沒有空間了if (tail == n) {// tail ==n && head==0，表示整個(gè)隊(duì)列都占滿了if (head == 0) return false;// 數(shù)據(jù)搬移for (int i = head; i < tail; ++i) {items[i-head] = items[i];}// 搬移完之后重新更新head和tailtail -= head;head = 0;}items[tail] = item;++tail;return true;}

• 鏈?zhǔn)疥?duì)列：用鏈表實(shí)現(xiàn)的隊(duì)列：基于鏈表的實(shí)現(xiàn)，我們同樣需要兩個(gè)指針：head 指針和 tail 指針。它們分別指向鏈表的第一個(gè)結(jié)點(diǎn)和最后一個(gè)結(jié)點(diǎn)。如圖所示，入隊(duì)時(shí)，tail->next= new_node, tail = tail->next；出隊(duì)時(shí)，head = head->next;
• 循環(huán)隊(duì)列：數(shù)組來(lái)實(shí)現(xiàn)隊(duì)列的時(shí)候，在 tail==n 時(shí)，會(huì)有數(shù)據(jù)搬移操作，如何避免數(shù)據(jù)搬移？——用循環(huán)隊(duì)列

循環(huán)隊(duì)列的難點(diǎn)：確定好隊(duì)空和隊(duì)滿的判定條件

那針對(duì)循環(huán)隊(duì)列，如何判斷隊(duì)空和隊(duì)滿呢？隊(duì)列為空的判斷條件仍然是 head == tail。

隊(duì)列滿的條件：(tail+1)%n=head。你有沒有發(fā)現(xiàn)，當(dāng)隊(duì)列滿時(shí)，圖中的 tail 指向的位置實(shí)際上是沒有存儲(chǔ)數(shù)據(jù)的。循環(huán)隊(duì)列會(huì)浪費(fèi)一個(gè)數(shù)組的存儲(chǔ)空間。

循環(huán)隊(duì)列的實(shí)現(xiàn)代碼：注意其中的?tail = (tail + 1) % n;? ? head = (head+1)%n;

public class CircularQueue {// 數(shù)組：items，數(shù)組大小：nprivate String[] items;private int n = 0;// head表示隊(duì)頭下標(biāo)，tail表示隊(duì)尾下標(biāo)private int head = 0;private int tail = 0;// 申請(qǐng)一個(gè)大小為capacity的數(shù)組public CircularQueue(int capacity) {items = new String[capacity];n = capacity;}// 入隊(duì)public boolean enqueue(String item) {// 隊(duì)列滿了if ((tail + 1) % n == head) return false;items[tail] = item;tail = (tail + 1) % n;return true;}// 出隊(duì)public String dequeue() {// 如果head == tail 表示隊(duì)列為空if (head == tail) return null;String ret = items[head];head = (head + 1) % n;return ret;} }

阻塞隊(duì)列和并發(fā)隊(duì)列

阻塞隊(duì)列：在隊(duì)列為空的時(shí)候，從隊(duì)頭取數(shù)據(jù)會(huì)被阻塞；如果隊(duì)列已經(jīng)滿了，那么插入數(shù)據(jù)的操作就會(huì)被阻塞，直到隊(duì)列中有空閑位置后再插入數(shù)據(jù)，然后再返回。“生產(chǎn)者 - 消費(fèi)者模型”！是的，我們可以使用阻塞隊(duì)列，輕松實(shí)現(xiàn)一個(gè)“生產(chǎn)者 - 消費(fèi)者模型”！

基于阻塞隊(duì)列，我們還可以通過(guò)協(xié)調(diào)“生產(chǎn)者”和“消費(fèi)者”的個(gè)數(shù)，來(lái)提高數(shù)據(jù)的處理效率。比如前面的例子，我們可以多配置幾個(gè)“消費(fèi)者”，來(lái)應(yīng)對(duì)一個(gè)“生產(chǎn)者”。

并發(fā)隊(duì)列

如何實(shí)現(xiàn)一個(gè)線程安全的隊(duì)列？簡(jiǎn)單粗暴的方式是直接在enqueue()、dequeue（）方法上直接加鎖；但是并發(fā)度較低；

對(duì)于基于數(shù)組的循環(huán)隊(duì)列，利用cas操作可以實(shí)現(xiàn)更高效的并發(fā)；

循環(huán)隊(duì)列比鏈?zhǔn)疥?duì)列的應(yīng)用廣泛；

總結(jié)：

線程池沒有空閑線程時(shí)，新的任務(wù)請(qǐng)求線程資源時(shí)，線程池該如何處理？各種處理策略又是如何實(shí)現(xiàn)的呢？

兩種處理策略：一種是非阻塞的處理方式，直接拒絕該請(qǐng)求；一種是阻塞的處理方式，將請(qǐng)求排隊(duì)，等有空閑線程時(shí)再取出進(jìn)行處理；

隊(duì)列適應(yīng)于存儲(chǔ)排隊(duì)請(qǐng)求。基于鏈表和基于數(shù)組的實(shí)現(xiàn)：基于鏈表的支持無(wú)限隊(duì)列的無(wú)界排隊(duì)，但是會(huì)導(dǎo)致過(guò)多的請(qǐng)求排隊(duì)等待，造成響應(yīng)時(shí)間過(guò)長(zhǎng)，針對(duì)響應(yīng)時(shí)間比較敏感的系統(tǒng)，基于鏈表實(shí)現(xiàn)的無(wú)限排隊(duì)的線程池是不合適的。；而基于數(shù)組的隊(duì)列的大小有限，所以線程池中排隊(duì)的請(qǐng)求超過(guò)隊(duì)列大小時(shí)，接下來(lái)的請(qǐng)求就會(huì)被拒絕，這種方式對(duì)響應(yīng)時(shí)間敏感的系統(tǒng)來(lái)說(shuō)，就相對(duì)更加合理。關(guān)鍵的是設(shè)置一個(gè)合理的隊(duì)列大小。

實(shí)際上，對(duì)于大部分有限資源的場(chǎng)景，當(dāng)沒有空閑資源基本都可以通過(guò)隊(duì)列的數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)請(qǐng)求排隊(duì)。例如數(shù)據(jù)庫(kù)連接池

?

?

總結(jié)

以上是生活随笔為你收集整理的09 | 队列：队列在线程池等有限资源池中的应用的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。