C# Queue源码分析

Queue<T> 是 .NET 中的泛型队列类，采用循环数组实现先进先出（FIFO）操作。核心字段包括_array（存储元素）、_head（队头）、_tail（队尾）和_size（元素数量）。主要方法包括： Enqueue：入队时自动扩容（默认翻倍）； Dequeue/TryDequeue：出队操作； Peek/TryPeek：查看队首； Clear：清空队列时处理引用类型。通过环形数

yasince

979人浏览 · 2025-08-18 20:05:28

yasince · 2025-08-18 20:05:28 发布

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，扩容后是 200
        int 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)
{
    // 创建一个新的数组，容量为传入的 capacity
    T[] 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;
    else
        return
            Array.IndexOf(_array, item, _head, _array.Length - _head) >= 0 ||
            Array.IndexOf(_array, item, 0, _tail) >= 0;
}

判断队列中是否包含某个元素。
分段查找环形数组中的内容。

2. `CopyTo`

public void CopyTo(T[] array, int arrayIndex)
{
    // 参数检查：目标数组不能为 null
    if (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);

        // 如果枚举已结束，直接返回 false
        if (_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 枚举器规范

Queue<T>.Enumerator 是一个支持环形数组结构的枚举器，通过保存队列的版本号来检测并发修改，确保枚举过程的稳定性，同时使用高效的索引计算方式处理非连续存储的数据。

七、结语

Queue<T> 是 .NET 中一个非常实用的泛型集合类，其基于环形数组的实现方式在性能和内存管理上做了很好的权衡。

2048 AI社区

有“AI”的1024 = 2048，欢迎大家加入2048 AI社区

更多推荐

LangChain 的Chain 架构在处理复杂 Agent 任务时的局限性深度剖析

随着大语言模型（LLM）应用从简单的 RAG（检索增强生成）向自主性更强的 Agent（智能体）演进，开发者们发现 LangChain 早期引以为傲的 "Chain"（链式）架构在处理复杂任务时逐渐显得力不从心。本文将从拓扑结构、状态管理、动态决策及容错机制四个维度，深入剖析 Chain 架构在构建复杂 Agent 时的局限性，并探讨为何架构模式正在从 DAG（有向无环图）向循环图（Cyclic

2048 AI社区

李飞飞AI突破物理世界瓶颈，RUST 静态生命周期和动态生命周期

李飞飞在物理世界 AI 的研究中强调了多维度价值与跨领域融合的重要性。物理世界 AI 的核心在于将人工智能技术与现实物理环境紧密结合，实现从感知到决策的闭环。静态生命周期通过注解显式声明，编译器在编译期验证引用有效性。Rust 的生命周期机制是内存安全的核心，分为静态（编译时确定）和动态（运行时检查）两类。当生命周期无法在编译时确定时，需依赖运行时检查。允许跨线程共享 AI 模型，动态管理其生命周

2048 AI社区

LTU：一种能听、能想、能理解的大模型架构，HTML 表格

LTU（Listen-Think-Understand）是一种新型的大模型架构，旨在通过模块化设计实现多模态交互能力。其核心思想是将模型的输入、处理和输出分为三个独立但协同工作的模块，分别对应“听”（输入感知）、“想”（逻辑推理）和“理解”（语义生成）。例如，语音输入通过ASR（自动语音识别）转换为文本，图像通过CLIP模型提取语义特征。LTU适用于需要复杂交互的场景，例如智能客服、教育辅助和医疗

2048 AI社区

所有评论(0)

查看更多评论

yasince

@qq_40924071

已为社区贡献3条内容

C# Queue源码分析

yasince

一、类结构与字段说明

核心字段：

二、构造函数

1. 默认构造函数

2. 指定初始容量的构造函数

3. 使用 IEnumerable<T> 构造

三、核心操作方法

1. 入队 Enqueue

扩容逻辑：

2. 出队 Dequeue

3. 尝试出队 TryDequeue

4. 查看队首 Peek

5. 尝试查看队首 TryPeek

6. 清空队列 Clear

情况 1：连续存储

情况 2：环形存储

7. 遍历队列 GetEnumerator

8. 转换为数组 ToArray

情况 1：连续存储

情况 2：环形存储

9. 扩容方法 SetCapacity

情况 1：连续存储

情况 2：环形存储

10. 指针移动 MoveNext

四、其他辅助方法

1. Contains

2. CopyTo

五、迭代器

设计亮点总结

七、结语

所有评论(0)

yasince

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

1. 入队 `Enqueue`

2. 出队 `Dequeue`

3. 尝试出队 `TryDequeue`

4. 查看队首 `Peek`

5. 尝试查看队首 `TryPeek`

6. 清空队列 `Clear`

7. 遍历队列 `GetEnumerator`

8. 转换为数组 `ToArray`

9. 扩容方法 `SetCapacity`

10. 指针移动 `MoveNext`

1. `Contains`

2. `CopyTo`