1. Python技术站首页
  2. 其他
  3. C#

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

• 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;
    }
}

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

本站文章如无特殊说明，均为本站原创，如若转载，请注明出处：C#实现顺序栈和链栈的代码实例 - Python技术站

赞 (0)
0 0 打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2023年6月7日
下一篇 2023年6月7日

相关文章

  • C#中的分布式ID生成组件IDGen介绍并给出示例代码

    C#中的IDGen是一个C#实现的Twitter Snowflake算法的ID生成器，可以生成全局唯一的ID，支持高并发场景下的ID生成。在本篇文章中，我们将介绍IDGen的使用方法并提供相关的C#示例代码。 IDGen的介绍 IDGen是一款开源的分布式唯一ID生成器，支持多种ID生成算法，并且可以在高并发场景下快速生成全局唯一的ID。目前支持的ID生成算…

    C# 2023年4月24日
    00

  • C#如何修改项目名图文详解

    下面是关于“C#如何修改项目名”的完整攻略，包含两条示例： C#如何修改项目名 1. 手动修改项目名 步骤 1：关闭 Visual Studio 在修改项目名称之前，首先需要关闭 Visual Studio。 步骤 2：重命名项目文件夹 在 Windows 资源管理器中，定位到你想要重命名的项目文件夹。右键单击该文件夹，并选择“重命名”。输入你想要的项目名称…

    C# 2023年5月15日
    00

  • C# Entity Framework中的IQueryable和IQueryProvider详解

    C# Entity Framework中的IQueryable和IQueryProvider详解 什么是IQueryable和IQueryProvider 在C#的Entity Framework中，IQueryable和IQueryProvider是两个重要的接口，它们负责处理LINQ查询操作和将其转换为的SQL语句。 简单来说，IQueryable表示一…

    C# 2023年6月1日
    00

  • 浅谈Async和Await如何简化异步编程（几个实例让你彻底明白）

    浅谈Async和Await如何简化异步编程 在JavaScript中异步编程显得非常重要，尤其是在处理网络请求等I / O操作时。ES6引入了Async和 Await两个关键字，它们可以使异步编程变得更加容易和更加易于阅读。本文将深入讲解Async / Await的使用方法，并通过几个实例来帮助读者更好地理解。 Async / Await的基础知识 Asyn…

    C# 2023年6月6日
    00

  • 使用Linq注意事项避免报错的方法

    使用Linq时要注意以下几点，以避免在代码中出现错误： 1. 空引用异常 在使用Linq时，一定要注意空引用异常，这通常是因为查询结果为 null，或者结果集中的某些数据为 null。 解决此问题的方法是，先要用 null 检查语句来确保在使用结果集中的某些属性时，结果集不为空。可以使用 ?? 运算符来处理 null 异常。 以下是一个示例代码，可以用于处理…

    C# 2023年5月14日
    00

  • ASP.NET Core中如何利用多种方式给Action传参

    在ASP.NET Core中，您可以使用多种方式将参数传递给Action。以下是一些常见的方法： 1. 通过路由参数传递参数 在ASP.NET Core中，您可以通过路由参数将参数传递给Action。以下是一个示例： [Route("products/{id}")] public IActionResult GetProduct(int …

    C# 2023年5月17日
    00

  • C# 泛型的约束

    下面是详细讲解 “C# 泛型的约束” 的完整攻略，包括概念、使用方法和示例说明等： 概念 在 C# 中，泛型是一种让类或方法可以支持多种数据类型的技术。泛型的优点是能够让程序更加灵活、可扩展，同时也避免了大量的重复代码。而泛型的约束则是用来限制泛型类型参数的类型或属性的限制条件，以确保泛型类型参数符合特定需求，比如实现某种接口、具有某种属性等。 使用方法 泛…

    C# 2023年5月31日
    00

  • C#中event内存泄漏总结

    下面是“C#中event内存泄漏总结”的完整攻略： 1. 内存泄漏是什么？ 所谓内存泄漏，指的是在编写代码时没有正确地释放不再需要的内存，导致程序占用过多的内存空间，从而影响程序的正常运行。 在C#中，经常会涉及到事件（event）的使用，而事件如果不处理好可能会导致内存泄漏问题。 2. 常见的event内存泄漏情况 2.1 订阅事件未取消 当一个对象注册了…

    C# 2023年5月15日
    00
合作推广
合作推广
分享本页
返回顶部