定義
有一定的業(yè)務(wù)需求就會(huì)有對(duì)應(yīng)的技術(shù)或數(shù)據(jù)結(jié)構(gòu)產(chǎn)生精耐。我們都知道 CPU 的資源是有限的朴读，任務(wù)的處理速度與線程個(gè)數(shù)并不是線性正相關(guān)作煌。相反過多的線程反而會(huì)導(dǎo)致 CPU 頻繁切換，處理性能下降汁雷。所以線程池的大小一般都是綜合考慮處理任務(wù)的特點(diǎn)和硬件環(huán)境苔悦，來事先設(shè)置的轩褐。
隊(duì)列的特點(diǎn) 先進(jìn)先出，可以想象成排隊(duì)買票玖详，先來的先買把介。最基本的操作就是 入隊(duì)和出隊(duì)，所以隊(duì)列跟棧一樣蟋座，也是一種 操作受限的線性數(shù)據(jù)結(jié)構(gòu)拗踢。
實(shí)現(xiàn)
類似棧，可以通過數(shù)組和鏈表試下向臀，數(shù)組實(shí)現(xiàn)的隊(duì)列叫做 順序隊(duì)列巢墅，鏈表實(shí)現(xiàn)的隊(duì)列叫做 鏈?zhǔn)疥?duì)列。
順序隊(duì)列
核心思想在于，使用兩個(gè)下標(biāo)保存頭部和尾部的數(shù)據(jù)君纫，也可以當(dāng)成標(biāo)識(shí)驯遇。因?yàn)槿腙?duì)是從屁股進(jìn)行插入，出隊(duì)是從頭部拿出數(shù)據(jù)蓄髓，因此要記住頭尾的位置叉庐。
先來看一下簡(jiǎn)單的實(shí)現(xiàn)方式：
class ArrayQueue<T> {
T[] items;
int head;
int tail;
int count;
ArrayQueue(int capacity) {
items = (T[]) new Object[capacity];
count = capacity;
}
boolean enqueue(T t) {
if (tail == count) return false;
items[tail] = t;
tail ++;
print("enqueue");
return true;
}
T dequeue() {
if (head == tail) return null;
T t= items[head];
items[head] = null;
head ++;
print("dequeue");
return t;
}
void print(String mode) {
System.out.println("mode:\t" + mode + " head:\t" + head + " tail:\t" + tail);
for (int i = head; i < tail; i++) {
System.out.print(items[i] + "");
}
System.out.println();
}
public static void main(String[] args) {
ArrayQueue<String> queue = new ArrayQueue<String>(6);
queue.enqueue("1");
queue.enqueue("2");
queue.enqueue("3");
queue.dequeue();
queue.dequeue();
queue.dequeue();
queue.enqueue("5");
queue.enqueue("6");
}
}
運(yùn)行結(jié)果：
mode: enqueue head: 0 tail: 1
1
mode: enqueue head: 0 tail: 2
12
mode: enqueue head: 0 tail: 3
123
mode: dequeue head: 1 tail: 3
23
mode: dequeue head: 2 tail: 3
3
mode: dequeue head: 3 tail: 3
mode: enqueue head: 3 tail: 4
5
mode: enqueue head: 3 tail: 5
56
上述實(shí)現(xiàn)的方式有一個(gè)弊端，當(dāng) tail == n 的時(shí)候会喝，就不能繼續(xù)插入數(shù)據(jù)陡叠，但是此時(shí)容器并沒有裝滿，只是不能繼續(xù)往后插入數(shù)據(jù)了肢执。那這個(gè)時(shí)候就需要對(duì)容器進(jìn)行改變：數(shù)據(jù)搬移匾竿。單并不是每次入隊(duì)都需要遷移，為了優(yōu)化時(shí)間復(fù)雜度蔚万，可以在每次尾節(jié)點(diǎn)到達(dá)終點(diǎn)時(shí)岭妖，再開始數(shù)據(jù)搬移，即數(shù)據(jù)往前移動(dòng) head 的位置反璃。
來看一下實(shí)現(xiàn)方式：
class DynamicArrayQueue<T> {
T[] items;
int head;
int tail;
int count;
DynamicArrayQueue(int capacity) {
items = (T[]) new Object[capacity];
count = capacity;
}
boolean enqueue(T t) {
if (tail == count) {
if (head == 0) return false;
for (int i = head; i < tail; i++) {
items[i - head] = items[i];
}
tail -= head;
head = 0;
}
items[tail] = t;
tail ++;
print("enqueue");
return true;
}
T dequeue() {
if (head == tail) return null;
T t = items[head];
items[head] = null;
head ++;
print("new dequeue");
return t;
}
void print(String mode) {
System.out.println("mode:\t" + mode + " head:\t" + head + " tail:\t" + tail);
for (int i = head; i < tail; i++) {
System.out.print(items[i] + "");
}
System.out.println();
System.out.println(Arrays.toString(items));
}
public static void main(String[] args) {
DynamicArrayQueue<String> queue = new DynamicArrayQueue<String>(4);
queue.enqueue("1");
queue.enqueue("2");
queue.enqueue("3");
queue.enqueue("4");
queue.dequeue();
queue.dequeue();
queue.enqueue("5");
queue.enqueue("6");
}
}
結(jié)果：
mode: enqueue head: 0 tail: 1
1
[1, null, null, null]
mode: enqueue head: 0 tail: 2
12
[1, 2, null, null]
mode: enqueue head: 0 tail: 3
123
[1, 2, 3, null]
mode: enqueue head: 0 tail: 4
1234
[1, 2, 3, 4]
mode: new dequeue head: 1 tail: 4
234
[null, 2, 3, 4]
mode: new dequeue head: 2 tail: 4
34
[null, null, 3, 4]
mode: enqueue head: 0 tail: 3
345
[3, 4, 5, 4]
mode: enqueue head: 0 tail: 4
3456
[3, 4, 5, 6]
mode: new dequeue head: 1 tail: 4
456
[null, 4, 5, 6]
mode: enqueue head: 0 tail: 4
4567
[4, 5, 6, 7]
想比較之前的實(shí)現(xiàn)昵慌，出隊(duì)的邏輯并沒有任何的改變，在入隊(duì)是淮蜈，需要判斷 tail == 0斋攀，如果達(dá)到這個(gè)條件則可能需要進(jìn)行數(shù)據(jù)搬移。
鏈?zhǔn)疥?duì)列
思路其實(shí)類似于順序隊(duì)列的實(shí)現(xiàn)邏輯梧田。
class LinkedQueue<T> {
Node<T> head = null;
Node<T> tail = null;
void enqueue(T t) {
if (tail == null) {
Node<T> node = new Node<T>(t, null);
head = node;
tail = node;
} else {
tail.next = new Node<T>(t, null);
tail = tail.next;
}
System.out.println(head.toString());
}
T dequeue() {
if (head == null) return null;
T t = head.value;
head = head.next;
if (head == null) {
tail = null;
}
System.out.println(head == null ? "null" : head.toString());
return t;
}
public static void main(String[] args) {
LinkedQueue<String> queue = new LinkedQueue<String>();
queue.enqueue("1");
queue.enqueue("2");
queue.enqueue("3");
queue.dequeue();
queue.dequeue();
queue.enqueue("6");
}
}
運(yùn)行結(jié)果：
1
1 2
1 2 3
2 3
3
3 6
需要注意的是：
- 入隊(duì)的時(shí)候淳蔼，需要考慮隊(duì)列無數(shù)據(jù)的情況
- 出隊(duì)的時(shí)候，需要考慮出隊(duì)到最后尾節(jié)點(diǎn)的處理
循環(huán)隊(duì)列
之前在用數(shù)組實(shí)現(xiàn)隊(duì)列時(shí)裁眯，在 tail == n 時(shí)會(huì)有數(shù)據(jù)搬移的操作鹉梨，這樣入隊(duì)操作性能就會(huì)收到影響，我們可以使用循環(huán)隊(duì)列來解決這個(gè)問題穿稳。
循環(huán)隊(duì)列其實(shí)長(zhǎng)得像一個(gè)環(huán)存皂，現(xiàn)在需要將首尾相連變成一個(gè)環(huán)。
放三張圖感受一下逢艘，圖片來自于極客時(shí)間的課程旦袋。
從圖中可以發(fā)現(xiàn)規(guī)律，當(dāng) (tail + 1) % n = head 時(shí)它改，說明隊(duì)列已滿疤孕。
來看一下代碼的具體實(shí)現(xiàn)方式：
class CircularQueue {
// 數(shù)組：items，數(shù)組大醒胪稀：n
private String[] items;
private int n = 0;
// head表示隊(duì)頭下標(biāo)祭阀，tail表示隊(duì)尾下標(biāo)
private int head = 0;
private int tail = 0;
// 申請(qǐng)一個(gè)大小為capacity的數(shù)組
public CircularQueue(int capacity) {
items = new String[capacity + 1];
n = capacity + 1;
}
// 入隊(duì)
public boolean enqueue(String item) {
// 隊(duì)列滿了
if ((tail + 1) % n == head) return false;
items[tail] = item;
tail = (tail + 1) % n;
return true;
}
// 出隊(duì)
public String dequeue() {
// 如果head == tail 表示隊(duì)列為空
if (head == tail) return null;
String ret = items[head];
head = (head + 1) % n;
return ret;
}
public void printAll() {
if (0 == n) return;
for (int i = head; i % n != tail; ++i) {
System.out.print(items[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
CircularQueue queue = new CircularQueue(5);
queue.enqueue("1");
queue.enqueue("2");
queue.enqueue("3");
queue.enqueue("4");
queue.printAll();
queue.dequeue();
queue.printAll();
queue.enqueue("5");
queue.enqueue("6");
queue.printAll();
}
}
運(yùn)行結(jié)果：
1 2 3 4
2 3 4
2 3 4 5 6
參考自極客時(shí)間
