Java代碼手撕【數(shù)據(jù)結(jié)構(gòu)】| 隊(duì)列的實(shí)現(xiàn)與優(yōu)化指南
一、前言
隊(duì)列是一種重要的數(shù)據(jù)結(jié)構(gòu)，它按照“先入先出”（FIFO）的原則管理數(shù)據(jù)。本文將介紹隊(duì)列的概念、應(yīng)用場(chǎng)景，以及如何使用數(shù)組實(shí)現(xiàn)普通隊(duì)列和環(huán)形隊(duì)列。
二、內(nèi)容
2.1 概述
2.1.1什么是隊(duì)列？
隊(duì)列（Queue）是一種常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)，它是一個(gè)線(xiàn)性數(shù)據(jù)結(jié)構(gòu)，按照先入先出（FIFO，F(xiàn)irst-In-First-Out）的原則來(lái)管理數(shù)據(jù)。
注意，先入先出的原則就意味著最早進(jìn)入隊(duì)列的元素將最先被取出，而最后進(jìn)入隊(duì)列的元素將最后被取出，類(lèi)似于排隊(duì)等候服務(wù)的行為。
隊(duì)列可以使用數(shù)組或鏈表來(lái)實(shí)現(xiàn)，具體實(shí)現(xiàn)方式因應(yīng)用需求而異。
隊(duì)列支持兩種主要的操作，即入隊(duì)（Enqueue）和出隊(duì)（Dequeue）。
- 入隊(duì)：將元素添加到隊(duì)列的尾部。
- 出隊(duì)：從隊(duì)列的頭部取出元素并刪除它。
應(yīng)用場(chǎng)景
隊(duì)列的應(yīng)用場(chǎng)景有很多，比如：
- 任務(wù)調(diào)度：操作系統(tǒng)使用隊(duì)列來(lái)管理待執(zhí)行的任務(wù)或進(jìn)程，確保按照進(jìn)入隊(duì)列的順序分配處理時(shí)間。
- 數(shù)據(jù)緩沖：隊(duì)列用于數(shù)據(jù)傳輸和處理中，特別是在異步通信或生產(chǎn)者-消費(fèi)者模式中，可以緩沖待處理的數(shù)據(jù)。
- 廣度優(yōu)先搜索：在圖論和搜索算法中，隊(duì)列用于實(shí)現(xiàn)廣度優(yōu)先搜索，以逐層遍歷圖結(jié)構(gòu)。
- 打印任務(wù)隊(duì)列：打印機(jī)隊(duì)列用于管理待打印的文檔，確保按照順序打印。
- 網(wǎng)頁(yè)請(qǐng)求隊(duì)列：Web服務(wù)器可以使用隊(duì)列來(lái)處理收到的請(qǐng)求，以便有序響應(yīng)客戶(hù)端請(qǐng)求。
- 排隊(duì)系統(tǒng)：在銀行、餐館、醫(yī)院等場(chǎng)所，隊(duì)列被用來(lái)管理等待服務(wù)的客戶(hù)，確保服務(wù)按照先來(lái)先服務(wù)的原則。
- ......
隊(duì)列在計(jì)算機(jī)科學(xué)和實(shí)際應(yīng)用中非常有用，因?yàn)樗鼈兲峁┝艘环N有效的方法來(lái)管理和調(diào)度數(shù)據(jù)或任務(wù)，以確保按照特定的順序進(jìn)行處理。
2.2 數(shù)組模擬隊(duì)列
下面，我們用數(shù)組來(lái)模擬一個(gè)簡(jiǎn)單的隊(duì)列數(shù)據(jù)結(jié)構(gòu)。
2.2.1 隊(duì)列類(lèi)定義
首先給出類(lèi)的定義：
class ArrayQueue {
private int maxSize;
private int front;
private int rear;
private int[] data;
ArrayQueue(int queueMaxSize) {
maxSize = queueMaxSize; // 隊(duì)列的最大容量
data = new int[maxSize]; // 存放隊(duì)列的數(shù)據(jù)
front = -1; // 指向隊(duì)列頭的前一個(gè)位置
rear = -1; // 直接指向隊(duì)列尾部
}
// ... 方法定義
}在這里，ArrayQueue 是一個(gè)隊(duì)列類(lèi)，使用數(shù)組作為內(nèi)部數(shù)據(jù)存儲(chǔ)。它包括最大容量（maxSize）、隊(duì)列頭（front）、隊(duì)列尾（rear）和一個(gè)整數(shù)數(shù)組（data）來(lái)存放隊(duì)列的數(shù)據(jù)。
構(gòu)造函數(shù) ArrayQueue 接受一個(gè)整數(shù)參數(shù) queueMaxSize，表示隊(duì)列的最大容量。初始化時(shí)，隊(duì)列的頭（front）和尾都（rear）被置為-1，表示隊(duì)列為空。
需要注意這里的定義，在這里，front 變量指的是指向隊(duì)列首元素的前一個(gè)位置，而 rear 變量則指向隊(duì)列的尾部元素，即最后一個(gè)元素。
因此，初始隊(duì)列的結(jié)構(gòu)圖如下：
2.2.2 isEmpty
public boolean isEmpty() {
return rear == front;
}2.2.3 isFull
public boolean isFull() {
return rear == maxSize - 1;
}2.2.4 enQueue
// 入隊(duì)操作，添加數(shù)據(jù)到隊(duì)尾
public void enQueue(int num) {
if(isFull()) {
System.out.println("隊(duì)列已滿(mǎn)，無(wú)法入隊(duì)");
return;
}
rear++;
data[rear] = num;
}enQueue 方法用于將數(shù)據(jù)添加到隊(duì)列的尾部。首先，它會(huì)檢查隊(duì)列是否已滿(mǎn)，如果是，將輸出一條錯(cuò)誤消息并不執(zhí)行入隊(duì)操作。如果隊(duì)列未滿(mǎn)，將 rear 后移，然后將數(shù)據(jù)存入隊(duì)列尾部。
再次強(qiáng)調(diào)一下，這里的 rear 變量用于指向隊(duì)列的最后一個(gè)數(shù)據(jù)，即隊(duì)列的尾部。
2.2.5 deQueue
// 出隊(duì)操作，取出隊(duì)頭數(shù)據(jù)
public int deQueue() {
if(isEmpty()) {
throw new RuntimeException("隊(duì)列為空，無(wú)法出隊(duì)");
}
front++;
return data[front];
}deQueue 方法用于取出隊(duì)列頭部的數(shù)據(jù)。首先，它會(huì)檢查隊(duì)列是否為空，如果是，將拋出一個(gè)運(yùn)行時(shí)異常。如果隊(duì)列不為空，將 front 后移，然后返回隊(duì)頭的數(shù)據(jù)。
再次強(qiáng)調(diào)一下，這里的 front 變量指向的是隊(duì)列頭數(shù)據(jù)的前一個(gè)位置。
2.2.6 headQueue
// 查看隊(duì)頭數(shù)據(jù)（注意不是取出數(shù)據(jù)）
public int headQueue() {
if(isEmpty()) {
throw new RuntimeException("隊(duì)列為空，沒(méi)有數(shù)據(jù)");
}
return data[front+1];
}headQueue 方法用于獲取隊(duì)列頭部的數(shù)據(jù)，但不會(huì)將其出隊(duì)。它會(huì)檢查隊(duì)列是否為空，如果是，將拋出一個(gè)運(yùn)行時(shí)異常。如果隊(duì)列不為空，將返回隊(duì)頭的數(shù)據(jù)。
2.2.7 showQueue
// 打印隊(duì)列
public void showQueue() {
if(isEmpty()) {
System.out.println("隊(duì)列為空，沒(méi)有數(shù)據(jù)");
return;
}
// 簡(jiǎn)單的遍歷隊(duì)列
for(int i = 0; i < data.length; i++) {
System.out.printf("data[%d] = %d\n", i, data[i]);
}
}showQueue 方法用于簡(jiǎn)單地打印隊(duì)列的所有元素。如果隊(duì)列為空，將輸出一條消息表示隊(duì)列為空。否則，它會(huì)簡(jiǎn)單地遍歷隊(duì)列，打印每個(gè)數(shù)據(jù)元素的索引和值。
2.3 數(shù)組模擬環(huán)形隊(duì)列
存在的問(wèn)題
我們?cè)賮?lái)思考一個(gè)問(wèn)題，雖然上述的隊(duì)列類(lèi)實(shí)現(xiàn)了一個(gè)簡(jiǎn)單的隊(duì)列數(shù)據(jù)結(jié)構(gòu)，但仍然存在弊端。那就是數(shù)組使用一次后不能復(fù)用。
什么意思？
具體的，我們可以發(fā)現(xiàn)，每當(dāng)隊(duì)列入隊(duì)一個(gè)數(shù)據(jù)，rear 變量就會(huì)往后移一位。每當(dāng)有元素出隊(duì)，front 變量也會(huì)往后移一位。但是！一旦 rear 變量到達(dá)隊(duì)列的尾部，如果隊(duì)列頭部仍有空余的空間，就像這樣：
那么此時(shí)根據(jù) isFull() 方法的判斷下，該隊(duì)列是滿(mǎn)的。因此無(wú)法再入隊(duì)。
因此我們說(shuō)，對(duì)于之前的隊(duì)列簡(jiǎn)單實(shí)現(xiàn)來(lái)說(shuō)，一旦隊(duì)列中的數(shù)據(jù)元素被取出，對(duì)應(yīng)的數(shù)組位置就不能再次使用。數(shù)據(jù)從頭部添加，從尾部取出。一旦數(shù)組被填滿(mǎn)，我們無(wú)法再添加新的數(shù)據(jù)，即使隊(duì)列的前面已經(jīng)有一些位置被釋放出來(lái)。這就會(huì)導(dǎo)致內(nèi)存資源浪費(fèi)。
為了解決這個(gè)問(wèn)題，我們考慮使用環(huán)形隊(duì)列來(lái)優(yōu)化。
那什么是環(huán)形隊(duì)列？
事實(shí)上，環(huán)形隊(duì)列是一種更高效的隊(duì)列實(shí)現(xiàn)方式，它允許隊(duì)列在達(dá)到最大容量后繼續(xù)添加元素，以覆蓋掉隊(duì)列頭部已經(jīng)被取出的數(shù)據(jù)，實(shí)現(xiàn)數(shù)據(jù)的循環(huán)復(fù)用。
我們通過(guò)取模運(yùn)算 % 來(lái)實(shí)現(xiàn)環(huán)形隊(duì)列。
思路分析
當(dāng)我們考慮了隊(duì)列內(nèi)部數(shù)據(jù)存儲(chǔ)資源的復(fù)用后，我們就需要對(duì) front 和 rear 變量的含義進(jìn)行一個(gè)的調(diào)整（當(dāng)然不調(diào)整也行，看個(gè)人習(xí)慣）。
具體如下：
- front 變量： 表示指向隊(duì)列的第一個(gè)元素，即首元素。 data[front] 是隊(duì)列的第一個(gè)元素。 front的初始值為 0。
- rear 變量： 表示指向隊(duì)列最后一個(gè)元素的下一個(gè)位置。 這是為了表示隊(duì)列中哪些位置是可用的，以便繼續(xù)添加新的元素。 rear 的初始值同樣為 0。
當(dāng)我們這樣約定好了后，就可以開(kāi)始著手編寫(xiě)代碼，得到一個(gè)環(huán)形隊(duì)列。
此時(shí)判斷隊(duì)列已滿(mǎn)或空時(shí)，邏輯需要略微調(diào)整。
判斷環(huán)形隊(duì)列空時(shí)，條件為：(rear == front)。因?yàn)楫?dāng) rear 指針等于 front 指針時(shí)，表示隊(duì)列沒(méi)有有效的元素，即隊(duì)列為空。
判斷環(huán)形隊(duì)列滿(mǎn)時(shí)，條件為：(rear + 1) % maxSize == front
這該怎么理解？
事實(shí)上，在含義調(diào)整后，環(huán)形隊(duì)列中的 rear 變量指向的位置實(shí)際上就是預(yù)留給下次入隊(duì)的數(shù)據(jù)存放的位置。
當(dāng)有一個(gè)新的數(shù)據(jù)入隊(duì)時(shí)，rear 指向的位置就可以存儲(chǔ)本次入隊(duì)的數(shù)據(jù)的值，然后，rear 就會(huì)加一并取余 maxSize ，用于尋找下一個(gè)可以存儲(chǔ)入隊(duì)數(shù)據(jù)的位置。
因此，當(dāng)(rear + 1) % maxSize 的值剛好等于 front，那么證明該環(huán)形隊(duì)列已經(jīng)滿(mǎn)了，沒(méi)有地方可以存儲(chǔ)下一次入隊(duì)的值。
舉一個(gè)例子，假設(shè) maxSize 為 3，初始時(shí) front 和 rear 都是0：
- 隊(duì)列為空：front = 0, rear = 0
- 插入一個(gè)元素：front = 0, rear = 1
- 插入第二個(gè)元素：front = 0, rear = 2
- 插入第三個(gè)元素：front = 0, rear = 0（此時(shí)隊(duì)列滿(mǎn)，因?yàn)?(rear + 1) % maxSize 等于 front）
- 取出第一個(gè)元素：front = 1, rear = 0（此時(shí)隊(duì)列有效元素個(gè)數(shù)為 2，因?yàn)?(0+3-1) % 3 == 2）
示意圖如下：
優(yōu)化后的隊(duì)列類(lèi)
優(yōu)化后的代碼實(shí)現(xiàn)如下：
class CircleArrayQueue {
private int maxSize;
private int front; // 初始值為 0，指向隊(duì)頭數(shù)據(jù)，即首元素
private int rear; // 初始值為 0，指向隊(duì)尾數(shù)據(jù)的下一個(gè)位置
private int[] data;
ArrayQueue(int queueMaxSize) {
maxSize = queueMaxSize;
data = new int[maxSize];
}
// 判斷隊(duì)列是否為空
public boolean isEmpty() {
return rear == front;
}
// 判斷隊(duì)列是否滿(mǎn)
public boolean isFull() {
return (rear + 1) % maxSize == front;
}
// 入隊(duì)：添加數(shù)據(jù)到隊(duì)尾
public void enQueue(int num) {
if(isFull()) {
System.out.println("隊(duì)列已滿(mǎn)，無(wú)法入隊(duì)");
return;
}
data[rear] = num;
rear = (rear + 1) % maxSize;
}
// 出隊(duì)，取出隊(duì)頭數(shù)據(jù)
public int deQueue() {
if(isEmpty()) {
throw new RuntimeException("隊(duì)列為空，無(wú)法出隊(duì)");
}
int value = data[front];
front = (front + 1) % maxSize;
return value;
}
// 顯示隊(duì)列的頭數(shù)據(jù)（不是取出數(shù)據(jù)）
public int headQueue() {
if(isEmpty()) {
throw new RuntimeException("隊(duì)列為空，沒(méi)有數(shù)據(jù)");
}
return data[front];
}
// 返回環(huán)形隊(duì)列當(dāng)前的元素個(gè)數(shù)
public int size() {
return (rear + maxSize - front) % maxSize;
}
// 打印隊(duì)列
public void showQueue() {
if(isEmpty()) {
System.out.println("隊(duì)列為空，沒(méi)有數(shù)據(jù)");
return;
}
// 遍歷思路，從 data[front] 遍歷到 data[front + size]
for(int i = front; i < front + size(); i++) {
System.out.printf("data[%d] = %d\n", i%maxSize, data[i%maxSize]);
}
}
}三、總結(jié)
本文詳細(xì)介紹了隊(duì)列數(shù)據(jù)結(jié)構(gòu)的概念和應(yīng)用，包括普通隊(duì)列和環(huán)形隊(duì)列的實(shí)現(xiàn)。隊(duì)列是一種有序的數(shù)據(jù)結(jié)構(gòu)，它在計(jì)算機(jī)科學(xué)中被廣泛應(yīng)用，用于管理數(shù)據(jù)和任務(wù)的順序執(zhí)行。普通隊(duì)列使用數(shù)組實(shí)現(xiàn)，但存在內(nèi)存資源浪費(fèi)的問(wèn)題。為了解決這個(gè)問(wèn)題，我們引入了環(huán)形隊(duì)列的概念，它允許隊(duì)列數(shù)據(jù)的循環(huán)復(fù)用，更加高效地利用內(nèi)存。
