C#集合本质之堆栈的用法详解

什么是堆栈（Stack）？

堆栈是一种特殊的数据结构，它的特点是后进先出(Last In First Out, LIFO)。堆栈通常是通过数组或链表实现的，操作系统在进程调度、函数调用、表达式求值等方面广泛应用了堆栈。

C#堆栈的实现

C#中实现堆栈的数据结构有两种，一种是System.Collections.Stack类，另一种是System.Collections.Generic.Stack泛型类。

System.Collections.Stack

该类是C#在1.0版本时引入的，它的特点是线程安全，但在性能上较泛型类要慢。

Stack stack = new Stack();
stack.Push("A");
stack.Push("B");
stack.Push("C");

while (stack.Count > 0)
{
    Console.WriteLine(stack.Pop());
}

上述代码在堆栈中依次压入"A"、"B"、"C"三个元素，而后依次弹出并输出它们。输出结果为：

C
B
A

System.Collections.Generic.Stack

该类是C#在2.0版本时引入的，使用时需要使用命名空间System.Collections.Generic，它的特点是泛型，并且在性能上比非泛型类要快。

Stack<string> stack = new Stack<string>();
stack.Push("A");
stack.Push("B");
stack.Push("C");

while (stack.Count > 0)
{
    Console.WriteLine(stack.Pop());
}

上述代码与前一个示例类似，只是使用了泛型类。输出结果也与前一个示例相同。

堆栈的应用

堆栈的应用十分广泛，以下是两个实际的应用示例。

括号匹配

代码中使用堆栈来解决括号匹配的问题。

public bool IsValid(string s) {
    Stack<char> stack = new Stack<char>();
    for (int i = 0, length = s.Length; i < length; i++) {
        char ch = s[i];
        if (ch == '(' || ch == '[' || ch == '{') {
            stack.Push(ch);
        } else {
            if (stack.Count == 0) {
                return false;
            }
            char top = stack.Pop();
            if (ch == ')' && top != '(') {
                return false;
            }
            if (ch == ']' && top != '[') {
                return false;
            }
            if (ch == '}' && top != '{') {
                return false;
            }
        }
    }
    return stack.Count == 0;
}

代码中使用堆栈来保存左括号，并在遇到右括号时进行匹配，匹配失败则返回false。

逆序输出单词

代码中使用堆栈来逆序输出单词。

public string ReverseWords(string s) {
    StringBuilder sb = new StringBuilder();
    Stack<char> stack = new Stack<char>();
    for (int i = 0, length = s.Length; i < length; i++) {
        char ch = s[i];
        if (ch != ' ') {
            stack.Push(ch);
        } else {
            while (stack.Count > 0) {
                sb.Append(stack.Pop());
            }
            sb.Append(' ');
        }
    }
    while (stack.Count > 0) {
        sb.Append(stack.Pop());
    }
    return sb.ToString();
}

代码中将每个单词的字母按照顺序压入堆栈中，当遇到空格时逆序输出。最后返回逆序后的字符串。

小结

本文详细介绍了C#中堆栈的实现和应用，堆栈是一种经典的数据结构，在算法中应用广泛。