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