异常教程

C# 堆栈（Stack）（建议收藏）

更新时间:

💡一则或许对你有用的小广告

欢迎加入小哈的星球 ，你将获得：专属的项目实战 / 1v1 提问 / Java 学习路线 / 学习打卡 / 每月赠书 / 社群讨论

截止目前， 星球 内专栏累计输出 90w+ 字，讲解图 3441+ 张，还在持续爆肝中.. 后续还会上新更多项目，目标是将 Java 领域典型的项目都整一波，如秒杀系统, 在线商城, IM 即时通讯，权限管理，Spring Cloud Alibaba 微服务等等，已有 3100+ 小伙伴加入学习 ，欢迎点击围观

前言

在编程世界中，数据结构是构建高效算法和程序的核心工具之一。其中，C# 堆栈（Stack） 作为一种经典的后进先出（LIFO）数据结构，因其简洁的逻辑和广泛的应用场景，成为开发者必须掌握的基础知识。无论是实现表达式求值、递归优化，还是浏览器历史记录功能，堆栈都能提供优雅的解决方案。本文将从基础概念出发，结合代码示例和实际案例，深入浅出地解析 C# 堆栈的原理与实践技巧。

堆栈的基本概念与 LIFO 原理

什么是堆栈？

堆栈（Stack）是一种遵循 后进先出（Last In, First Out） 原则的数据结构。想象一个图书馆的书架：当你将书籍一本本叠放时，最后一本放上去的书（顶部）必须最先被取出，而最底层的书只能在所有上层书籍被取出后才能访问。这种“先进后出”的特性，正是堆栈的核心逻辑。

LIFO 原理的直观比喻

用食堂的餐盘举例：当服务员将餐盘摞在托盘上时，每个新餐盘都会被放在最上面。当需要取用时，只能从顶部开始逐层取出。这种“后进先出”的模式，正是堆栈工作的直观体现。

C# 中的堆栈实现与常用操作

Stack 类的介绍

在 C# 中，堆栈通过 System.Collections.Generic.Stack<T> 类实现。该类提供了以下核心方法：

  • Push(T item)：将元素压入堆栈顶部。
  • Pop()：移除并返回堆栈顶部的元素。
  • Peek()：返回堆栈顶部的元素，但不移除它。
  • Count：获取堆栈中元素的数量。

示例代码：基础操作演示

Stack<int> numbers = new Stack<int>();
numbers.Push(10); // 压入元素 10
numbers.Push(20); // 压入元素 20
numbers.Push(30); // 压入元素 30

Console.WriteLine(numbers.Peek()); // 输出 30（顶部元素）
Console.WriteLine(numbers.Pop());  // 移除并返回 30，堆栈变为 [10, 20]
Console.WriteLine(numbers.Count);  // 输出 2

泛型与非泛型的区别

C# 提供了两种堆栈实现：

  1. 泛型堆栈 Stack<T>：通过类型参数 <T> 确保元素类型一致，避免类型转换错误，推荐优先使用。
  2. 非泛型堆栈 Stack：存储 object 类型元素，需手动进行类型转换，灵活性较低。

示例代码：泛型与非泛型对比

// 泛型堆栈
Stack<string> names = new Stack<string>();
names.Push("Alice");
string first = names.Pop(); // 直接获取 string 类型，无需转换

// 非泛型堆栈
Stack nonGeneric = new Stack();
nonGeneric.Push("Bob");
string second = (string)nonGeneric.Pop(); // 需要显式类型转换

堆栈的典型应用场景

场景一：表达式求值与逆波兰表达式

堆栈在解析数学表达式时表现优异。例如，逆波兰表达式（后缀表达式）的计算需要通过堆栈暂存操作数，按顺序执行运算。

示例代码：逆波兰表达式求值

public static int EvaluatePostfix(string expression)
{
    Stack<int> stack = new Stack<int>();
    string[] tokens = expression.Split(' ');

    foreach (string token in tokens)
    {
        if (int.TryParse(token, out int num))
        {
            stack.Push(num);
        }
        else
        {
            int b = stack.Pop();
            int a = stack.Pop();
            switch (token)
            {
                case "+": stack.Push(a + b); break;
                case "-": stack.Push(a - b); break;
                case "*": stack.Push(a * b); break;
                case "/": stack.Push(a / b); break;
            }
        }
    }
    return stack.Pop();
}

// 使用示例：计算 "3 4 + 5 *"
int result = EvaluatePostfix("3 4 + 5 *"); // 结果为 35

场景二：递归的替代方案

某些递归问题可以通过堆栈手动模拟，避免栈溢出风险。例如，深度优先搜索（DFS）算法常使用堆栈来替代递归实现。

示例代码：非递归 DFS 遍历

public static void DepthFirstSearch(Node root)
{
    Stack<Node> stack = new Stack<Node>();
    stack.Push(root);

    while (stack.Count > 0)
    {
        Node current = stack.Pop();
        Console.WriteLine(current.Value); // 访问节点

        foreach (Node child in current.Children)
        {
            stack.Push(child);
        }
    }
}

堆栈的性能与实现方式

堆栈的底层实现

C# 的 Stack<T> 类默认基于 动态数组 实现，其内部通过一个数组存储元素，并维护一个指向顶部的指针。当元素数量超过数组容量时，会自动扩容。

堆栈 vs 队列：性能对比

堆栈的 Push 和 Pop 操作时间复杂度为 O(1)，而队列的 Enqueue 和 Dequeue 操作（基于数组或链表）同样高效。但两者的区别在于：

  • 堆栈遵循 LIFO，队列遵循 FIFO（先进先出）。

对比表格

（以下表格与前一行空一行）
| 操作 | 堆栈（Stack） | 队列（Queue） |
|---------------|---------------------|----------------------|
| 添加元素 | Push（顶部） | Enqueue（队尾） |
| 移除元素 | Pop（顶部） | Dequeue（队首） |
| 时间复杂度 | O(1) | O(1) |
| 典型应用 | 表达式求值、递归 | 消息队列、任务调度 |

堆栈的进阶用法与注意事项

线程安全问题

在多线程环境下，Stack<T> 类并非线程安全。若需在并发场景中使用，可通过 SyncLock 或 ConcurrentStack<T> 类实现安全操作。

示例代码：线程安全的堆栈

// 使用 ConcurrentStack<T> 替代 Stack<T>
ConcurrentStack<int> threadSafeStack = new ConcurrentStack<int>();
threadSafeStack.Push(100);
int value;
threadSafeStack.TryPop(out value); // 安全地弹出元素

堆栈的深度与内存管理

堆栈的容量会随元素数量动态调整，但频繁的扩容可能影响性能。可通过 Capacity 属性预分配空间以优化效率。

示例代码：预分配容量

Stack<int> preAllocatedStack = new Stack<int>(100); // 初始容量为 100

结论

C# 堆栈（Stack） 是一种简单但强大的数据结构，其 LIFO 特性在表达式求值、递归替代、浏览器历史记录等场景中展现出独特优势。通过本文的解析，开发者不仅能掌握堆栈的基本操作，还能深入理解其实现原理和优化技巧。在实际开发中，合理选择堆栈的实现方式（如泛型 vs 非泛型、线程安全与否），并结合具体需求设计高效算法，是提升代码质量和性能的关键。

通过持续练习和实践，开发者将能够灵活运用堆栈这一工具，解决更复杂的编程挑战。

最新发布

查看更多文章