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