什么是隊(duì)列
??隊(duì)列跟棧一樣，也是一種操作受限的線性表數(shù)據(jù)結(jié)構(gòu)。不過，隊(duì)列是先進(jìn)者先出。
隊(duì)列和棧的區(qū)別
??棧只支持兩個(gè)基本操作：入棧 push()和出棧 pop()。隊(duì)列跟棧非常相似，支持的操作也很有限，最基本的操作也是兩個(gè)：入隊(duì) enqueue()，放一個(gè)數(shù)據(jù)到隊(duì)列尾部；出隊(duì) dequeue()，從隊(duì)列頭部取一個(gè)元素。
??隊(duì)列的概念很好理解，基本操作也很容易掌握。作為一種非常基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)，隊(duì)列的應(yīng)用也非常廣泛，特別是一些具有某些額外特性的隊(duì)列，比如循環(huán)隊(duì)列、阻塞隊(duì)列、并發(fā)隊(duì)列。它們?cè)诤芏嗥讓酉到y(tǒng)、框架、中間件的開發(fā)中，起著關(guān)鍵性的作用。比如高性能隊(duì)列 Disruptor、Linux 環(huán)形緩存，都用到了循環(huán)并發(fā)隊(duì)列；Java concurrent 并發(fā)包利用 ArrayBlockingQueue 來實(shí)現(xiàn)公平鎖等。
隊(duì)列的類型
??跟棧一樣，隊(duì)列可以用數(shù)組來實(shí)現(xiàn)，也可以用鏈表來實(shí)現(xiàn)。用數(shù)組實(shí)現(xiàn)的棧叫作順序棧，用鏈表實(shí)現(xiàn)的棧叫作鏈?zhǔn)綏?。同樣，用?shù)組實(shí)現(xiàn)的隊(duì)列叫作順序隊(duì)列，用鏈表實(shí)現(xiàn)的隊(duì)列叫作鏈?zhǔn)疥?duì)列。
順序隊(duì)列
public class ArrayQueue<T> {
/**
* 存儲(chǔ)數(shù)據(jù)的數(shù)組
*/
private T[] tArr;
/**
* 頭坐標(biāo)
*/
private int head = 0;
/**
* 尾坐標(biāo)
*/
private int tail = -1;
/**
* 隊(duì)列容量
*/
@Getter
private int size = 0;
/**
* 構(gòu)造函數(shù)
*/
public ArrayQueue(int arrLength) {
tArr = (T[]) new Object[arrLength];
}
/**
* 入隊(duì)，線程不安全
*/
public boolean offer(T t) {
// 隊(duì)列是否已滿
if (size == tArr.length) {
return false;
}
// 尾是否已到數(shù)組最后，到達(dá)最后則移動(dòng)
if (tail == tArr.length - 1) {
// 移動(dòng)數(shù)組
for (int i = 0; i < size; i++) {
tArr[i] = tArr[head + i];
}
// 重設(shè)頭尾坐標(biāo)
head = 0;
tail = tail - size;
}
// 設(shè)置值
tail++;
tArr[tail] = t;
size++;
return true;
}
/**
* 出隊(duì)，線程不安全
*/
public T take() {
// 隊(duì)列是否為空
if (size == 0) {
return null;
}
// 取值
T t = tArr[head];
head++;
size--;
return t;
}
}
??從代碼中我們看到，當(dāng)隊(duì)列的 tail 指針移動(dòng)到數(shù)組的最右邊后，如果有新的數(shù)據(jù)入隊(duì)，我們可以將 head 到 tail 之間的數(shù)據(jù)，整體搬移到數(shù)組中 0 到 size（隊(duì)列大?。?的位置。圖示如下：
鏈?zhǔn)疥?duì)列
public class LinkedQueue<T> {
/**
* 隊(duì)列頭部節(jié)點(diǎn)
*/
private QueueNode<T> headNode = null;
/**
* 隊(duì)列尾部節(jié)點(diǎn)
*/
private QueueNode<T> tailNode = null;
/**
* 入隊(duì)，線程不安全
*/
public boolean offer(T t) {
// 定義新節(jié)點(diǎn)
QueueNode<T> newNode = new QueueNode<>();
newNode.setData(t);
// 對(duì)頭為空時(shí)設(shè)置為新節(jié)點(diǎn)
if (headNode == null) {
headNode = newNode;
}
// 隊(duì)尾非空時(shí)，設(shè)置其下一節(jié)點(diǎn)為新節(jié)點(diǎn)
if (tailNode != null) {
tailNode.setNextNode(newNode);
}
// 重設(shè)隊(duì)尾節(jié)點(diǎn)
tailNode = newNode;
return true;
}
/**
* 出隊(duì)，線程不安全
*/
public T take() {
// 隊(duì)列為空
if (headNode == null) {
return null;
}
// 獲取當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)
T data = headNode.getData();
// 取上一節(jié)點(diǎn)設(shè)置為棧頂
headNode = headNode.getNextNode();
return data;
}
@Data
private class QueueNode<T> {
/**
* 數(shù)據(jù)
*/
private T data;
/**
* 上一個(gè)節(jié)點(diǎn)
*/
private QueueNode<T> nextNode = null;
}
}
??基于鏈表的實(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ì)列
public class CircleQueue<T> {
/**
* 存儲(chǔ)數(shù)據(jù)的數(shù)組
*/
private T[] tArr;
/**
* 頭坐標(biāo)
*/
private int head = 0;
/**
* 尾坐標(biāo)
*/
private int tail = -1;
/**
* 隊(duì)列容量
*/
@Getter
private int size = 0;
/**
* 構(gòu)造函數(shù)
*/
public CircleQueue(int arrLength) {
tArr = (T[]) new Object[arrLength];
}
/**
* 入隊(duì)，線程不安全
*/
public boolean offer(T t) {
// 隊(duì)列是否已滿
if (size == tArr.length) {
return false;
}
// 尾是否已到數(shù)組最后，到達(dá)最后則移動(dòng)
int newTail = (tail + 1) % tArr.length;
// 設(shè)置值
tArr[newTail] = t;
tail = newTail;
size++;
return true;
}
/**
* 出隊(duì)，線程不安全
*/
public T take() {
// 隊(duì)列是否為空
if (size == 0) {
return null;
}
// 取值
T t = tArr[head];
head = head + 1 % tArr.length;
size--;
return t;
}
}
??循環(huán)隊(duì)列，顧名思義，它長(zhǎng)得像一個(gè)環(huán)。原本數(shù)組是有頭有尾的，是一條直線?，F(xiàn)在我們把首尾相連，扳成了一個(gè)環(huán)。我畫了一張圖，你可以直觀地感受一下。
??我們可以發(fā)現(xiàn)，圖中這個(gè)隊(duì)列的大小為 8，當(dāng)前 head=4，tail=6。當(dāng)有一個(gè)新的元素 a 入隊(duì)時(shí)，我們放入下標(biāo)為 7 的位置，把 tail 更新為 7。當(dāng)再有一個(gè)元素 b 入隊(duì)時(shí)，我們將 b 放入下標(biāo)為 0 的位置，然后 tail 更新為0。
??從上面的圖中我們可以看到，隊(duì)列為空的條件是head = tail ,而隊(duì)列滿的條件是(tail + 1) = head，當(dāng)tail + 1 > 8 時(shí)，tail + 1 = 0。而這個(gè)操作可以用（tail + 1）對(duì) 8 取模來完成，即隊(duì)列滿的條件是 (tail + 1) % 8 = head。
阻塞隊(duì)列
??阻塞隊(duì)列其實(shí)就是在隊(duì)列基礎(chǔ)上增加了阻塞操作。簡(jiǎn)單來說，就是在隊(duì)列為空的時(shí)候，從隊(duì)頭取數(shù)據(jù)會(huì)被阻塞。因?yàn)榇藭r(shí)還沒有數(shù)據(jù)可取，直到隊(duì)列中有了數(shù)據(jù)才能返回；如果隊(duì)列已經(jīng)滿了，那么插入數(shù)據(jù)的操作就會(huì)被阻塞，直到隊(duì)列中有空閑位置后再插入數(shù)據(jù)，然后再返回。
并發(fā)隊(duì)列
??線程安全的隊(duì)列我們叫作并發(fā)隊(duì)列。最簡(jiǎn)單直接的實(shí)現(xiàn)方式是直接在 enqueue()、dequeue() 方法上加鎖，但是鎖粒度大并發(fā)度會(huì)比較低，同一時(shí)刻僅允許一個(gè)存或者取操作。實(shí)際上，基于數(shù)組的循環(huán)隊(duì)列，利用 CAS 原子操作，可以實(shí)現(xiàn)非常高效的并發(fā)隊(duì)列。這也是循環(huán)隊(duì)列比鏈?zhǔn)疥?duì)列應(yīng)用更加廣泛的原因。在實(shí)戰(zhàn)篇講 Disruptor 的時(shí)候，我會(huì)再詳細(xì)講并發(fā)隊(duì)列的應(yīng)用。文章來源：http://www.zghlxwxcb.cn/news/detail-531015.html
總結(jié)
??隊(duì)列最大的特點(diǎn)就是先進(jìn)先出，主要的兩個(gè)操作是入隊(duì)和出隊(duì)。跟棧一樣，它既可以用數(shù)組來實(shí)現(xiàn)，也可以用鏈表來實(shí)現(xiàn)。用數(shù)組實(shí)現(xiàn)的叫順序隊(duì)列，用鏈表實(shí)現(xiàn)的叫鏈?zhǔn)疥?duì)列。特別是長(zhǎng)得像一個(gè)環(huán)的循環(huán)隊(duì)列。在數(shù)組實(shí)現(xiàn)隊(duì)列的時(shí)候，會(huì)有數(shù)據(jù)搬移操作，要想解決數(shù)據(jù)搬移的問題，我們就需要像環(huán)一樣的循環(huán)隊(duì)列。文章來源地址http://www.zghlxwxcb.cn/news/detail-531015.html
到了這里，關(guān)于算法與數(shù)據(jù)結(jié)構(gòu)-隊(duì)列的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
