重溫：數(shù)據(jù)結(jié)構(gòu)與算法 - 開篇
重溫：數(shù)據(jù)結(jié)構(gòu)與算法 - 復(fù)雜度分析(一)
重溫：數(shù)據(jù)結(jié)構(gòu)與算法 - 復(fù)雜度分析(二)
重溫：數(shù)據(jù)結(jié)構(gòu)與算法 - 數(shù)組
重溫：數(shù)據(jù)結(jié)構(gòu)與算法 - 鏈表(一)
重溫：數(shù)據(jù)結(jié)構(gòu)與算法 - 鏈表(二)
重溫：數(shù)據(jù)結(jié)構(gòu)與算法 - 棧
叨叨兩句
最近提了離職，給公司找交接人也面試了不少人，上次作為面試官還是兩年前事情;
最大感受大環(huán)境還是太過浮躁，五年前如此，今亦是如此，福報996，中年危機(jī)，卷王爭霸，各種負(fù)面信息纏繞在周圍;
作為個人，沒資格去評論他人的職業(yè)規(guī)劃，給他人灌輸雞湯，更是害人不淺。僅告誡自己：靜心、學(xué)習(xí)、自省、前行。
什么是隊列
言歸正傳，本章介紹另一種“操作受限”的線性表數(shù)據(jù)結(jié)構(gòu)：隊列。
與棧結(jié)構(gòu)相同，它僅支持添加和刪除操作：
- 添加操作（入隊 - enqueue）
- 刪除操作（出隊 - dequeue）
不同點(diǎn)在于與棧的先進(jìn)后出相反，它具有"先進(jìn)先出"特性：
圖中，排隊買票就是典型的隊列結(jié)構(gòu)，先排隊的人優(yōu)先買到票。
我們把入隊操作稱之"enqueue()"，出隊操作則為"dequeue()",一個簡單的隊列操作約束大致如下：
// 隊列基本操作約束接口
public interface Queue<T> {
// 入隊
boolean enqueue(T item);
// 出隊
T dequeue();
// 是否為空
boolean isEmpty();
// 隊中數(shù)據(jù)的數(shù)量
int size();
// 清空
void clear();
}
一個滿足先進(jìn)先出的隊列容器，其關(guān)鍵在于enqueue() 和 dequeue()函數(shù)的實(shí)現(xiàn)上，而基礎(chǔ)容器的選擇同上篇的棧結(jié)構(gòu)一樣，使用數(shù)組或者鏈表都可以，使用數(shù)組實(shí)現(xiàn)隊列稱之：順序隊列，使用鏈表實(shí)現(xiàn)則為：鏈?zhǔn)疥犃?/strong>。 以下是以數(shù)組實(shí)現(xiàn)順序隊列的思路，大家不妨看看： 順序隊列： 1、定義一個items[]數(shù)組來存儲數(shù)據(jù)； 2、定義一個head指針和tail指針，分別指向當(dāng)前隊列的首下標(biāo)和尾下標(biāo)； 3、入隊操作enqueue()中，校驗隊列是否已滿： 4、出隊操作dequeue()中，校驗隊列是否已空： 按照這個思路，我把實(shí)現(xiàn)代碼貼在了下方： 測試一下： 輸出： 通過測試，我們創(chuàng)建了一個大小為3的隊列，并一口氣增加了5個元素，因隊列只能容納3個元素，后續(xù)添加的4、5元素都失敗了；緊接出隊兩個元素1、2，隊列最終只剩下元素3，滿足隊列的先進(jìn)先出原則。 然而，當(dāng)我想嘗試?yán)^續(xù)添加元素6時，卻失敗了！隊列當(dāng)前大小依舊是1，但我們知道隊列總大小明明是3，卻不能繼續(xù)向隊列添加數(shù)據(jù)，顯然這并不是我想要的結(jié)果，通過下圖我們可以看到原因： 當(dāng)我們在第一步入隊操作后，tail指針就已到隊尾，無論第二步出隊多少個元素，tail指針始終沒有被重置，顯然這是導(dǎo)致此問題的根本原因。 如何解決？ 按照上面思路，的確解決了問題，不過每次出隊都需要進(jìn)行一次數(shù)據(jù)搬移，這使得dequeue()函數(shù)時間復(fù)雜度由原先的 O(1) --》O(n). 有沒有更好的方案？ 已上圖為例，當(dāng)執(zhí)行第三步時，tail指針指向隊尾，但head指針并不在隊首，那么將3搬移至下標(biāo)為0的位置，重置head、tail指針位置，再入隊元素6，按照這個思路修改enqueue()函數(shù)如下： 修改后的enqueue()函數(shù)時間復(fù)雜度，又是多少呢？分析如下： OK，接下來學(xué)習(xí)鏈?zhǔn)疥犃校?br>
鏈?zhǔn)疥犃邢噍^順序隊列簡單很多，不需關(guān)心存儲空間不夠，或數(shù)據(jù)搬移問題。 鏈?zhǔn)疥犃校?/p>
測試： 輸出： 可以看到鏈?zhǔn)疥犃?，無論是入隊enqueue()還是出隊dequeue()，都可通過指針直接訪問到對應(yīng)結(jié)點(diǎn)，所以鏈?zhǔn)疥犃械某鲫犎腙爼r間復(fù)雜度都是：O(1) 前面提到，在內(nèi)存資源有限的場景下，推薦使用順序隊列，反之可使用鏈?zhǔn)疥犃?。如果在有限資源下，又希望能擁有像鏈?zhǔn)疥犃幸粯痈咝У娜腙牪僮?，這樣的隊列能否實(shí)現(xiàn)？ 如圖所示，我們將數(shù)組的首尾相連： 測試： 輸出： 由于入隊enqueue()、出隊dequeue()分別對tail指針和head指針進(jìn)行了糾正，不再會出現(xiàn)數(shù)據(jù)搬移的情況，其時間復(fù)雜度都為：O(1).
對于資源限制嚴(yán)謹(jǐn)?shù)膱鼍跋峦扑]使用順序隊列，而對資源限制沒有要求，僅需先進(jìn)后出特性的場景可使用鏈?zhǔn)疥犃小?/p>
順序隊列（數(shù)組）
public class ArrayQueue<T> implements Queue<T> {
private static final int DEFAULT_SIZE = 10;
// 隊列中數(shù)據(jù)數(shù)量
private int count;
private Object[] items;
// 當(dāng)前隊列能存儲的最大容量
private int maxSize;
// head指向隊首下標(biāo) ， tail指向隊尾下標(biāo)
private int head = 0, tail = 0;
public ArrayQueue() {
this(DEFAULT_SIZE);
}
public ArrayQueue(int intSize) {
items = new Object[intSize];
this.maxSize = intSize;
}
@Override
public boolean enqueue(T item) {
// 隊列滿了，存儲失敗
if (tail == maxSize) return false;
// 存儲，隊尾下標(biāo)后移一位
items[tail] = item;
++tail;
++count;
return true;
}
@Override
public T dequeue() {
// 隊空，返回null
if (isEmpty()) return null;
// 取出數(shù)據(jù)，隊首下標(biāo)后移一位
Object item = items[head];
++head;
--count;
return (T) item;
}
@Override
public boolean isEmpty() {
return count == 0;
}
@Override
public int size() {
return count;
}
@Override
public void clear() {
if (isEmpty()) return;
for (int i = 0; i < size(); i++) {
items[i] = null;
}
count = 0;
}
public void print() {
for (int i = head; i < tail; i++) {
System.out.print(items[i] + "\t");
}
System.out.println();
}
}
ArrayQueue<String> queue = new ArrayQueue<>(3);
queue.enqueue("1");
queue.enqueue("2");
queue.enqueue("3");
queue.enqueue("4");
queue.enqueue("5");
queue.print();
String data1 = queue.dequeue();
System.out.println("出隊：" + data1);
String data2 = queue.dequeue();
System.out.println("出隊：" + data2);
queue.print();
System.out.println("大?。? + queue.size());
// 問題：隊列有空閑空間卻無法添加數(shù)據(jù)
System.out.println(queue.enqueue("6"));
queue.print();
System.out.println("大?。? + queue.size());
1 2 3
出隊：1
出隊：2
3
大?。?
false
3
大小：1
數(shù)據(jù)搬移！沒錯，在數(shù)組章節(jié)提到過插入一個數(shù)據(jù)進(jìn)數(shù)組中，需要將插入位置及后面所有的數(shù)據(jù)都向后搬移一位；同理，當(dāng)隊列中隊首元素出隊時，將隊首之后的所有元素向前搬移一位，并將tail--，這樣就可以保證tail指針始終指向的是隊內(nèi)實(shí)際尾元素下標(biāo)，而不是隊列實(shí)際大小的尾下標(biāo)。
換個角度，來看看enqueue()入隊函數(shù)，還是上面問題，當(dāng)我們執(zhí)行第3步，入隊元素6時，由于tail指針指向了隊尾，入隊失敗。但通過上圖可以看到head指針前是存在空閑空間的，此時我們進(jìn)行數(shù)據(jù)搬移可否？ public boolean enqueue(T item) {
// 隊列到達(dá)末尾
if (tail == maxSize) {
// 隊列滿了，存儲失敗
if (head == 0) return false;
// 隊列頭部有空閑空間，進(jìn)行數(shù)據(jù)搬移
for (int i = head; i < tail; i++) {
items[i - head] = items[i];
}
// 修正head、tail下標(biāo)
tail = tail - head;
head = 0;
}
// 存儲，隊尾下標(biāo)向后移動一位
items[tail] = item;
++tail;
++count;
return true;
}
鏈?zhǔn)疥犃校ㄦ湵恚?/h3>
public class LinkedQueue<T> implements Queue<T> {
private Node<T> head, tail;
private int count = 0;
@Override
public boolean enqueue(T item) {
Node<T> newNode = new Node<>(item);
if (head == null) {
head = tail = newNode;
} else {
tail.next = newNode;
tail = tail.next;
}
count++;
return true;
}
@Override
public T dequeue() {
if (head == null) return null;
T item = head.data;
head = head.next;
count--;
return item;
}
@Override
public boolean isEmpty() {
return count == 0;
}
@Override
public int size() {
return count;
}
@Override
public void clear() {
head = null;
}
public void print() {
Node<T> temp = head;
while (temp != null) {
System.out.print(temp.data + "\t");
temp = temp.next;
}
System.out.println();
}
static class Node<T> {
public T data; // 存儲數(shù)據(jù)
public Node<T> next; // 下一個結(jié)點(diǎn)
public Node(T data) {
this.data = data;
}
}
}
LinkedQueue<String> queue = new LinkedQueue<>();
queue.enqueue("1");
queue.enqueue("2");
queue.enqueue("3");
queue.enqueue("4");
queue.enqueue("5");
queue.print();
System.out.println("出隊：" + queue.dequeue());
System.out.println("出隊：" + queue.dequeue());
System.out.println("出隊：" + queue.dequeue());
queue.print();
queue.enqueue("6");
queue.print();
出隊：1
出隊：2
出隊：3
4 5
4 5 6
進(jìn)階
循環(huán)隊列
/**
* 循環(huán)隊列
*/
public class CircularQueue<T> implements Queue<T> {
private static final int DEFAULT_SIZE = 10;
// 隊列中數(shù)據(jù)數(shù)量
private int count;
private Object[] items;
// 當(dāng)前隊列能存儲的最大容量
private int maxSize;
// head指向隊列頭部下標(biāo) ， tail指向尾部下標(biāo)
private int head = 0, tail = 0;
public CircularQueue() {
this(DEFAULT_SIZE);
}
public CircularQueue(int intSize) {
items = new Object[intSize];
this.maxSize = intSize;
}
@Override
public boolean enqueue(T item) {
// 隊滿
if (count == maxSize) return false;
// tail到達(dá)隊尾，
if (tail == maxSize) tail = 0;
// 存儲，隊尾下標(biāo)向后移動一位
items[tail] = item;
++tail;
++count;
return true;
}
@Override
public T dequeue() {
// 隊空，返回null
if (isEmpty()) return null;
// 取出數(shù)據(jù)，隊頭下標(biāo)向后移動一位
Object item = items[head];
head = (head + 1) % maxSize;
--count;
return (T) item;
}
@Override
public boolean isEmpty() {
return count == 0;
}
@Override
public int size() {
return count;
}
@Override
public void clear() {
if (isEmpty()) return;
for (int i = 0; i < size(); i++) {
items[i] = null;
}
count = 0;
}
public void print() {
for (int i = head, j = 0; j < count; i = (i + 1) % maxSize, j++) {
System.out.print(items[i] + "\t");
}
System.out.println();
}
}
CircularQueue<String> queue = new CircularQueue<>(5);
queue.enqueue("1");
queue.enqueue("2");
queue.enqueue("3");
queue.enqueue("4");
queue.enqueue("5");
queue.enqueue("6");
queue.print();
System.out.println("出隊：" + queue.dequeue());
System.out.println("出隊：" + queue.dequeue());
queue.print();
queue.enqueue("7");
queue.print();
1 2 3 4 5
出隊：1
出隊：2
3 4 5
3 4 5 7
