本文共 2566 字，大约阅读时间需要 8 分钟。
Stack（栈）是一种先进后出（LIFO）的数据结构，常用于管理程序运行时的方法调用顺序。在 .NET 中，Stack 类位于 System.dll 文件中，实现的逻辑位于 mscorlib.dll 的第 330 行。由于我们只关注泛型栈，因此需要调试 System.dll 来分析其内部逻辑。
在调试符号中选择添加 System.dll 即可轻松进入调试模式，这对 VS 的用户来说无疑是大大的便利。通过这种方式，我们可以直接查看栈的内部实现，深入了解其工作原理，从而更好地优化代码开发流程。
Stack 的内部实现主要依赖动态数组和一些控制变量。以下是实现细节：
1. `_size`：表示当前栈的大小，用于控制数组中指针的位置。
2. `_array`：存储实际数据的动态数组，类型由泛型 T 决定。
3. `_num`：原先用于扩容时的计算字段，现已被 `_size` 取代。
4. `_defaultCapacity`：默认扩容时的容量大小，通常为 4。
5. `_emptyArray`：一个静态空数组，用于初始化栈。
6. `_version`：用于检测数组结构发生变化的版本号。
Stack 提供多个构造函数以满足不同使用场景：
1. `public Stack()`：默认构造函数，初始化时使用空数组 `_emptyArray`。
2. `public Stack(int capacity)`：指定初始容量，直接创建大小为 capacity 的数组。
3. `public Stack(IEnumerable
Push 操作将一个项添加到栈顶部。实现细节如下：
1. 检查当前栈是否已满，如果已满则扩容。
2. 扩容时创建新数组，大小为当前数组大小的两倍（或默认容量 4），并将现有数据复制到新数组中。
3. 将新项添加到栈顶，更新 `_size`。
4. 更新 `_version`，用于区分不同版本的栈实例。
Pop 操作从栈顶部移除一个项。实现细节如下：
1. 检查栈是否为空，若为空抛出异常。
2. 更新 `_version`。
3. 从 `_size` 递减的位置取出项，并将该位置设置为默认值（即数组中对应位置的 T 类型的默认值）。
4. 返回被移除的项。
Peek 操作允许开发者查看栈顶部的项而不移除它。实现细节如下：
1. 检查栈是否为空，若为空抛出异常。
2. 直接访问 `_array[_size - 1]`，返回栈顶部的项。
Contains 操作用于检查栈中是否存在指定的项。实现细节如下：
1. 遍历从 `_head` 到 `_tail` 的所有项（从栈底部到栈顶部）。
2. 使用 `EqualityComparer.Default` 比较项是否存在。
3. 如果找到匹配项返回 `true`，否则返回 `false`。
Queue（队列）是一种先进先出（FIFO）的数据结构，在 .NET 中由 Queue 类实现，内部实现位于 mscorlib.dll 的第 471 行。与 Stack 不同，Queue 使用两个指针（_head 和 _tail）来管理数据的插入和移除操作。
Queue 的内部实现主要依赖以下字段：
1. `_array`：存储数据的动态数组。
2. `_head`：指针，指向队列的当前头部项的位置。
3. `_tail`：指针，指向队列的当前尾部项的位置。
4. `_size`：表示队列中当前有多少项。
5. `_DefaultCapacity`：默认扩容时的容量大小，通常为 4。
6. `_emptyArray`：静态空数组，用于初始化队列。
Queue 提供多个构造函数：
1. `public Queue()`：默认构造函数，初始化时使用空数组 `_emptyArray`。
2. `public Queue(int capacity)`：指定初始容量，创建大小为 capacity 的数组。
3. `public Queue(IEnumerable
Enqueue 操作将一个项添加到队列末尾。实现细节如下：
1. 检查是否有空间，如果没有空间调用 `SetCapacity` 方法扩容。
2. 更新 `_tail` 指针到下一个位置。
3. 更新 `_size`。
4. 更新 `_version`。
Dequeue 操作从队列头部移除一个项。实现细节如下：
1. 检查是否为空，若为空抛出异常。
2. 将 `_head` 指针移动到下一个位置，并将该位置的项设置为 null。
3. 更新 `_size` 和 `_version`。
4. 返回被移除的项。
Peek 操作允许开发者查看队列头部的项而不移除它。实现细节如下：
1. 检查是否为空，若为空抛出异常。
2. 返回 `_array[_size]` 中的项。
Contains 操作用于检查队列中是否存在指定的项。实现细节如下：
1. 从 `_head` 到 `_tail` 遍历所有项。
2. 使用 `EqualityComparer.Default` 比较项是否存在。
3. 返回 `true` 或 `false`。
Queue 提供一个枚举器，允许开发者遍历队列中的所有项。默认枚举器通过循环 `_array` 并从 `_head` 到 `_tail` 检查每个位置是否不为空来获取项。
通过调用 `GetEnumerator()` 方法可以获取枚举器实例。
转载地址：http://lcgfk.baihongyu.com/