概念
隊(duì)列（queue）是一種特殊的線性表，特殊之處在于它只允許在表的前端（front）進(jìn)行刪除操作，而在表的后端（rear）進(jìn)行插入操作。
和棧一樣，隊(duì)列是一種操作受限制的線性表。隊(duì)列是先進(jìn)先出（FIFO）的。進(jìn)行插入操作的端稱為隊(duì)尾，進(jìn)行刪除操作的端稱為隊(duì)頭。
隊(duì)列和棧非常相似，棧有入棧和出棧兩個(gè)基本操作操作，隊(duì)列也有兩個(gè)基本操作：入隊(duì)（enqueue），把數(shù)據(jù)放到隊(duì)尾。出隊(duì)（dequeue）,從隊(duì)頭取出一個(gè)數(shù)據(jù)。
隊(duì)列出隊(duì)和入隊(duì)的時(shí)間復(fù)雜度都是O(1)。
順序隊(duì)列
用數(shù)組實(shí)現(xiàn)的隊(duì)列叫做順序隊(duì)列。
// 用數(shù)組實(shí)現(xiàn)的隊(duì)列
public class ArrayQueue {
// 數(shù)組：arr，數(shù)組大小：len
private String[] arr;
private int len = 0;
// front 隊(duì)頭下標(biāo)，rear 隊(duì)尾下標(biāo)
private int front = 0;
private int rear = 0;
// 創(chuàng)建一個(gè)數(shù)組
public ArrayQueue(int length) {
items = new String[length];
n = length;
}
// 入隊(duì)
public boolean enqueue(String item) {
// 隊(duì)列已滿
if (rear == len) return false;
items[rear] = item;
rear++;
return true;
}
// 出隊(duì)
public String dequeue() {
// 隊(duì)列為空
if (front == rear) return null;
String result = items[front];
front++;
return result;
}
}
隊(duì)列有兩個(gè)指針一個(gè)是front指向隊(duì)頭，一個(gè)是rear指向隊(duì)尾。
如a、b、c、d、e 入列后，隊(duì)頭指針指向是的下標(biāo)為0的位置，隊(duì)尾指針指向的是下標(biāo)為6的位置。
然后不斷進(jìn)行出列和入列的操作，兩個(gè)指針也不斷往后移動(dòng)，當(dāng)隊(duì)尾指針到達(dá)最右邊的位置，就算數(shù)組中還有一個(gè)空閑的空間，但也沒有辦法繼續(xù)向隊(duì)列中加數(shù)據(jù)了。
回想數(shù)組空間不足，進(jìn)行擴(kuò)容，遷移數(shù)據(jù)的操作。
同理在這里也要對(duì)隊(duì)列進(jìn)行數(shù)據(jù)搬遷，只要在入列的時(shí)候判斷一下 （rear == len ）隊(duì)列尾是已經(jīng)到最后的話就進(jìn)行數(shù)據(jù)遷移，然后重新計(jì)算兩個(gè)指針的指向，然后再入列就可以了。
鏈?zhǔn)疥?duì)列
用鏈表實(shí)現(xiàn)的隊(duì)列叫做鏈?zhǔn)疥?duì)列。同樣需要兩個(gè)指針，隊(duì)頭指向第一個(gè)節(jié)點(diǎn)，隊(duì)尾指向最后一個(gè)節(jié)點(diǎn)。
入隊(duì)：rear -> next = newnode , rear = rear -> next
出隊(duì)：front = front-> next
循環(huán)隊(duì)列
用數(shù)組實(shí)現(xiàn)隊(duì)列的時(shí)候，如果 rear == len ，就需要進(jìn)行數(shù)據(jù)遷移操作。
為了避免進(jìn)行數(shù)據(jù)遷移操作，可以用循環(huán)隊(duì)列來解決。
循環(huán)隊(duì)列首尾相接。
隊(duì)空條件：front == rear
隊(duì)滿條件：(rear + 1) % len = front
確定好上面的兩個(gè)條件，代碼實(shí)現(xiàn)就很容易了。
阻塞隊(duì)列
在隊(duì)列的基礎(chǔ)上增加了阻塞操作。
隊(duì)列為空，隊(duì)頭取數(shù)據(jù)阻塞，等隊(duì)列中有數(shù)據(jù)才會(huì)返回?cái)?shù)據(jù)。
隊(duì)列已滿，隊(duì)尾插數(shù)據(jù)阻塞，等隊(duì)列中有空閑位置再插入數(shù)據(jù)。
其實(shí)這就是「生產(chǎn)者 - 消費(fèi)者模型」，還可以通過配置多個(gè)「消費(fèi)者」來對(duì)應(yīng)一個(gè)「生產(chǎn)者」。
并發(fā)隊(duì)列
在多線程情況下，會(huì)有多個(gè)線程訪問隊(duì)列，會(huì)存在線程安全問題。
線程安全的隊(duì)列叫做并發(fā)隊(duì)列。
通過在 enqueue() 、dequeue() 加鎖來實(shí)現(xiàn)。
