hello-algo 圖解佇列FIFO 先入先出原理、雙端操作與多語(yǔ)言實(shí)作指南【免費(fèi)下載鏈接】hello-algo《Hello 算法》動(dòng)畫圖解、一鍵運(yùn)行的數(shù)據(jù)結(jié)構(gòu)與算法教程。支持簡(jiǎn)中、繁中、English、日本語(yǔ)提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代碼實(shí)現(xiàn)項(xiàng)目地址: https://gitcode.com/GitHub_Trending/he/hello-algo佇列queue是《Hello 演算法》中與堆疊齊名的基礎(chǔ)線性資料結(jié)構(gòu)它嚴(yán)格遵循「先入先出」First In, First OutFIFO規(guī)則模擬了現(xiàn)實(shí)中的排隊(duì)現(xiàn)象。本文以 佇列章節(jié) 為主體完整覆蓋佇列的核心概念、常用操作的效率分析、13 種程式語(yǔ)言的現(xiàn)成佇列用法並結(jié)合本倉(cāng)庫(kù)的 鏈結(jié)串列實(shí)作 與 環(huán)形陣列實(shí)作 原始碼深入剖析兩種底層實(shí)作方案。讀完本文你將掌握佇列的操作語(yǔ)義、時(shí)間複雜度分析以及從零手寫佇列的核心技巧。什麼是佇列佇列queue是一種遵循先入先出規(guī)則的線性資料結(jié)構(gòu)。顧名思義佇列模擬了排隊(duì)現(xiàn)象即新來(lái)的人不斷加入佇列尾部而位於佇列頭部的人逐個(gè)離開。我們將佇列頭部稱為「佇列首」front尾部稱為「佇列尾」rear把將元素加入列尾的操作稱為「入列」enqueue / push把刪除佇列首元素的操作稱為「出列」dequeue / pop。上圖直觀展示了這個(gè)過(guò)程元素 1、3、2 依次入列形成佇列接著 5、4 從列尾加入出列時(shí)則永遠(yuǎn)是位於佇列首的 1、3 先被移除體現(xiàn)出「先進(jìn)先出」的嚴(yán)格順序。與堆疊「後進(jìn)先出」的對(duì)比是理解佇列的關(guān)鍵堆疊如同疊貓貓後放上去的先拿走佇列則像貓貓排隊(duì)先到的先離開。兩者分別代表兩種截然不同的邏輯關(guān)係也是後續(xù)樹的走訪BFS等演算法的重要基礎(chǔ)。佇列常用操作佇列的常見操作如下表所示。需要注意的是不同程式語(yǔ)言的方法名稱可能有所不同本倉(cāng)庫(kù)在此採(cǎi)用與堆疊相同的方法命名便於讀者類比記憶。方法名描述時(shí)間複雜度push()元素入列即將元素新增至佇列尾$O(1)$pop()佇列首元素出列$O(1)$peek()訪問(wèn)佇列首元素$O(1)$三種核心操作的時(shí)間複雜度均為 $O(1)$這正是佇列被廣泛用於緩衝、任務(wù)排程等場(chǎng)景的根本原因——無(wú)論佇列中有多少元素入列與出列都只涉及常數(shù)次操作。各語(yǔ)言現(xiàn)成的佇列類別我們可以直接使用程式語(yǔ)言中現(xiàn)成的佇列類別無(wú)需自行實(shí)作。以下完整列出本倉(cāng)庫(kù)文檔中覆蓋的 13 種語(yǔ)言用法 Pythonpython titlequeue.py from collections import deque # 初始化佇列 # 在 Python 中我們一般將雙向佇列類別 deque 當(dāng)作佇列使用 # 雖然 queue.Queue() 是純正的佇列類別但不太好用因此不推薦 que: deque[int] deque() # 元素入列 que.append(1) que.append(3) que.append(2) que.append(5) que.append(4) # 訪問(wèn)佇列首元素 front: int que[0] # 元素出列 pop: int que.popleft() # 獲取佇列的長(zhǎng)度 size: int len(que) # 判斷佇列是否為空 is_empty: bool len(que) 0 Ccpp titlequeue.cpp /* 初始化佇列 */ queueint queue; /* 元素入列 */ queue.push(1); queue.push(3); queue.push(2); queue.push(5); queue.push(4); /* 訪問(wèn)佇列首元素 */ int front queue.front(); /* 元素出列 */ queue.pop(); /* 獲取佇列的長(zhǎng)度 */ int size queue.size(); /* 判斷佇列是否為空 */ bool empty queue.empty(); Javajava titlequeue.java /* 初始化佇列 */ QueueInteger queue new LinkedList(); /* 元素入列 */ queue.offer(1); queue.offer(3); queue.offer(2); queue.offer(5); queue.offer(4); /* 訪問(wèn)佇列首元素 */ int peek queue.peek(); /* 元素出列 */ int pop queue.poll(); /* 獲取佇列的長(zhǎng)度 */ int size queue.size(); /* 判斷佇列是否為空 */ boolean isEmpty queue.isEmpty(); C#csharp titlequeue.cs /* 初始化佇列 */ Queueint queue new(); /* 元素入列 */ queue.Enqueue(1); queue.Enqueue(3); queue.Enqueue(2); queue.Enqueue(5); queue.Enqueue(4); /* 訪問(wèn)佇列首元素 */ int peek queue.Peek(); /* 元素出列 */ int pop queue.Dequeue(); /* 獲取佇列的長(zhǎng)度 */ int size queue.Count; /* 判斷佇列是否為空 */ bool isEmpty queue.Count 0; Gogo titlequeue_test.go /* 初始化佇列 */ // 在 Go 中將 list 作為佇列來(lái)使用 queue : list.New() /* 元素入列 */ queue.PushBack(1) queue.PushBack(3) queue.PushBack(2) queue.PushBack(5) queue.PushBack(4) /* 訪問(wèn)佇列首元素 */ peek : queue.Front() /* 元素出列 */ pop : queue.Front() queue.Remove(pop) /* 獲取佇列的長(zhǎng)度 */ size : queue.Len() /* 判斷佇列是否為空 */ isEmpty : queue.Len() 0 Swiftswift titlequeue.swift /* 初始化佇列 */ // Swift 沒有內(nèi)建的佇列類別可以把 Array 當(dāng)作佇列來(lái)使用 var queue: [Int] [] /* 元素入列 */ queue.append(1) queue.append(3) queue.append(2) queue.append(5) queue.append(4) /* 訪問(wèn)佇列首元素 */ let peek queue.first! /* 元素出列 */ // 由於是陣列因此 removeFirst 的複雜度為 O(n) let pop queue.removeFirst() /* 獲取佇列的長(zhǎng)度 */ let size queue.count /* 判斷佇列是否為空 */ let isEmpty queue.isEmpty JSjavascript titlequeue.js /* 初始化佇列 */ // JavaScript 沒有內(nèi)建的佇列可以把 Array 當(dāng)作佇列來(lái)使用 const queue []; /* 元素入列 */ queue.push(1); queue.push(3); queue.push(2); queue.push(5); queue.push(4); /* 訪問(wèn)佇列首元素 */ const peek queue[0]; /* 元素出列 */ // 底層是陣列因此 shift() 方法的時(shí)間複雜度為 O(n) const pop queue.shift(); /* 獲取佇列的長(zhǎng)度 */ const size queue.length; /* 判斷佇列是否為空 */ const empty queue.length 0; TStypescript titlequeue.ts /* 初始化佇列 */ // TypeScript 沒有內(nèi)建的佇列可以把 Array 當(dāng)作佇列來(lái)使用 const queue: number[] []; /* 元素入列 */ queue.push(1); queue.push(3); queue.push(2); queue.push(5); queue.push(4); /* 訪問(wèn)佇列首元素 */ const peek queue[0]; /* 元素出列 */ // 底層是陣列因此 shift() 方法的時(shí)間複雜度為 O(n) const pop queue.shift(); /* 獲取佇列的長(zhǎng)度 */ const size queue.length; /* 判斷佇列是否為空 */ const empty queue.length 0; Dartdart titlequeue.dart /* 初始化佇列 */ // 在 Dart 中佇列類別 Queue 是雙向佇列也可作為佇列使用 Queueint queue Queue(); /* 元素入列 */ queue.add(1); queue.add(3); queue.add(2); queue.add(5); queue.add(4); /* 訪問(wèn)佇列首元素 */ int peek queue.first; /* 元素出列 */ int pop queue.removeFirst(); /* 獲取佇列的長(zhǎng)度 */ int size queue.length; /* 判斷佇列是否為空 */ bool isEmpty queue.isEmpty; Rustrust titlequeue.rs /* 初始化雙向佇列 */ // 在 Rust 中使用雙向佇列作為普通佇列來(lái)使用 let mut deque: VecDequeu32 VecDeque::new(); /* 元素入列 */ deque.push_back(1); deque.push_back(3); deque.push_back(2); deque.push_back(5); deque.push_back(4); /* 訪問(wèn)佇列首元素 */ if let Some(front) deque.front() { } /* 元素出列 */ if let Some(pop) deque.pop_front() { } /* 獲取佇列的長(zhǎng)度 */ let size deque.len(); /* 判斷佇列是否為空 */ let is_empty deque.is_empty(); Cc titlequeue.c // C 未提供內(nèi)建佇列 Kotlinkotlin titlequeue.kt /* 初始化佇列 */ val queue LinkedListInt() /* 元素入列 */ queue.offer(1) queue.offer(3) queue.offer(2) queue.offer(5) queue.offer(4) /* 訪問(wèn)佇列首元素 */ val peek queue.peek() /* 元素出列 */ val pop queue.poll() /* 獲取佇列的長(zhǎng)度 */ val size queue.size /* 判斷佇列是否為空 */ val isEmpty queue.isEmpty() Rubyruby titlequeue.rb # 初始化佇列 # Ruby 內(nèi)建的佇列Thread::Queue) 沒有 peek 和走訪方法可以把 Array 當(dāng)作佇列來(lái)使用 queue [] # 元素入列 queue.push(1) queue.push(3) queue.push(2) queue.push(5) queue.push(4) # 訪問(wèn)佇列元素 peek queue.first # 元素出列 # 清注意由於是陣列Array#shift 方法時(shí)間複雜度為 O(n) pop queue.shift # 獲取佇列的長(zhǎng)度 size queue.length # 判斷佇列是否為空 is_empty queue.empty? 從上述範(fàn)例中可以歸納出一個(gè)重要規(guī)律並非每種語(yǔ)言都提供了真正的「佇列」容器。例如 Python 推薦用雙向佇列deque、Go 用雙向鏈結(jié)串列l(wèi)ist、Rust 用VecDeque而 Swift、JS、TS、Ruby 則直接拿陣列當(dāng)佇列使用——此時(shí)必須注意removeFirst()、shift()等操作在陣列底層的複雜度退化為 $O(n)$需要搬移後續(xù)所有元素與標(biāo)準(zhǔn)佇列的 $O(1)$ 出列存在本質(zhì)差異在效能敏感場(chǎng)景需謹(jǐn)慎取捨。C 語(yǔ)言則完全沒有內(nèi)建佇列這正是下一節(jié)手寫實(shí)作的用武之地。佇列實(shí)作為了實(shí)現(xiàn)佇列我們需要一種資料結(jié)構(gòu)可以在一端新增元素並在另一端刪除元素鏈結(jié)串列和陣列都符合要求。本倉(cāng)庫(kù)在 chapter_stack_and_queue 目錄下同時(shí)提供了兩種實(shí)作下面逐一深入分析?；舵溄Y(jié)串列的實(shí)作我們可以將鏈結(jié)串列的「頭節(jié)點(diǎn)」和「尾節(jié)點(diǎn)」分別視為「佇列首」和「佇列尾」規(guī)定佇列尾僅可新增節(jié)點(diǎn)佇列首僅可刪除節(jié)點(diǎn)。以下是本倉(cāng)庫(kù)以 C 語(yǔ)言實(shí)作的鏈結(jié)串列佇列完整原始碼位於 linkedlist_queue.c/* 基于鏈表實(shí)現(xiàn)的隊(duì)列 */ typedef struct { ListNode *front, *rear; int queSize; } LinkedListQueue; /* 構(gòu)造函數(shù) */ LinkedListQueue *newLinkedListQueue() { LinkedListQueue *queue (LinkedListQueue *)malloc(sizeof(LinkedListQueue)); queue-front NULL; queue-rear NULL; queue-queSize 0; return queue; } /* 入隊(duì) */ void push(LinkedListQueue *queue, int num) { // 尾節(jié)點(diǎn)處添加 node ListNode *node newListNode(num); // 如果隊(duì)列為空則令頭、尾節(jié)點(diǎn)都指向該節(jié)點(diǎn) if (queue-front NULL) { queue-front node; queue-rear node; } // 如果隊(duì)列不為空則將該節(jié)點(diǎn)添加到尾節(jié)點(diǎn)后 else { queue-rear-next node; queue-rear node; } queue-queSize; } /* 訪問(wèn)隊(duì)首元素 */ int peek(LinkedListQueue *queue) { assert(size(queue) queue-front); return queue-front-val; } /* 出隊(duì) */ int pop(LinkedListQueue *queue) { int num peek(queue); ListNode *tmp queue-front; queue-front queue-front-next; free(tmp); queue-queSize--; return num; }從實(shí)作細(xì)節(jié)可以提煉出鏈結(jié)串列佇列的三個(gè)要點(diǎn)雙指針結(jié)構(gòu)僅維護(hù)front與rear兩個(gè)節(jié)點(diǎn)指標(biāo)天然支援一端入列、一端出列無(wú)需像單向鏈結(jié)串列走訪那樣從頭遍歷空佇列的初始化push()時(shí)若front NULL需讓頭、尾節(jié)點(diǎn)同時(shí)指向新節(jié)點(diǎn)這是鏈結(jié)串列佇列最容易遺漏的邊界條件出列即刪節(jié)點(diǎn)pop()透過(guò)free(tmp)釋放被移除的頭節(jié)點(diǎn)記憶體避免記憶體洩漏——Python 版本 linkedlist_queue.py 與 Java 版本 linkedlist_queue.java 因語(yǔ)言自帶垃圾回收而無(wú)需此步驟但邏輯結(jié)構(gòu)完全一致。鏈結(jié)串列實(shí)作的入列、出列皆為 $O(1)$且無(wú)容量上限受可用記憶體約束缺點(diǎn)是每個(gè)節(jié)點(diǎn)需額外儲(chǔ)存next指標(biāo)快取不友好?；蛾嚵械膶?shí)作在陣列中刪除首元素的時(shí)間複雜度為 $O(n)$這會(huì)導(dǎo)致出列操作效率較低。然而我們可以採(cǎi)用以下巧妙方法來(lái)避免這個(gè)問(wèn)題。核心思路使用一個(gè)變數(shù)front指向佇列首元素的索引並維護(hù)一個(gè)變數(shù)size用於記錄佇列長(zhǎng)度。定義rear front size這個(gè)公式計(jì)算出的rear指向佇列尾元素之後的下一個(gè)位置?；洞嗽O(shè)計(jì)陣列中包含元素的有效區(qū)間為[front, rear - 1]各種操作的實(shí)現(xiàn)方法如下入列操作將輸入元素賦值給rear索引處並將size增加 1。出列操作只需將front增加 1並將size減少 1?？梢钥吹饺肓泻统隽胁僮鞫贾恍柽M(jìn)行一次操作時(shí)間複雜度均為 $O(1)$。你可能會(huì)發(fā)現(xiàn)一個(gè)問(wèn)題在不斷進(jìn)行入列和出列的過(guò)程中front和rear都在向右移動(dòng)當(dāng)它們到達(dá)陣列尾部時(shí)就無(wú)法繼續(xù)移動(dòng)了。為了解決此問(wèn)題我們可以將陣列視為首尾相接的「環(huán)形陣列」。對(duì)於環(huán)形陣列我們需要讓front或rear在越過(guò)陣列尾部時(shí)直接回到陣列頭部繼續(xù)走訪。這種週期性規(guī)律可以透過(guò)「取餘操作」來(lái)實(shí)現(xiàn)。本倉(cāng)庫(kù)的 C 語(yǔ)言實(shí)作位於 array_queue.c/* 基于環(huán)形數(shù)組實(shí)現(xiàn)的隊(duì)列 */ typedef struct { int *nums; // 用于存儲(chǔ)隊(duì)列元素的數(shù)組 int front; // 隊(duì)首指針指向隊(duì)首元素 int queSize; // 當(dāng)前隊(duì)列的元素?cái)?shù)量 int queCapacity; // 隊(duì)列容量 } ArrayQueue; /* 入隊(duì) */ void push(ArrayQueue *queue, int num) { if (size(queue) capacity(queue)) { printf(隊(duì)列已滿\r\n); return; } // 計(jì)算隊(duì)尾指針指向隊(duì)尾索引 1 // 通過(guò)取余操作實(shí)現(xiàn) rear 越過(guò)數(shù)組尾部后回到頭部 int rear (queue-front queue-queSize) % queue-queCapacity; // 將 num 添加至隊(duì)尾 queue-nums[rear] num; queue-queSize; } /* 出隊(duì) */ int pop(ArrayQueue *queue) { int num peek(queue); // 隊(duì)首指針向后移動(dòng)一位若越過(guò)尾部則返回到數(shù)組頭部 queue-front (queue-front 1) % queue-queCapacity; queue-queSize--; return num; }取餘運(yùn)算是環(huán)形陣列的精髓兩條關(guān)鍵公式分別對(duì)應(yīng)入列與出列入列rear (front size) % capacity讓尾指標(biāo)在越界後繞回陣列頭部出列front (front 1) % capacity讓首指標(biāo)繞回陣列頭部。為了驗(yàn)證環(huán)形陣列在「指標(biāo)繞回」場(chǎng)景下的正確性本倉(cāng)庫(kù)的 Driver Code 做了專門的壓力測(cè)試Python 版見 array_queue.py# 測(cè)試環(huán)形數(shù)組 for i in range(10): queue.push(i) queue.pop() print(第, i, 輪入隊(duì) 出隊(duì)后 queue , queue.to_list())連續(xù) 10 輪「入隊(duì) 出隊(duì)」迫使front指標(biāo)反覆越過(guò)陣列尾部再繞回驗(yàn)證了取餘邏輯的正確性。陣列實(shí)作的侷限與改進(jìn)以上實(shí)現(xiàn)的佇列仍然具有侷限性——其長(zhǎng)度不可變?nèi)萘吭诮?gòu)時(shí)固定push時(shí)佇列已滿只能報(bào)錯(cuò)或丟棄。這個(gè)問(wèn)題不難解決我們可以將陣列替換為動(dòng)態(tài)陣列引入擴(kuò)容機(jī)制例如容量翻倍後複製元素有興趣的讀者可以嘗試自行實(shí)現(xiàn)。陣列實(shí)作的優(yōu)勢(shì)在於連續(xù)記憶體帶來(lái)的快取命中率高、記憶體開銷小劣勢(shì)則是需要預(yù)先規(guī)劃容量並處理擴(kuò)容。兩種實(shí)作的對(duì)比兩種實(shí)作的對(duì)比結(jié)論與堆疊一致鏈結(jié)串列版彈性大、無(wú)容量限制但佔(zhàn)用更多記憶體陣列版記憶體緊湊、快取友好但有容量上限。在實(shí)際工程中各語(yǔ)言的標(biāo)準(zhǔn)庫(kù)佇列如 Cstd::queue、JavaLinkedList通常底層正是採(cǎi)用了上述某一種策略理解本節(jié)的原始碼後再回頭看「現(xiàn)成佇列類別」的用法會(huì)更加通透。佇列典型應(yīng)用佇列的 FIFO 特性使其成為「先來(lái)後到」類場(chǎng)景的標(biāo)準(zhǔn)解法本倉(cāng)庫(kù)文檔列舉了兩類最典型的應(yīng)用淘寶訂單。購(gòu)物者下單後訂單將加入佇列中系統(tǒng)隨後會(huì)根據(jù)順序處理佇列中的訂單。在雙十一期間短時(shí)間內(nèi)會(huì)產(chǎn)生海量訂單高併發(fā)成為工程師們需要重點(diǎn)攻克的問(wèn)題——訊息佇列如 Kafka、RabbitMQ 等訊息中介軟體正是佇列思想在分散式系統(tǒng)中的延伸。各類待辦事項(xiàng)。任何需要實(shí)現(xiàn)「先來(lái)後到」功能的場(chǎng)景例如印表機(jī)的任務(wù)佇列、餐廳的出餐佇列等佇列在這些場(chǎng)景中可以有效地維護(hù)處理順序。除此之外從資料結(jié)構(gòu)的角度看佇列還是**廣度優(yōu)先走訪BFS**的天然載體——無(wú)論是二元樹的層序走訪見 binary_tree_bfs還是圖的廣度優(yōu)先搜尋見 graph_bfs都依賴佇列來(lái)控制「按層展開」的走訪順序。小結(jié)佇列是遵循**先入先出FIFO**規(guī)則的線性資料結(jié)構(gòu)入列在佇列尾、出列在佇列首三種核心操作push()、pop()、peek()的理想時(shí)間複雜度均為 $O(1)$工程上可直接使用各語(yǔ)言標(biāo)準(zhǔn)庫(kù)但需留意 Swift、JS、TS 等語(yǔ)言以陣列模擬佇列時(shí)shift()/removeFirst()會(huì)退化為 $O(n)$手寫佇列有兩條路線鏈結(jié)串列版雙指針front/rear無(wú)容量限制與環(huán)形陣列版front size定位rear配合取餘運(yùn)算繞回原始碼分別見 linkedlist_queue.c 與 array_queue.c佇列廣泛應(yīng)用於訂單處理、任務(wù)排程、印表機(jī)佇列與 BFS 走訪等場(chǎng)景是後續(xù)學(xué)習(xí)樹與圖演算法的必備基礎(chǔ)。本節(jié)為堆疊與佇列章節(jié)的一部分其姊妹篇 堆疊、雙向佇列 以及章節(jié)總結(jié) summary 可在本倉(cāng)庫(kù)對(duì)應(yīng)目錄下繼續(xù)深入學(xué)習(xí)?！久赓M(fèi)下載鏈接】hello-algo《Hello 算法》動(dòng)畫圖解、一鍵運(yùn)行的數(shù)據(jù)結(jié)構(gòu)與算法教程。支持簡(jiǎn)中、繁中、English、日本語(yǔ)提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代碼實(shí)現(xiàn)項(xiàng)目地址: https://gitcode.com/GitHub_Trending/he/hello-algo創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考