在 .NET 中，Stack<T> 是一个基于数组实现的后进先出（LIFO集合类型，常用于需要栈行为的场景，如表达式求值、递归模拟、括号匹配等。与 Queue<T> 类似，它也使用数组进行内部存储，但其行为逻辑和操作顺序完全不同。

---

一、类结构与字段说明

 public class Stack<T> : IEnumerable<T>,System.Collections.ICollection,IReadOnlyCollection<T>
{
	private T[] _array;     // 存储栈元素的数组
	private int _size;      // 当前栈中元素的数量
	private int _version;   // 用于枚举器同步，防止在遍历时修改栈
	private const int DefaultCapacity = 4; // 默认初始容量
}

• 实现了 IEnumerable<T>、ICollection 和 IReadOnlyCollection<T> 接口，支持枚举、集合操作和只读访问。
• _array：栈的底层存储结构，所有元素都存放在这个数组中。
• _size：栈顶指针，表示当前栈中元素的数量，也表示下一个插入的位置。
• _version：用于防止在 foreach 等遍历过程中修改栈导致异常（如 InvalidOperationException）。

---

二、 构造函数

1. 无参构造函数

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

• 初始化一个空栈，使用空数组 _array = Array.Empty<T>()。
• 不立即分配内存，首次 Push 时会动态扩容。

2. 指定容量构造函数

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

• 初始化一个指定容量的栈。
• 如果容量为 0，则仍使用空数组。

3. 使用集合构造

public Stack(IEnumerable<T> collection)
{
    _array = EnumerableHelpers.ToArray(collection, out _size);
}

• 将传入的集合内容压入栈中，按顺序从 collection 的枚举器读取元素依次压栈（即顺序相反）。

---

三、 核心操作方法

Push(T item)：入栈

public void Push(T item)
{
    int size = _size;
    T[] array = _array;

    if ((uint)size < (uint)array.Length)
    {
        array[size] = item;
        _version++;
        _size = size + 1;
    }
    else
    {
        PushWithResize(item);
    }
}

private void PushWithResize(T item)
{
    // 如果当前数组为空（长度为0），则扩容为默认容量（DefaultCapacity = 4）
    // 否则，扩容为当前容量的 2 倍
    Array.Resize(ref _array, (_array.Length == 0) ? DefaultCapacity : 2 * _array.Length);

    // 将新元素插入到当前栈顶位置（即原 _size 位置）
    _array[_size] = item;
    _version++;
    _size++;
}

• 如果数组未满，则直接插入到 _array[_size] 位置。
• 如果数组已满，则调用 PushWithResize 扩容（默认扩容为原来的 2 倍）。
• 时间复杂度：O(1)（均摊），因为扩容操作是指数级增长。

Pop()：出栈

public T Pop()
{
    int size = _size - 1;
    if ((uint)size >= (uint)_array.Length)
        ThrowForEmptyStack();

    _version++;
    _size = size;
    T item = _array[size];
    if (RuntimeHelpers.IsReferenceOrContainsReferences<T>())
        _array[size] = default!;
    return item;
}

• 栈顶元素是 _array[_size - 1]。
• 出栈后 _size--，并清除引用以帮助 GC 回收。
• 时间复杂度：O(1)

Peek()：查看栈顶元素

public T Peek()
{
    int size = _size - 1;
    if ((uint)size >= (uint)_array.Length)
        ThrowForEmptyStack();
    return _array[size];
}

• 返回栈顶元素但不移除。
• 时间复杂度：O(1)

TryPop(out T result) 与 TryPeek(out T result)

public bool TryPop([MaybeNullWhen(false)] out T result)
{
    int size = _size - 1;
    T[] array = _array;

    if ((uint)size >= (uint)array.Length)
    {
        result = default!;
        return false;
    }

    _version++;
    _size = size;
    result = array[size];
    if (RuntimeHelpers.IsReferenceOrContainsReferences<T>())
    {
        array[size] = default!;
    }
    return true;
}

public bool TryPeek([MaybeNullWhen(false)] out T result)
{
    int size = _size - 1;
    T[] array = _array;

    if ((uint)size >= (uint)array.Length)
    {
        result = default!;
        return false;
    }
    result = array[size];
    return true;
}

• 安全版本的 Pop() 和 Peek()，不会抛出异常。
• 返回值为 bool，表示是否成功获取元素。

---

四、 查询与判断方法

Contains(T item)：判断栈中是否包含某个元素

public bool Contains(T item)
{
    return _size != 0 && Array.LastIndexOf(_array, item, _size - 1) != -1;
}

• 使用 Array.LastIndexOf 从栈顶开始查找，效率不高。
• 时间复杂度：O(n)

Count：获取栈中元素数量

public int Count => _size;

• 时间复杂度：O(1)

---

五、 清空与清理操作

Clear()：清空栈

public void Clear()
{
    if (RuntimeHelpers.IsReferenceOrContainsReferences<T>())
        Array.Clear(_array, 0, _size);
    _size = 0;
    _version++;
}

• 清除所有元素引用，释放内存。
• 时间复杂度：O(1)（如果是值类型）或 O(n)（如果是引用类型）

---

六、 数据复制与转换

ToArray()：将栈内容复制为数组

public T[] ToArray()
{
    T[] objArray = new T[_size];
    for (int i = 0; i < _size; i++)
    {
        objArray[i] = _array[_size - i - 1];
    }
    return objArray;
}

• 返回一个数组，顺序与栈的出栈顺序一致（即从栈顶到栈底）。
• 时间复杂度：O(n)

CopyTo(T[] array, int arrayIndex)：复制到目标数组

public void CopyTo(T[] array, int arrayIndex)
{
    // 从栈顶到栈底复制
    int srcIndex = 0;
    int dstIndex = arrayIndex + _size;
    while (srcIndex < _size)
    {
        array[--dstIndex] = _array[srcIndex++];
    }
}

• 与 ToArray() 类似，只是复制到指定数组位置。
• 时间复杂度：O(n)

---

七、 内存优化：TrimExcess()

public void TrimExcess()
{
    int threshold = (int)(_array.Length * 0.9);
    if (_size < threshold)
    {
        Array.Resize(ref _array, _size);
        _version++;
    }
}

• 如果当前栈中元素数量小于数组容量的 90%，则缩容。
• 避免浪费内存，适用于栈不再频繁扩容的场景。

---

八、迭代器

public struct Enumerator : IEnumerator<T>, System.Collections.IEnumerator
{
    // 引用当前正在被枚举的 Stack<T> 实例
    private readonly Stack<T> _stack;

    // 保存枚举开始时栈的版本号，用于检测是否在枚举期间被修改
    private readonly int _version;

    // 当前迭代的索引位置：
    // -2 表示尚未开始
    // -1 表示枚举已结束
    // >=0 表示当前访问的元素索引
    private int _index;

    // 缓存当前元素，供 Current 属性返回
    private T? _currentElement;

    // 构造函数，传入当前栈实例
    internal Enumerator(Stack<T> stack)
    {
        _stack = stack;
        _version = stack._version; // 保存当前版本号，用于后续版本检查
        _index = -2;               // 初始状态：未开始枚举
        _currentElement = default; // 初始为默认值
    }

    // 释放资源，标记枚举结束
    public void Dispose()
    {
        _index = -1; // 标记为枚举结束
    }

    // 移动到下一个元素
    public bool MoveNext()
    {
        bool retval;

        // 检查栈是否在枚举期间被修改（版本号不一致）
        if (_version != _stack._version)
            throw new InvalidOperationException(SR.InvalidOperation_EnumFailedVersion);

        // 第一次调用 MoveNext
        if (_index == -2)
        {
            // 定位到栈顶元素
            _index = _stack._size - 1;

            // 如果栈不为空，取出当前元素
            retval = (_index >= 0);
            if (retval)
                _currentElement = _stack._array[_index];

            return retval;
        }

        // 如果已结束枚举（调用过 Dispose 或多次 MoveNext 后超出范围），返回 false
        if (_index == -1)
        {
            return false;
        }

        // 移动到下一个元素（栈顶 -> 栈底）
        retval = (--_index >= 0);
        if (retval)
            _currentElement = _stack._array[_index];
        else
            _currentElement = default; // 枚举结束

        return retval;
    }

    // 获取当前元素
    public T Current
    {
        get
        {
            // 如果枚举未开始或已结束，抛出异常
            if (_index < 0)
                ThrowEnumerationNotStartedOrEnded();

            // 返回当前元素（非 null，因为已经通过 MoveNext 检查）
            return _currentElement!;
        }
    }

    // 抛出异常：枚举未开始或已结束
    private void ThrowEnumerationNotStartedOrEnded()
    {
        Debug.Assert(_index == -1 || _index == -2);
        throw new InvalidOperationException(
            _index == -2 
                ? SR.InvalidOperation_EnumNotStarted 
                : SR.InvalidOperation_EnumEnded);
    }

    // 非泛型接口的 Current 属性
    object? System.Collections.IEnumerator.Current
    {
        get { return Current; }
    }

    // 重置枚举器到初始状态
    void IEnumerator.Reset()
    {
        // 如果栈在枚举期间被修改过，抛出异常
        if (_version != _stack._version)
            throw new InvalidOperationException(SR.InvalidOperation_EnumFailedVersion);

        // 重置索引和当前元素
        _index = -2;
        _currentElement = default;
    }
}

---

总结注释要点

字段/方法	说明
_stack	当前被枚举的栈对象
_version	用于防止在枚举过程中修改栈
_index	控制枚举状态（-2=未开始，-1=结束，>=0=进行中）
MoveNext()	控制迭代器移动逻辑，从栈顶到栈底
Current	返回当前元素，枚举未开始或结束后抛出异常
Reset()	重置枚举器
Dispose()	标记枚举结束，防止继续访问
ThrowEnumerationNotStartedOrEnded()	在非法访问 Current 时抛出异常

---

九、与 Queue 的对比总结

功能	Stack<T>	Queue<T>
数据结构	后进先出（LIFO）	先进先出（FIFO）
插入位置	栈顶（_size）	队尾（_tail）
删除位置	栈顶（_size - 1）	队头（_head）
扩容方式	原数组两倍	原数组两倍
清除引用	支持	支持
判断空	_size == 0	_size == 0
枚举顺序	栈顶 → 栈底	队头 → 队尾
ToArray() 顺序	栈顶 → 栈底	队头 → 队尾
枚举器版本控制	有 _version	有 _version

---

十、 Stack 与 Queue 迭代器对比分析

特性	Stack<T>.Enumerator	Queue<T>.Enumerator
接口实现	实现 IEnumerator<T> 和 IEnumerator	同样实现 IEnumerator<T> 和 IEnumerator
结构类型	struct（值类型）	struct（值类型）
遍历顺序	从栈顶到栈底（LIFO）	从队头到队尾（FIFO）
索引控制	_index 从 _size - 1 递减到 0	_head 到 _tail，循环队列处理
缓存当前元素	_currentElement	_currentElement
版本控制	使用 _version 防止枚举期间修改栈	使用 _version 防止枚举期间修改队列
Reset() 方法	支持，重置为初始状态	支持，重置为初始状态
Dispose() 方法	设置 _index = -1 表示结束	设置 _index = -1 表示结束
Current 属性	枚举未开始或结束后访问抛异常	同上
非泛型 Current	返回 Current（兼容性）	同上

---

Stack<T> 遍历顺序（LIFO）

栈顶 → 4
        ↓
        3
        ↓
        2
        ↓
栈底 → 1

遍历顺序：4 → 3 → 2 → 1

Queue<T> 遍历顺序（FIFO）

队头 → 1 → 2 → 3 → 4 ← 队尾

遍历顺序：1 → 2 → 3 → 4

---

十一、 总结

Stack<T> 是一个基于数组实现的 LIFO 集合，具有高效的插入和删除操作，适用于需要后进先出逻辑的场景。它与 Queue<T> 在结构上类似，但行为逻辑完全不同，适用于不同类型的算法和数据处理需求。

---