hello-algo 圖解佇列：FIFO 先入先出原理、雙端操作與多語言實作指南-平芜编程栈

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 Out，FIFO）規則，模擬了現實中的排隊現象。本文以佇列章節為主體，完整覆蓋佇列的核心概念、常用操作的效率分析、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 種語言用法：

=== "Python"

```python title="queue.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 ```

=== "C++"

```cpp title="queue.cpp" /* 初始化佇列 */ queue<int> 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(); ```

=== "Java"

```java title="queue.java" /* 初始化佇列 */ Queue<Integer> 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 title="queue.cs" /* 初始化佇列 */ Queue<int> 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; ```

=== "Go"

```go title="queue_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 ```

=== "Swift"

```swift title="queue.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 ```

=== "JS"

```javascript title="queue.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; ```

=== "TS"

```typescript title="queue.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; ```

=== "Dart"

```dart title="queue.dart" /* 初始化佇列 */ // 在 Dart 中，佇列類別 Queue 是雙向佇列，也可作為佇列使用 Queue<int> 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; ```

=== "Rust"

```rust title="queue.rs" /* 初始化雙向佇列 */ // 在 Rust 中使用雙向佇列作為普通佇列來使用 let mut deque: VecDeque<u32> = 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(); ```

=== "C"

```c title="queue.c" // C 未提供內建佇列 ```

=== "Kotlin"

```kotlin title="queue.kt" /* 初始化佇列 */ val queue = LinkedList<Int>() /* 元素入列 */ 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() ```

=== "Ruby"

```ruby title="queue.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時佇列已滿只能報錯或丟棄）。這個問題不難解決，我們可以將陣列替換為動態陣列，引入擴容機制（例如容量翻倍後複製元素），有興趣的讀者可以嘗試自行實現。陣列實作的優勢在於連續記憶體帶來的快取命中率高、記憶體開銷小；劣勢則是需要預先規劃容量並處理擴容。

兩種實作的對比

兩種實作的對比結論與堆疊一致：鏈結串列版彈性大、無容量限制但佔用更多記憶體；陣列版記憶體緊湊、快取友好但有容量上限。在實際工程中，各語言的標準庫佇列（如 C++std::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 走訪等場景，是後續學習樹與圖演算法的必備基礎。