隊列的理解
隊列是一種受限的線性表數(shù)據(jù)結(jié)構(gòu),它的主要特點就是先進先出.隊列的基本操作有兩個,入隊(enqueue)和出隊(dequeue).
實現(xiàn)一個隊列需要兩個指針,一個head指向隊頭,一個tail指向隊尾.
當(dāng)出隊和入隊的時候head指針持續(xù)的向后移動.
當(dāng)tail移動到最右邊,即使隊列中還有還有空閑的空間也無法向其中添加數(shù)據(jù)了,這個時候就需要進行數(shù)據(jù)搬移.
隊列的實現(xiàn)方式
隊列可以用數(shù)組實現(xiàn),叫做順序隊列.也可以用鏈表實現(xiàn),叫做鏈式隊列.
順序隊列的實現(xiàn)代碼
// 用數(shù)組實現(xiàn)的隊列
public class ArrayQueue {
// 數(shù)組：items趁舀，數(shù)組大小：n
private String[] items;
private int n = 0;
// head表示隊頭下標，tail表示隊尾下標
private int head = 0;
private int tail = 0;
// 申請一個大小為capacity的數(shù)組
public ArrayQueue(int capacity) {
items = new String[capacity];
n = capacity;
}
// 入隊操作岩喷，將item放入隊尾
public boolean enqueue(String item) {
// tail == n表示隊列末尾沒有空間了
if (tail == n) {
// tail ==n && head==0呆奕，表示整個隊列都占滿了
if (head == 0) return false;
// 數(shù)據(jù)搬移
for (int i = head; i < tail; ++i) {
items[i-head] = items[i];
}
// 搬移完之后重新更新head和tail
tail -= head;
head = 0;
}
items[tail] = item;
++tail;
return true;
}
// 出隊
public String dequeue() {
// 如果head == tail 表示隊列為空
if (head == tail) return null;
// 為了讓其他語言的同學(xué)看的更加明確啰脚，把--操作放到單獨一行來寫了
String ret = items[head];
++head;
return ret;
}
}
循環(huán)隊列
循環(huán)隊列就像一個環(huán)一樣,把本來的一條直線變?yōu)榱耸孜蚕噙B,
我們可以看到效扫，圖中這個隊列的大小為 8看幼，當(dāng)前 head=4展懈，tail=7销睁。當(dāng)有一個新的元素 a 入隊時，我們放入下標為 7 的位置存崖。但這個時候冻记，我們并不把 tail 更新為 8，而是將其在環(huán)中后移一位来惧，到下標為 0 的位置冗栗。當(dāng)再有一個元素 b 入隊時，我們將 b 放入下標為 0 的位置供搀，然后 tail 加 1 更新為 1隅居。所以，在 a葛虐，b 依次入隊之后胎源，循環(huán)隊列中的元素就變成了下面的樣子：
隊滿的判斷條件
(tail+1)%n = head
又上圖可以看出循環(huán)隊列隊滿的時候tail位置也是沒有數(shù)據(jù)的,說明循環(huán)隊列會浪費一個存儲空間.
循環(huán)隊列的實現(xiàn)
public class CircularQueue {
// 數(shù)組：items，數(shù)組大杏炱辍：n
private String[] items;
private int n = 0;
// head表示隊頭下標涕蚤，tail表示隊尾下標
private int head = 0;
private int tail = 0;
// 申請一個大小為capacity的數(shù)組
public CircularQueue(int capacity) {
items = new String[capacity];
n = capacity;
}
// 入隊
public boolean enqueue(String item) {
// 隊列滿了
if ((tail + 1) % n == head) return false;
items[tail] = item;
tail = (tail + 1) % n;
return true;
}
// 出隊
public String dequeue() {
// 如果head == tail 表示隊列為空
if (head == tail) return null;
String ret = items[head];
head = (head + 1) % n;
return ret;
}
}
阻塞隊列
其實就是在隊列基礎(chǔ)上增加了阻塞操作。簡單來說的诵，就是在隊列為空的時候万栅，從隊頭取數(shù)據(jù)會被阻塞。因為此時還沒有數(shù)據(jù)可取奢驯，直到隊列中有了數(shù)據(jù)才能返回申钩；如果隊列已經(jīng)滿了，那么插入數(shù)據(jù)的操作就會被阻塞瘪阁，直到隊列中有空閑位置后再插入數(shù)據(jù)撒遣，然后再返回。
并發(fā)隊列
并發(fā)隊列就是隊列的操作多線程安全管跺。
練習(xí):隊列
ps:內(nèi)容整理自極客時間--數(shù)據(jù)結(jié)構(gòu)與算法之美
