如何理解“隊列”？
特點
- 先進先出寇损，后進后出
- “操作受限”的線性表川陆，隊列尾部插入辜限，隊列頭部刪除
順序隊列和鏈?zhǔn)疥犃?/h1>
- 順序隊列:數(shù)組實現(xiàn)的隊列
- 鏈?zhǔn)疥犃?鏈表實現(xiàn)的隊列
順序隊列
// 用數(shù)組實現(xiàn)的隊列
public class ArrayQueue {
// 數(shù)組：items，數(shù)組大星钏薄：n
private String[] items;
private int n = 0;
// head表示隊頭下標(biāo)逻翁，tail表示隊尾下標(biāo)
private int head = 0;
private int tail = 0;
// 申請一個大小為capacity的數(shù)組
public ArrayQueue(int capacity) {
items = new String[capacity];
n = capacity;
}
// 入隊
public boolean enqueue(String item) {
// 如果tail == n 表示隊列已經(jīng)滿了
if (tail == n) return false;
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)隊列
數(shù)組實現(xiàn)
// 用數(shù)組實現(xiàn)的隊列
public class ArrayQueue {
// 數(shù)組：items，數(shù)組大星钏薄：n
private String[] items;
private int n = 0;
// head表示隊頭下標(biāo)逻翁，tail表示隊尾下標(biāo)
private int head = 0;
private int tail = 0;
// 申請一個大小為capacity的數(shù)組
public ArrayQueue(int capacity) {
items = new String[capacity];
n = capacity;
}
// 入隊
public boolean enqueue(String item) {
// 如果tail == n 表示隊列已經(jīng)滿了
if (tail == n) return false;
items[tail] = item;
++tail;
return true;
}
// 出隊
public String dequeue() {
// 如果head == tail 表示隊列為空
if (head == tail) return null;
// 為了讓其他語言的同學(xué)看的更加明確，把--操作放到單獨一行來寫了
String ret = items[head];
++head;
return ret;
}
}
原本數(shù)組是有頭有尾的捡鱼，是一條直線八回。把首尾相連，形成一個環(huán)驾诈。
public class CircularQueue {
// 數(shù)組：items缠诅，數(shù)組大小：n
private String[] items;
private int n = 0;
// head表示隊頭下標(biāo)乍迄，tail表示隊尾下標(biāo)
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ǔ)上增加了阻塞操作管引。當(dāng)隊列為空時，從隊列頭部取數(shù)據(jù)會被阻塞闯两；當(dāng)隊列已滿時褥伴，那么插入數(shù)據(jù)的操作就會被阻塞谅将。
并發(fā)隊列
并發(fā)隊列就是隊列的操作多線程安全。
