C# Queue源碼分析

Queue<T> 是 .NET 中實現隊列（先進先出）的一種泛型集合類。它基于數組實現，支持動態擴容、線程不安全，適用于大多數需要隊列結構的場景。

一、類結構與字段說明

public class Queue<T> : IEnumerable<T>, ICollection, IReadOnlyCollection<T>{private T[] _array;private int _head;       //指向隊列中最先進入的元素位置，執行出隊(Dequeue)操作時使用此索引private int _tail;       // 指向下一個要插入的位置，而不是最后一個元素的位置private int _size;       // 元素個數private int _version;private const int MinimumGrow = 4;private const int GrowFactor = 200;  // double each time}

實現了 IEnumerable<T>、ICollection 和 IReadOnlyCollection<T> 接口，支持枚舉、集合操作和只讀訪問。
內部使用環形數組（循環隊列）實現，避免頻繁復制和移動數據。

核心字段：

字段名	類型	說明
`_array`	`T[]`	存儲元素的數組
`_head`	`int`	隊頭索引（下一個要出隊的元素）
`_tail`	`int`	隊尾索引（下一個要入隊的位置）
`_size`	`int`	當前隊列中元素個數
`_version`	`int`	用于枚舉器版本控制，防止修改時遍歷異常
`MinimumGrow`	`int`	最小擴容數量（4）
`GrowFactor`	`int`	擴容因子（200%）

二、構造函數

1. 默認構造函數

public Queue()
{_array = Array.Empty<T>();
}

初始化一個空隊列，默認容量為 0，首次入隊時自動擴容。

2. 指定初始容量的構造函數

public Queue(int capacity)
{if (capacity < 0)throw new ArgumentOutOfRangeException(...);_array = new T[capacity];
}

指定初始容量，避免頻繁擴容。

3. 使用 `IEnumerable<T>` 構造

public Queue(IEnumerable<T> collection)
{_array = EnumerableHelpers.ToArray(collection, out _size);if (_size != _array.Length) _tail = _size;
}

將集合一次性入隊，注意 _tail 的處理。

三、核心操作方法

1. 入隊 `Enqueue`

public void Enqueue(T item)
{// 如果當前隊列已滿（元素數量等于數組長度），需要擴容if (_size == _array.Length){// 根據 GrowFactor（默認 200）計算新的容量，即當前容量的 200%// 例如：當前容量是 4，擴容后是 8；當前容量是 100，擴容后是 200int newcapacity = (int)((long)_array.Length * (long)GrowFactor / 100);// 如果計算出的新容量仍小于當前容量加上最小增長量（MinimumGrow = 4）// 則直接使用當前容量 + MinimumGrow，確保至少增加 4 個容量if (newcapacity < _array.Length + MinimumGrow){newcapacity = _array.Length + MinimumGrow;}// 調用 SetCapacity 方法，創建一個新的數組并復制舊數據SetCapacity(newcapacity);}// 將新元素插入到隊尾位置_array[_tail] = item;// 移動隊尾指針到下一個位置（考慮環形數組）// 例如：如果當前是數組末尾，則回到數組開頭MoveNext(ref _tail);// 隊列元素數量增加 1_size++;// 增加版本號，用于在枚舉時檢測集合是否被修改（防止 InvalidOperationException）_version++;
}

如果數組已滿，則調用 SetCapacity 進行擴容。
插入到 _tail 位置，更新 _tail 和 _size。

擴容邏輯：

默認擴容為原來的 200%（即翻倍），如果不夠，則至少擴容 4 個單位。

2. 出隊 `Dequeue`

public T Dequeue()
{if (_size == 0)ThrowForEmptyQueue();T removed = _array[_head];if (RuntimeHelpers.IsReferenceOrContainsReferences<T>()){_array[_head] = default!;}MoveNext(ref _head);_size--;_version++;return removed;
}

如果隊列為空拋出異常。
獲取 _head 處的元素并清除（引用類型時）。
更新 _head 和 _size。

3. 嘗試出隊 `TryDequeue`

public bool TryDequeue([MaybeNullWhen(false)] out T result)
{if (_size == 0){result = default!;return false;}result = _array[_head];if (RuntimeHelpers.IsReferenceOrContainsReferences<T>()){_array[_head] = default!;}MoveNext(ref _head);_size--;_version++;return true;
}

不拋出異常，返回 false 表示隊列為空。

4. 查看隊首 `Peek`

public T Peek()
{if (_size == 0)ThrowForEmptyQueue();return _array[_head];
}

返回隊首元素，不移除。

5. 嘗試查看隊首 `TryPeek`

public bool TryPeek([MaybeNullWhen(false)] out T result)
{if (_size == 0){result = default!;return false;}result = _array[_head];return true;
}

類似 TryDequeue，不拋異常。

6. 清空隊列 `Clear`

public void Clear()
{// 如果隊列中有元素（_size > 0），才需要進行清理操作if (_size != 0){// 如果 T 是引用類型或包含引用類型（如類、字符串等），需要顯式清空內存// 避免內存泄漏（例如引用未被釋放，GC 無法回收）if (RuntimeHelpers.IsReferenceOrContainsReferences<T>()){// 情況 1：元素是連續存儲的（_head < _tail）if (_head < _tail){// 清空從 _head 開始的 _size 個元素Array.Clear(_array, _head, _size);}else{// 情況 2：元素是環形存儲的（_head > _tail）// 第一步：清空從 _head 到數組末尾的部分Array.Clear(_array, _head, _array.Length - _head);// 第二步：清空從數組開頭到 _tail 的部分Array.Clear(_array, 0, _tail);}}// 將元素數量置為 0_size = 0;}// 重置隊頭和隊尾指針為 0，表示隊列為空_head = 0;_tail = 0;// 增加版本號，用于防止在枚舉過程中修改隊列導致異常（如 InvalidOperationException）_version++;
}

情況 1：連續存儲

_array = [_, _, 1, 2, 3, _]
_head = 2
_tail = 5
_size = 3

_head < _tail，執行 Array.Clear(_array, 2, 3)，清除 1, 2, 3
_size = 0
_head = 0, _tail = 0

情況 2：環形存儲

_array = [4, _, _, _, 1, 2, 3]
_head = 4
_tail = 1
_size = 4

執行兩次 Array.Clear：
- Array.Clear(_array, 4, 3) → 清除 1, 2, 3
- Array.Clear(_array, 0, 1) → 清除 4
_size = 0
_head = 0, _tail = 0

7. 遍歷隊列 `GetEnumerator`

public Enumerator GetEnumerator()
{return new Enumerator(this);
}

返回一個 Enumerator，支持 foreach 遍歷。
內部使用 _version 檢測是否在遍歷時被修改。

8. 轉換為數組 `ToArray`

public T[] ToArray()
{// 創建一個與當前隊列大小相同的新數組T[] arr = new T[_size];// 判斷隊列中元素的存儲方式（連續 or 環形）// 情況 1：隊列元素是連續存儲的（_head <= _tail）if (_head < _tail){// 將數組中從 _head 開始的 _size 個元素復制到新數組的起始位置Array.Copy(_array, _head, arr, 0, _size);}else{// 情況 2：隊列元素是環形存儲的（_head > _tail）// 即：隊列數據從 _head 到數組末尾，再從數組開頭到 _tail// 第一步：復制從 _head 到數組末尾的部分到新數組的起始位置Array.Copy(_array, _head, arr, 0, _array.Length - _head);// 第二步：復制從數組開頭到 _tail 的部分到新數組后續位置Array.Copy(_array, 0, arr, _array.Length - _head, _tail);}// 返回包含隊列所有元素的新數組return arr;
}

情況 1：連續存儲

_array = [_, _, 1, 2, 3, _]
_head = 2
_tail = 5
_size = 3

Array.Copy(_array, 2, arr, 0, 3) → 復制 1, 2, 3
返回 [1, 2, 3]

情況 2：環形存儲

_array = [4, _, _, _, 1, 2, 3]
_head = 4
_tail = 1
_size = 4

執行兩次 Array.Copy：
- Array.Copy(_array, 4, arr, 0, 3) → 復制 1, 2, 3
- Array.Copy(_array, 0, arr, 3, 1) → 復制 4 到 3 的后面
返回 [1, 2, 3, 4]

9. 擴容方法 `SetCapacity`

private void SetCapacity(int capacity)
{// 創建一個新的數組，容量為傳入的 capacityT[] newarray = new T[capacity];// 如果當前隊列中有元素（_size > 0），則需要復制舊數據到新數組if (_size > 0){// 情況 1：隊列中元素是連續存儲的（沒有環繞）// 即：隊頭索引 < 隊尾索引，元素從 _head 到 _tail - 1 連續存放if (_head < _tail){// 將舊數組中從 _head 開始的 _size 個元素復制到新數組的起始位置Array.Copy(_array, _head, newarray, 0, _size);}else{// 情況 2：隊列中元素是環繞存儲的（即隊尾索引小于隊頭索引）// 例如：數組最后幾個元素是隊列的一部分，隊頭在數組末尾附近，隊尾在數組開頭附近// 第一步：復制從 _head 到數組末尾的部分Array.Copy(_array, _head, newarray, 0, _array.Length - _head);// 第二步：復制從數組開頭到 _tail 的部分Array.Copy(_array, 0, newarray, _array.Length - _head, _tail);}}// 將舊數組替換為新數組_array = newarray;// 重置隊頭為新數組的起始位置（0）_head = 0;// 設置隊尾位置：// 如果隊列已滿（_size == capacity），則隊尾回到 0（表示隊列已滿）// 否則，隊尾指向當前元素數量的位置（即下一個插入的位置）_tail = (_size == capacity) ? 0 : _size;// 增加版本號，用于防止在遍歷時修改隊列導致異常（如 InvalidOperationException）_version++;
}

情況 1：連續存儲

_array = [_, _, 1, 2, 3, 4] （_head = 2, _tail = 6, _size = 4）
擴容到 capacity = 8復制后：
newarray = [1, 2, 3, 4, _, _, _, _]
_head = 0
_tail = 4

情況 2：環形存儲

_array = [4, _, _, _, 1, 2, 3] （_head = 4, _tail = 1, _size = 4）
擴容到 capacity = 8復制后：
newarray = [1, 2, 3, 4, _, _, _, _]
_head = 0
_tail = 4

10. 指針移動 `MoveNext`

private void MoveNext(ref int index)
{int tmp = index + 1;if (tmp == _array.Length){tmp = 0;}index = tmp;
}

實現環形數組的指針移動。

四、其他輔助方法

1. `Contains`

public bool Contains(T item)
{if (_size == 0)return false;if (_head < _tail)return Array.IndexOf(_array, item, _head, _size) >= 0;elsereturnArray.IndexOf(_array, item, _head, _array.Length - _head) >= 0 ||Array.IndexOf(_array, item, 0, _tail) >= 0;
}

判斷隊列中是否包含某個元素。
分段查找環形數組中的內容。

2. `CopyTo`

public void CopyTo(T[] array, int arrayIndex)
{// 參數檢查：目標數組不能為 nullif (array == null){throw new ArgumentNullException(nameof(array));}// 參數檢查：arrayIndex 必須在 [0, array.Length] 范圍內if (arrayIndex < 0 || arrayIndex > array.Length){throw new ArgumentOutOfRangeException(nameof(arrayIndex), arrayIndex, SR.ArgumentOutOfRange_Index);}// 獲取目標數組的長度int arrayLen = array.Length;// 檢查目標數組從 arrayIndex 開始是否有足夠空間容納 _size 個元素if (arrayLen - arrayIndex < _size){throw new ArgumentException(SR.Argument_InvalidOffLen);}// 要復制的元素數量，初始為整個隊列的大小int numToCopy = _size;// 如果隊列為空，直接返回if (numToCopy == 0)return;// 第一部分復制：從 _head 開始，到數組末尾為止，最多能復制多少個元素int firstPart = Math.Min(_array.Length - _head, numToCopy);// 復制第一部分：從 _head 到數組末尾Array.Copy(_array, _head, array, arrayIndex, firstPart);// 減去已復制的元素數量numToCopy -= firstPart;// 如果還有剩余元素，說明隊列是環形存儲，需要復制第二部分（從數組開頭到 _tail）if (numToCopy > 0){// 繼續復制剩余元素，從數組開頭開始復制Array.Copy(_array, 0, array, arrayIndex + firstPart, numToCopy);}
}

復制原理和SetCapacity方法相同

五、迭代器

// 實現 Queue<T> 的枚舉器（迭代器），用于支持 foreach 循環。
// 枚舉器使用隊列內部的版本號（_version）來確保在枚舉期間隊列沒有被修改。
public struct Enumerator : IEnumerator<T>, System.Collections.IEnumerator
{// 引用當前隊列private readonly Queue<T> _q;// 保存隊列的版本號，用于檢測在枚舉過程中隊列是否被修改private readonly int _version;// 當前枚舉索引：// -1 表示未開始// -2 表示已結束或已釋放private int _index;// 當前枚舉的元素private T? _currentElement;// 構造函數：初始化枚舉器internal Enumerator(Queue<T> q){_q = q;_version = q._version; // 保存隊列當前版本號_index = -1;           // 初始狀態為未開始_currentElement = default;}// 清理資源，標記枚舉結束public void Dispose(){_index = -2;           // 標記為已釋放_currentElement = default;}// 移動到下一個元素public bool MoveNext(){// 檢查隊列是否被修改，若版本號不一致，拋出異常if (_version != _q._version)throw new InvalidOperationException(SR.InvalidOperation_EnumFailedVersion);// 如果枚舉已結束，直接返回 falseif (_index == -2)return false;// 索引遞增_index++;// 如果索引超出隊列大小，說明已經枚舉完所有元素if (_index == _q._size){_index = -2;           // 標記為結束_currentElement = default;return false;}// 獲取隊列的內部數組和容量T[] array = _q._array;int capacity = array.Length;// 計算實際數組索引：// 隊列的元素不一定從數組索引 0 開始，并且可能是環形存儲的。int arrayIndex = _q._head + _index;// 如果索引越界（環形），手動回繞（比取模更快）if (arrayIndex >= capacity){arrayIndex -= capacity;}// 保存當前元素_currentElement = array[arrayIndex];return true;}// 獲取當前元素（泛型版本）public T Current{get{if (_index < 0)ThrowEnumerationNotStartedOrEnded();return _currentElement!;}}// 拋出異常：枚舉未開始或已結束private void ThrowEnumerationNotStartedOrEnded(){Debug.Assert(_index == -1 || _index == -2);throw new InvalidOperationException(_index == -1 ? SR.InvalidOperation_EnumNotStarted : SR.InvalidOperation_EnumEnded);}// 獲取當前元素（非泛型版本）object? IEnumerator.Current{get { return Current; }}// 重置枚舉器（不推薦使用，因為 IEnumerator.Reset() 是顯式接口實現）void IEnumerator.Reset(){if (_version != _q._version)throw new InvalidOperationException(SR.InvalidOperation_EnumFailedVersion);_index = -1;           // 重置為未開始狀態_currentElement = default;}
}

設計亮點總結

功能	說明
版本號檢測	使用 `_version` 檢測隊列是否在枚舉期間被修改，防止并發修改異常
環形數組支持	正確處理 `_head` 和 `_index` 的組合，支持非連續存儲的隊列
性能優化	使用 `arrayIndex -= capacity` 替代 `%` 運算符，提升性能
狀態管理	使用 `_index` 的狀態區分枚舉是否開始、進行中或已結束
線程安全限制	不是線程安全的，但能檢測到隊列被修改
資源釋放	提供 `Dispose()` 方法清理資源，符合 .NET 枚舉器規范