WordPress文章生成海報代碼seo推廣策略
隊列(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)!下期見,謝謝~