C#实现顺序栈和链栈的代码实例

C#实现顺序栈和链栈的代码实例可以分成以下几个步骤：

第一步：定义栈的数据结构

在C#中，我们可以使用class或者struct定义一个栈的数据结构。在这里，我们以class为例，定义一个名为Stack的类：

public class Stack<T>
{
    private T[] _items;
    private int _count;

    public Stack(int capacity)
    {
        _items = new T[capacity];
        _count = 0;
    }

    public void Push(T item)
    {
        if (_count >= _items.Length)
        {
            var newItems = new T[_items.Length * 2];
            Array.Copy(_items, newItems, _items.Length);
            _items = newItems;
        }

        _items[_count++] = item;
    }

    public T Pop()
    {
        if (_count <= 0)
            throw new InvalidOperationException("Stack is empty");

        var item = _items[--_count];
        _items[_count] = default(T);
        return item;
    }

    public T Peek()
    {
        if (_count <= 0)
            throw new InvalidOperationException("Stack is empty");

        return _items[_count - 1];
    }

    public bool IsEmpty => _count == 0;
}

在这个实现中，我们使用了一个泛型类型参数T来表示栈的元素类型，使用一个数组_items来保存栈的元素，使用一个整数_count来表示栈的元素个数。在构造函数中，我们使用参数capacity来指定栈的容量。

第二步：实现顺序栈

2.1 栈的创建

首先，我们需要定义一个顺序栈类ArrayStack，并在其中定义一个基于数组的栈实现，代码如下：

public class ArrayStack<T>
{
    private T[] _items;
    private int _count;

    public ArrayStack(int capacity)
    {
        _items = new T[capacity];
        _count = 0;
    }

    // ...
}

同样，我们使用了一个泛型类型参数T来表示栈的元素类型，使用一个数组_items来存储栈中的元素。然后，我们在构造函数中使用参数capacity作为数组的长度，并初始化count为0表示栈中没有任何元素。

2.2 栈的入栈

然后，我们可以实现两个基本的操作：入栈(push)和出栈(pop)。入栈操作将一个元素添加到栈中，代码如下：

public void Push(T item)
{
    if (_count >= _items.Length)
    {
        var newItems = new T[_items.Length * 2];
        Array.Copy(_items, newItems, _items.Length);
        _items = newItems;
    }

    _items[_count++] = item;
}

入栈操作将元素存储在数组的尾部，并将计数器加1。如果数组已经满了，我们将其扩展为原来的两倍。

2.3 栈的出栈

出栈操作是将栈顶元素弹出并返回它的值。如果栈是空的，那么出栈操作将抛出异常。下面是出栈操作的代码：

public T Pop()
{
    if (_count <= 0)
        throw new InvalidOperationException("Stack is empty");

    var item = _items[--_count];
    _items[_count] = default(T);
    return item;
}

出栈操作首先检查栈是否为空，然后将_count减1以获取栈顶元素的索引。接下来，我们从数组中删除该元素，并将其设置为默认值null或0。

至此，我们已经成功地实现了一个基于数组的顺序栈。

第三步：实现链栈

3.1 栈的创建

接下来，我们将实现一个基于链表的链栈。首先，我们需要定义节点类Node，代码如下：

public class Node<T>
{
    public T Value { get; }

    public Node<T> Next { get; set; }

    public Node(T value)
    {
        Value = value;
        Next = null;
    }
}

我们使用泛型类型参数T来表示节点的值类型，使用Value属性来访问节点的值，使用Next属性来访问指向下一个节点的引用。在节点类构造函数中，我们使用参数value来初始化节点的值，将Next属性设置为null。

然后，我们需要定义一个链式栈类LinkedStack，代码如下：

public class LinkedStack<T>
{
    private Node<T> _top;

    public LinkedStack()
    {
        _top = null;
    }

    // ...
}

我们使用泛型类型参数T来表示链栈元素的类型。在构造函数中，我们将栈顶节点_top初始化为null。

3.2 栈的入栈

然后我们可以定义一个入栈(push)方法，将一个元素压入栈中，代码如下：

public void Push(T item)
{
    var newNode = new Node<T>(item);
    newNode.Next = _top;
    _top = newNode;
}

入栈操作首先创建一个新节点newNode，其值为item。然后将新节点的Next属性设置为栈顶节点_top，然后将新节点指定为栈顶节点_top。

3.3 栈的出栈

接下来，我们实现出栈(pop)方法，将栈顶元素弹出并返回它的值，代码如下：

public T Pop()
{
    if (_top == null)
        throw new InvalidOperationException("Stack is empty");

    var item = _top.Value;
    _top = _top.Next;
    return item;
}

出栈操作首先检查栈是否为空。然后，我们获取栈顶元素的值，将_top指向下一个元素，并返回弹出的元素的值。

至此，我们已经成功地实现了一个基于链表的链栈。

示例

示例1：顺序栈使用示例

现在，我们可以使用顺序栈实现一个简单的括号匹配程序。我们需要对字符序列中的括号进行匹配，并报告任何非法的括号匹配。下面是程序的实现：

public bool IsValid(string input)
{
    var stack = new ArrayStack<char>(input.Length);

    foreach (var ch in input)
    {
        if (ch == '(' || ch == '[' || ch == '{')
        {
            stack.Push(ch);
        }
        else if (ch == ')' || ch == ']' || ch == '}')
        {
            if (stack.IsEmpty)
                return false;

            var top = stack.Pop();
            if ((top == '(' && ch != ')') || (top == '[' && ch != ']') || (top == '{' && ch != '}'))
                return false;
        }
    }

    return stack.IsEmpty;
}

上面的方法使用了一个顺序栈来保存左括号字符（'(', '[', '{'）。对于每个右括号字符（')', ']', '}'），我们从栈中弹出一个字符，并将其与当前字符进行比较。如果匹配，则继续进行下一个字符；否则，表示括号匹配非法，返回false。如果字符串处理完毕后栈为空，则表示括号匹配合法，返回true。

示例2：链栈使用示例

下面是一个示例程序，使用链栈实现基本的计算器：

public class Calculator
{
    private readonly LinkedStack<double> _stack;

    public Calculator()
    {
        _stack = new LinkedStack<double>();
    }

    public double Evaluate(string expression)
    {
        var tokens = expression.Split();
        foreach (var token in tokens)
        {
            switch (token)
            {
                case "+":
                    _stack.Push(_stack.Pop() + _stack.Pop());
                    break;
                case "-":
                    _stack.Push(-_stack.Pop() + _stack.Pop());
                    break;
                case "*":
                    _stack.Push(_stack.Pop() * _stack.Pop());
                    break;
                case "/":
                    var numerator = _stack.Pop();
                    var denominator = _stack.Pop();
                    _stack.Push(denominator / numerator);
                    break;
                default:
                    _stack.Push(double.Parse(token));
                    break;
            }
        }

        var result = _stack.Pop();
        if (!_stack.IsEmpty)
            throw new ArgumentException("Expression contains too many values");

        return result;
    }
}

上面的程序使用了一个链栈来保存运算符和操作数。对于输入表达式的每个单词（由空格分隔），我们根据语法规则将其转换为一个数字或一个运算符，并在栈上执行相应的操作。最后，我们从栈中弹出结果值，并检查栈是否为空（如果不为空，则表示表达式中包含过多的数字）。