資料結構與演算法學習筆記之先進先出的佇列
前言
佇列是一種非常實用的資料結構，類似於生活中發排隊，可應用於生活，開發中各個方面，比如共享印表機（先請求先列印），訊息佇列。你想知道他們是怎麼工作的麼。那就來一起學習一下佇列吧
正文
一、佇列的定義？
1.一種先進先出的線性表
2.只允許 入棧 push()和出棧 pop()
在後端（稱為 rear ）進行插入操作，在前端（稱為 front ）進行刪除操作。
二、如何用程式碼實現佇列？
1.java中JDK提供了Queue介面
使得LinkedList實現了該介面，所以使用佇列的時候，一般採用LinkedList。因為LinkedList是雙向連結串列，可以很方便的實現佇列的所有功能。
Queue使用時要儘量避免Collection的add()和remove()方法，而是要使用offer()來加入元素，使用poll()來獲取並移出元素。它們的優點是通過返回值可以判斷成功與否，add()和remove()方法在失敗的時候會丟擲異常。 如果要使用前端而不移出該元素，使用
element()或者peek()方法。
2.陣列實現（順序佇列）
public class ArrayQueue {
//儲存資料的陣列
private String[] items;
//記錄陣列容量
private int n;
private int size;
//head記錄隊頭索引，tail記錄隊尾索引
private int head = 0;
private int tail = 0;
//申請一個指定容量的佇列
public ArrayQueue(int capacity){
items = new String[capacity];
n = capacity;
}
/*
* 入隊：
* 1.堆滿的時，入隊失敗
* 1.1頻繁出入隊，造成陣列使用不連續
* 1.2在入隊的時候，集中觸發進行資料搬移
* 2.在末尾插入資料，注意tail指向隊尾元素的索引+1
*/
public boolean enqueue(String item){
//表示隊滿
if(head == 0 && tail == n)
return false;
//表示需要資料搬移
else if(head != 0 && tail == n){
for (int i = head; i < tail; i++) {
items[i-head] = items[i];
}
head = 0;
tail = tail - head;
}
//將資料加入佇列
items[tail++] = item;
size++;
return true;
}
//出隊：1.隊空時，出隊失敗;2.出隊，head索引+1
public String dequeue(){
String res = null;
if(head == tail) return res;
res = items[head++];
size--;
return res;
}
}
(程式碼來源於姜威)
3.連結串列實現（鏈式佇列）
public class LinkedQueue {
//定義一個節點類
private class Node{
String value;
Node next;
}
//記錄佇列元素個數
private int size = 0;
//head指向隊頭結點，tail指向隊尾節點
private Node head;
private Node tail;
//申請一個佇列
public LinkedQueue(){}
//入隊
public boolean enqueue(String item){
Node newNode = new Node();
newNode.value = item;
if (size == 0) head = newNode;
else tail.next = newNode;
tail = newNode;
size++;
return true;
}
//出隊
public String dequeue(){
String res = null;
if(size == 0) return res;
if(size == 1) tail = null;
res = head.value;
head = head.next;
size--;
return res;
}
}
(程式碼來源於姜威)
4.迴圈佇列（基於陣列）
迴圈佇列的實現
public class LoopArrayQueue {
//儲存資料的陣列
private String[] items;
//記錄陣列容量
private int n;
private int size = 0;
//head記錄隊頭索引，tail記錄隊尾索引
private int head = 0;
private int tail = 0;
//申請一個指定容量的佇列
public LoopArrayQueue(int capacity){
items = new String[capacity];
n = capacity;
}
//入隊：關鍵在於隊滿的條件
public boolean enqueue(String item){
if ((tail + 1) % n == head) return false;
items[tail] = item;
tail = (tail + 1) % n;
size++;
return true;
}
//出隊：關鍵在於隊空的條件
public String dequeue(){
String res = null;
if(head == tail) return res;
res = items[head];
head = (head + 1) % n;
size--;
return res;
}
}
(程式碼來源於姜威)
三、佇列的常見的應用阻塞佇列和併發佇列
1.阻塞佇列
1）在佇列的基礎上增加阻塞操作，形成了阻塞佇列。
2）阻塞佇列就是在佇列為空的時候，從隊頭取資料會被阻塞，因為此時還沒有資料可取，直到佇列中有了資料才能返回；如果佇列已經滿了，那麼插入資料的操作就會被阻塞，直到佇列中有空閒位置後再插入資料，然後在返回。
3）“生產者-消費者模型”
(圖片來源於王爭)
基於阻塞佇列實現的“生產者-消費者模型”可以有效地協調生產和消費的速度。
當“生產者”生產資料的速度過快，“消費者”來不及消費時，儲存資料的佇列很快就會滿了，這時生產者就阻塞等待，直到“消費者”消費了資料，“生產者”才會被喚醒繼續生產。不僅如此，基於阻塞佇列，我們還可以通過協調“生產者”和“消費者”的個數，來提高資料處理效率，比如配置幾個消費者，來應對一個生產者。
2.併發佇列
1）在多執行緒的情況下，會有多個執行緒同時操作佇列，這時就會存線上程安全問題。
執行緒安全問題的佇列就稱為併發佇列。
2）併發佇列簡單的實現就是在enqueue()、dequeue()方法上加鎖，但是鎖粒度大併發度會比較低，同一時刻僅允許一個存或取操作。
3）基於陣列的迴圈佇列利用CAS原子操作，可以實現非常高效的併發佇列。這也是迴圈佇列比鏈式佇列應用更加廣泛的原因。
3.執行緒池資源枯竭是的處理
在資源有限的場景，當沒有空閒資源時，基本上都可以通過“佇列”這種資料結構來實現請求排隊。
四、佇列線上程池等有限資源中的應用
當我們向固定大小的執行緒池中請求一個執行緒時，如果執行緒池中沒有空閒資源了，這個時候執行緒池如何處理這個請求？ 是拒絕請求還是排隊請求？各種處理策略又是怎麼實現的呢？
兩種處理策略：
非阻塞的處理方式，直接拒絕任務請求
阻塞的處理方式，將請求排隊，等有空閒執行緒，取出佇列中請求繼續處理
基於連結串列的實現方式，可以實現一個支援無線排隊的無界佇列，但是可能會導致過多的請求排隊，請求處理的響應時間過長
基於陣列的實現的有界佇列，佇列的大小有限，所以執行緒池中排隊的請求超過佇列大小時，接下來的請求就會被拒絕，這種方式對響應時間敏感的系統，更加合適；
佇列可以應用在任何有限的資源池中，當沒有空閒資源都可以通過“佇列”來實現請求排隊
五、思考
1.除了執行緒池這種池結構會用到佇列排隊請求，還有哪些類似執行緒池結構或者場景中會用到佇列的排隊請求呢？
在很多偏底層的系統、框架、中介軟體的開發中，起著關鍵性的作用。比如高效能佇列 Disruptor、Linux 環形快取，都用到了迴圈併發佇列；Java concurrent 併發包利用 ArrayBlockingQueue 來實現公平鎖等。
分散式訊息佇列，如 kafka 也是一種佇列
2.今天講到併發佇列，關於如何實現無鎖的併發佇列，網上有很多討論。對這個問題，你怎麼看？
可以使用 cas + 陣列的方式實現。考慮使用CAS實現無鎖佇列，則在入隊前，獲取tail位置，入隊時比較tail是否發生變化，如果否，則允許入隊，反之，本次入隊失敗。出隊則是獲取head位置，進行cas
相關文章