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#保存图片到数据库并读取显示图片的方法

    整体思路 将图片转换为二进制，然后将二进制数据存储到数据库中，读取时从数据库中读取二进制数据，再将二进制数据转换为图片。 示范代码1：保存图片到数据库 首先，我们需要创建一个包含二进制数据的表格来存储图片。在该表格上创建两个字段：图片ID和图片内容。然后，使用下面的代码将图片转换为二进制数据，并将其插入到表格中： // 读取图片文件 FileStream f…

    C# 2023年6月2日
    00

  • windows mysql 自动备份的几种方法汇总

    Windows MySQL 自动备份的几种方法汇总 为什么需要自动备份 在使用 MySQL 数据库时，为了保护数据的安全性，我们需要进行备份操作。但是，手动备份数据是非常繁琐的，而且容易出现遗漏的情况。因此，使用自动备份工具可以提高备份的效率，也可以保证备份的全面性。 几种自动备份方法 1. 使用 mysqldump 命令进行备份 使用 mysqldump …

    C# 2023年5月31日
    00

  • C#并发实战记录之Parallel.ForEach使用

    C#并发实战记录之Parallel.ForEach使用 什么是 Parallel.ForEach？ Parallel.ForEach 是一个并行迭代器，它允许并行执行循环。简单的说，就是可以将一个大型的循环任务拆分成多个子任务，使得多个任务可以并行执行，提高执行效率。 如何使用 Parallel.ForEach？ Parallel.ForEach 的用法非常…

    C# 2023年6月6日
    00

  • C#队列Queue用法实例分析

    C#队列Queue用法实例分析 什么是队列？ 队列（queue）是一种先进先出（First-In-First-Out，FIFO）的数据结构，和栈（stack）不同，队列的两端分别称为队首（front）和队尾（rear）。在队列中，新元素插入到队尾（rear），而队首的元素一直存在队列中，直到到达队列的结尾。要从队列中删除元素，需要从队首开始，一直到要删除的元…

    C# 2023年6月7日
    00

  • C# winform打印excel的方法

    下面是关于如何使用C# WinForm打印Excel的完整攻略，包含以下几个步骤： 1. 引用Excel Interop 要打印Excel，需要使用Microsoft Excel Interop库。这个库需要先引用才能在程序中使用。下面是引用Excel Interop的具体步骤： 在Visual Studio的工具栏中选择“项目”。 在项目中选择“添加引用”…

    C# 2023年6月7日
    00

  • C#查找字符串所有排列组合的方法

    我们可以使用递归的方法来查找字符串所有排列组合的方法。 首先，我们需要明确排列和组合的概念。排列指从n个不同元素中取出m个元素，有序排列成一列的所有可能情况。组合指从n个不同元素中取出m个元素，不考虑顺序的所有可能情况。 接下来，我们编写一个递归函数 PermuteString 来实现字符串的全排列： public static void PermuteSt…

    C# 2023年6月7日
    00

  • c# 复写Equals方法的实现

    针对您提供的主题“c# 复写Equals方法的实现”的完整攻略，我来介绍一下： 什么是Equals方法? 在C#中，Object类定义了一个名为Equals的方法，该方法用于判断两个对象是否相等。Equals方法的默认实现使用对象的引用来判断两个对象是否相等。如果两个对象引用同一个内存地址则返回true，否则返回false。因此，默认情况下，如果对象在堆上的…

    C# 2023年5月15日
    00

  • Unity实现已知落点和速度自动计算发射角度

    接下来我将对“Unity实现已知落点和速度自动计算发射角度”的攻略进行详细讲解，并提供两个示例说明。 一、问题背景 在某些游戏或模拟应用中，我们需要计算发射物体的发射角度，使其能够落到指定的位置，并且在指定的速度范围内运动。这时候我们不可能通过手动调整发射角度的方式来实现目标的达成，因为如果落点或速度范围改变，我们需要重新计算发射角度，这是非常麻烦的。因此，…

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