1. 什么是隊列蛙紫？
隊列的特點是先進(jìn)先出，有兩個基本操作：入隊（enqueue）途戒，放一個數(shù)據(jù)到隊列尾部坑傅；出隊（dequeue），從隊列頭部取一個元素棺滞。裁蚁。它和棧一樣矢渊，也是一種操作受限的線形表數(shù)據(jù)結(jié)構(gòu)继准。
隊列的應(yīng)用非常廣泛，特別是一些具有某些額外特性的隊列矮男，比如循環(huán)隊列移必、阻塞隊列、并發(fā)隊列毡鉴。它們在很多偏底層系統(tǒng)崔泵、框架、中間件的開發(fā)中猪瞬，起著關(guān)鍵性的作用憎瘸。
2. 如何實現(xiàn)隊列？
跟棧一樣陈瘦，隊列可以用數(shù)組來實現(xiàn)幌甘，也可以用鏈表來實現(xiàn)。用數(shù)組實現(xiàn)的隊列叫作順序隊列，用鏈表實現(xiàn)的隊列叫作鏈?zhǔn)疥犃?/strong>锅风。
使用數(shù)組實現(xiàn)的隊列：
public class QueueByArray<E> {
private int size;
private E[] data;
private int head;
private int tail;
public QueueByArray() {
this(8);
}
public QueueByArray(int size) {
data = (E[]) new Object[size];
this.size = size;
}
/**
* 入隊
*
* @param element
* @return
*/
public boolean enqueue(E element) {
// 隊尾沒有空間
if (tail == size) {
// 隊列已滿
if (head == 0) {
return false;
}
System.out.println("move element, head " + head + ", tail " + tail);
// 移動元素酥诽，從尾部向首部搬移
for (int i = head; i < tail; i++) {
data[i - head] = data[i];
}
tail -= head;
head = 0;
}
data[tail++] = element;
return true;
}
/**
* 出隊
*
* @return
*/
public E dequeue() {
// 隊列為空
if (head == tail) {
return null;
}
return data[head++];
}
}
使用鏈表實現(xiàn)的隊列：
public class QueueByLink<E> {
private int size;
private Node head;
private Node tail;
/**
* 入隊
*
* @param element
*/
public void enqueue(E element) {
if (head == null) {
head = new Node();
head.element = element;
tail = head;
} else {
Node node = new Node();
node.element = element;
tail.next = node;
tail = node;
}
size++;
}
/**
* 出隊
*
* @return
*/
public E dequeue() {
if (head == null) {
return null;
}
E element = head.element;
head = head.next;
size--;
return element;
}
private class Node {
private E element;
private Node next;
}
}
3. 循環(huán)隊列
循環(huán)隊列像一個環(huán)，首尾相連皱埠，避免了數(shù)據(jù)移動肮帐。實現(xiàn)循環(huán)隊列的關(guān)鍵是，確定好隊空和隊滿的判定條件边器。當(dāng)隊滿時训枢，(tail+1)%n=head。
下面是使用數(shù)組實現(xiàn)循環(huán)隊列：
public class CircularQueue<E> {
// 容量
private int size;
private E[] data;
private int head;
private int tail;
public CircularQueue() {
this(8);
}
public CircularQueue(int size) {
data = (E[]) new Object[size];
this.size = size;
}
/**
* 入隊
*
* @param element
* @return
*/
public boolean enqueue(E element) {
// 隊列已滿
if ((tail + 1) % size == head) {
return false;
}
data[tail] = element;
tail = (tail + 1) % size;
return true;
}
/**
* 出隊
*
* @return
*/
public E dequeue() {
// 隊列為空
if (head == tail) {
return null;
}
E ele = data[head];
head = (head + 1) % size;
return ele;
}
}
4. 阻塞隊列和并發(fā)隊列
阻塞隊列就是在隊列基礎(chǔ)上增加了阻塞操作忘巧。簡單來說肮砾，就是在隊列為空的時候，從隊頭取數(shù)據(jù)會被阻塞袋坑。直到隊列中有了數(shù)據(jù)才能返回仗处；如果隊列已經(jīng)滿了，那么插入數(shù)據(jù)就會被阻塞枣宫，直到隊列中有空閑位置后再插入數(shù)據(jù)婆誓，然后再返回。這種基于阻塞隊列實現(xiàn)的“生產(chǎn)者 - 消費者模型”也颤，可以有效地協(xié)調(diào)生產(chǎn)和消費的速度洋幻。
線程安全的隊列我們叫作并發(fā)隊列。最簡單直接的實現(xiàn)方式是直接在 enqueue()翅娶、dequeue() 方法上加鎖文留，但是鎖粒度大并發(fā)度會比較低，同一時刻僅允許一個存或者取操作竭沫。實際上燥翅，基于數(shù)組的循環(huán)隊列，利用 CAS 原子操作蜕提，可以實現(xiàn)非常高效的并發(fā)隊列森书。這也是循環(huán)隊列比鏈?zhǔn)疥犃袘?yīng)用更加廣泛的原因。
線程池的阻塞隊列分為兩種：基于鏈表的實現(xiàn)方式谎势，可以實現(xiàn)一個支持無限排隊的無界隊列凛膏，但是可能會導(dǎo)致過多的請求排隊等待，請求處理的響應(yīng)時間過長脏榆。而基于數(shù)組實現(xiàn)的有界隊列猖毫，隊列的大小有限，所以線程池中排隊的請求超過隊列大小時须喂，接下來的請求就會被拒絕吁断，設(shè)置一個合理的隊列大小非常有講究典唇。
課后思考
還有哪些類似線程池結(jié)構(gòu)或者場景中會用到隊列的排隊請求呢？
