隊列（Queue）是一種重要的線性數(shù)據(jù)結(jié)構(gòu)，遵循先進先出、后進后出的原則。本文將更詳細地介紹隊列的概念、特點、Java 實現(xiàn)以及應(yīng)用場景。

模運算小復(fù)習(xí)：

a % b 的值總是小于b

5 % 4 = 1? ?5?% 2 = 1

1 % 5 = 1? ?4 % 5 = 4

1. 隊列概念概述

想象一下排隊買票，先排隊的人總是先買到票。隊列就像這樣，元素從一端進入，稱為隊尾（Rear）或尾指針（tail），從另一端取出，稱為隊首（Front）或頭指針（head）。元素的添加操作稱為入隊（Enqueue）或加入隊列，刪除操作稱為出隊（Dequeue）或移出隊列。

隊列是一種抽象數(shù)據(jù)類型 (ADT)，這意味著我們只關(guān)心它的操作和特性，而不關(guān)心具體的實現(xiàn)方式。隊列的關(guān)鍵操作包括：

• enqueue(item):?將元素 item 添加到隊尾。

• dequeue():?移除并返回隊首元素。

• peek():?返回隊首元素，但不移除它。

• isEmpty():?檢查隊列是否為空。

• size(): 返回隊列中元素的數(shù)量 (部分實現(xiàn)可能不包含此方法，需要額外維護一個計數(shù)變量)。

2. 隊列的特點

• 先進先出 (FIFO):?這是隊列最核心的特點，最先入隊的元素總是最先出隊。

• 操作受限:?只能在隊尾入隊，在隊首出隊。這限制了訪問元素的靈活性，但也保證了操作的高效性 (時間復(fù)雜度通常為 O(1))。

3. 隊列的 Java 實現(xiàn)?

Java 中可以使用鏈表或環(huán)形數(shù)組實現(xiàn)隊列。

3.1 基于鏈表的實現(xiàn)

public class LinkedListQueue<T> {private Node<T> head; // 指向隊首節(jié)點的指針private Node<T> tail; // 指向隊尾節(jié)點的指針private int size; // 記錄隊列大小private static class Node<T> { // 鏈表節(jié)點的內(nèi)部類T data;Node<T> next;Node(T data) {this.data = data;}}public LinkedListQueue() {this.head = null;this.tail = null;this.size = 0;}public boolean isEmpty() {return size == 0; // 或 head == null}public int size() {return size;}//入隊public void enqueue(T item) {Node<T> newNode = new Node<>(item);if (isEmpty()) {head = newNode; // 如果隊列為空，新節(jié)點既是隊首也是隊尾} else {tail.next = newNode; // 否則，將新節(jié)點添加到隊尾}tail = newNode; // 更新隊尾指針size++;}//出隊public T dequeue() {if (isEmpty()) {throw new NoSuchElementException("Queue is empty"); // 使用更具體的異常類型}T data = head.data;head = head.next; // 更新隊首指針if (head == null) { // 如果隊列只有一個元素，出隊后隊列變空，tail 也需要置空tail = null;}size--;return data;}//返回隊首元素public T peek() {if (isEmpty()) {throw new NoSuchElementException("Queue is empty");}return head.data;}
}

3.2 基于環(huán)形數(shù)組的實現(xiàn)?

好處

• 對比普通數(shù)組，起點和終點更為自由，不用考慮數(shù)據(jù)移動

• “環(huán)”意味著不會存在【越界】問題

• 數(shù)組性能更佳

• 環(huán)形數(shù)組比較適合實現(xiàn)有界隊列、RingBuffer 等

public class ArrayQueue<T> {private T[] data;private int head; // 隊首指針private int tail; // 隊尾指針private int capacity; // 數(shù)組容量private int size; // 隊列大小public ArrayQueue(int capacity) {this.capacity = capacity;this.data = (T[]) new Object[capacity];this.head = 0;this.tail = 0;this.size = 0;}public boolean isEmpty() {return size == 0; // 或 head == tail}public boolean isFull() {return size == capacity; // 使用 size 判斷是否滿}public int size() { return size; }//入隊public void enqueue(T item) {if (isFull()) {//throw new RuntimeException("Queue is full");resizeArray(); //  擴容操作}data[tail] = item;tail = (tail + 1) % capacity; // 環(huán)形數(shù)組的關(guān)鍵：使用模運算size++;}//出隊public T dequeue() {if (isEmpty()) {throw new NoSuchElementException("Queue is empty");}T item = data[head];data[head] = null; //  避免對象游離head = (head + 1) % capacity; // 環(huán)形數(shù)組的關(guān)鍵：使用模運算size--;return item;}//返回隊首元素public T peek() {if (isEmpty()) {throw new NoSuchElementException("Queue is empty");}return data[head];}private void resizeArray() { // 擴容方法示例int newCapacity = capacity * 2;T[] newData = (T[]) new Object[newCapacity];for (int i = 0; i < size; i++) {newData[i] = data[(head + i) % capacity];}data = newData;head = 0;tail = size;capacity = newCapacity;}
}

4. 隊列的基本操作圖解?

4.1 下標(biāo)計算

例如，數(shù)組長度是 5，當(dāng)前位置是 3 ，向前走 2 步，此時下標(biāo)為 (3 + 2) % 5 = 0

• cur 當(dāng)前指針位置

• step 前進步數(shù)

• length 數(shù)組長度 ?

4.2 判空

引入size屬性后有兩種方式：

return tail == size; //隊列大小return size == 0;

4.3 判滿

引入size屬性后有兩種方式：
?

return size =?capacity; //數(shù)組容量return (tail + 1) % length == head;

4.4 入隊

假設(shè)入隊前隊空：此時head == tail

入隊后：head 不變，tail + 1，代碼中這樣書寫 ：tail = (tail + 1) % length，保證了不會越界的情況，不能設(shè)置為 tail ++ 。此時a即是隊頭也是隊尾。

4.5 出隊

這里要牢記隊列的特點：先進先出、后進后出

假設(shè)此時a、b已入隊，現(xiàn)在a要出隊，出隊前：a是隊頭，b是隊尾

a出隊后：此時b成為新隊頭

4.6 返回隊頭元素?

略，具體實現(xiàn)：首先確保不是空隊列，然后返回 data[head]?

5. 各個操作的時間復(fù)雜度

• 入隊 (enqueue):?數(shù)組實現(xiàn): 均攤 O(1) (因為需要考慮擴容的情況，但大多數(shù)情況下是 O(1)), 鏈表實現(xiàn): O(1)

• 出隊 (dequeue):?O(1)

• 查看隊首元素 (peek):?O(1)

6. 隊列的局限性

• 數(shù)組實現(xiàn)的假溢出:?使用環(huán)形數(shù)組實現(xiàn)時，雖然解決了普通數(shù)組的"一次性"問題，但仍然存在容量限制。需要仔細處理擴容操作。

• 固定大小：在某些實現(xiàn)中，隊列的大小是固定的，這意味著一旦隊列滿了，就不能再添加新的元素，除非移除一些元素。這可能導(dǎo)致數(shù)據(jù)丟失或需要額外的邏輯來處理溢出。

• 性能問題：在基于數(shù)組的隊列實現(xiàn)中，如果隊列經(jīng)常達到其最大容量，那么在隊列的末尾添加元素可能需要數(shù)組的復(fù)制，這會帶來額外的時間成本。雖然這個操作是偶爾發(fā)生的，但在高負載情況下可能會影響性能。

• 不適合隨機訪問：隊列不支持隨機訪問，這意味著你不能直接訪問隊列中間的元素。如果你需要隨機訪問，可能需要使用其他數(shù)據(jù)結(jié)構(gòu)，如數(shù)組或鏈表。

• 不適合實時系統(tǒng)：在實時系統(tǒng)中，隊列可能不是最佳選擇，因為隊列的操作（入隊和出隊）可能需要等待，特別是在有大量并發(fā)操作時。

• 空間效率：在基于數(shù)組的實現(xiàn)中，即使隊列中沒有很多元素，數(shù)組也可能被預(yù)分配了較大的空間，這可能導(dǎo)致空間的浪費。

• 操作的局限性：隊列只允許在隊尾添加元素，在隊頭移除元素。如果需要在隊列中間進行操作，隊列可能不是最合適的選擇。

• 并發(fā)問題：在多線程環(huán)境中，隊列的操作需要同步，以避免競態(tài)條件和數(shù)據(jù)不一致的問題。這可能需要額外的鎖機制，從而影響性能。

• 不適合處理大量數(shù)據(jù)：如果需要處理大量數(shù)據(jù)，隊列可能不是最佳選擇，因為隊列的操作可能會因為數(shù)據(jù)量大而變得緩慢。

• 不適合需要頻繁插入和刪除的場景：如果應(yīng)用場景中需要頻繁地在隊列的中間進行插入和刪除操作，隊列可能不是最佳選擇，因為這些操作在隊列中是不允許的。

• 不適合需要多種訪問模式的場景：如果應(yīng)用需要多種不同的數(shù)據(jù)訪問模式，如堆棧的后進先出（LIFO）特性，隊列可能不足以滿足需求。

7. 總結(jié)和應(yīng)用場景

隊列是一種簡單但強大的數(shù)據(jù)結(jié)構(gòu)，其 FIFO 特性使其在許多場景下都非常有用，例如：

• 任務(wù)調(diào)度:?操作系統(tǒng)中的任務(wù)調(diào)度通常使用隊列來管理待執(zhí)行的任務(wù)，保證先提交的任務(wù)先執(zhí)行。例如打印隊列，按照先來先服務(wù)的順序打印文檔。

• 寬度優(yōu)先搜索 (BFS):?圖算法中常用的寬度優(yōu)先搜索算法使用隊列來存儲待訪問的節(jié)點， ensuring that nodes closer to the starting node are visited first.

• 緩沖區(qū):?在生產(chǎn)者-消費者模型中，隊列可以作為緩沖區(qū)，平衡生產(chǎn)者和消費者的速度差異。生產(chǎn)者將數(shù)據(jù)放入隊列，消費者從隊列中取出數(shù)據(jù)。隊列可以緩解生產(chǎn)和消費速度不匹配的問題，避免數(shù)據(jù)丟失或程序阻塞. 例如，網(wǎng)絡(luò)請求中的緩沖區(qū)。

• 消息隊列:?在分布式系統(tǒng)中，消息隊列用于異步通信。發(fā)送方將消息放入隊列，接收方從隊列中取出消息。消息隊列可以解耦發(fā)送方和接收方，提高系統(tǒng)的可靠性和可擴展性。 例如，Kafka, RabbitMQ.

理解隊列的概念和實現(xiàn)對于程序員來說至關(guān)重要，它能幫助我們更好地設(shè)計和優(yōu)化程序。

希望本文能幫助各位看官更好地理解隊列這種重要的數(shù)據(jù)結(jié)構(gòu)！下期見，謝謝~