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指標快取不友好。基於陣列的實作在陣列中刪除首元素的時間複雜度為 $O(n)$這會導致出列操作效率較低。然而我們可以採用以下巧妙方法來避免這個問題。核心思路使用一個變數front指向佇列首元素的索引並維護一個變數size用於記錄佇列長度。定義rear front size這個公式計算出的rear指向佇列尾元素之後的下一個位置。基於此設計陣列中包含元素的有效區間為[front, rear - 1]各種操作的實現方法如下入列操作將輸入元素賦值給rear索引處並將size增加 1。出列操作只需將front增加 1並將size減少 1。可以看到入列和出列操作都只需進行一次操作時間複雜度均為 $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 可在本倉庫對應目錄下繼續深入學習。【免费下载链接】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），仅供参考