C#栈和队列的简介,算法与应用简单实例

C#栈和队列的简介

什么是栈和队列？

栈(Stack)和队列(Queue)是两种常用的数据结构，它们都是线性数据结构。

栈就像是一个箱子，我们往箱子里放入物品（压栈），并取出箱子里面的物品（弹栈）。

队列就像是一条排队的队伍，我们往队伍的尾部加入一个人（入队），并从队伍的头部取出一个人（出队）。

算法

栈(Stack)

1.入栈（Push）：将一个元素加入栈顶。

2.出栈（Pop）：删除栈顶的元素，同时返回这个元素。

3.查看栈顶元素（Peek）：返回栈顶元素，但不删除它。

4.栈的判空（IsEmpty）：判断栈是否为空，如果为空返回True，反之返回False。

队列(Queue)

1.入队（Enqueue）：向队列尾部添加一个元素。

2.出队（Dequeue）：返回队列头部的元素并将其从队列中删除。

3.查看队列头部元素（Peek）：返回队列头部的元素，但不删除它。

4.队列的长度（Count）：返回队列中元素的个数。

应用

栈(Stack)

1.平衡符号检查：检查表达式中的符号是否配对，如圆括号、方括号、大括号等。

示例代码：

public bool CheckSyntax(string expression)
{
    Stack<char> stack = new Stack<char>();

    foreach(char c in expression)
    {
        if(c == '(' || c == '{' || c == '[')
        {
            stack.Push(c);
        }
        else if(c == ')' || c == '}' || c == ']')
        {
            if(stack.Count == 0) return false;

            char top = stack.Pop();

            if((c == ')' && top != '(') || (c == '}' && top != '{') || (c == ']' && top != '['))
            {
                return false;
            }
        }
    }

    return stack.Count == 0;
}

2.逆波兰式计算器：将中缀表达式转换为后缀表达式（逆波兰式），然后用栈计算后缀表达式的值。

示例代码：

public double Calculate(string expression)
{
    Stack<double> stack = new Stack<double>();
    string[] tokens = expression.Split(' ');

    foreach(string token in tokens)
    {
        if(double.TryParse(token, out double number))
        {
            stack.Push(number);
        }
        else
        {
            double right = stack.Pop();
            double left = stack.Pop();

            switch(token)
            {
                case "+":
                    stack.Push(left + right);
                    break;
                case "-":
                    stack.Push(left - right);
                    break;
                case "*":
                    stack.Push(left * right);
                    break;
                case "/":
                    stack.Push(left / right);
                    break;
            }
        }
    }

    return stack.Pop();
}

队列(Queue)

1.广度优先搜索(BFS)：在图或树等数据结构中进行的一种搜索算法，简单来说就是从起点开始，一层层向周围扩展，直到找到终点。

示例代码：

public void BFS(Node root)
{
    Queue<Node> queue = new Queue<Node>();
    HashSet<Node> visited = new HashSet<Node>();

    queue.Enqueue(root);
    visited.Add(root);

    while(queue.Count > 0)
    {
        Node node = queue.Dequeue();
        Console.WriteLine(node.Value);

        foreach(Node neighbor in node.Neighbors)
        {
            if(!visited.Contains(neighbor))
            {
                queue.Enqueue(neighbor);
                visited.Add(neighbor);
            }
        }
    }
}

2.生产者和消费者模式：利用队列实现线程间的协作，生产者负责生产数据，消费者负责消费数据，共同维护一个队列，生产者将数据放入队列尾部，消费者从队列头部取出数据。

示例代码：

public class ProducerConsumer
{
    private Queue<int> queue = new Queue<int>();
    private object locker = new object();

    public void Produce()
    {
        while(true)
        {
            int number = GenerateNumber();

            lock(locker)
            {
                queue.Enqueue(number);
                Console.WriteLine("Produced: " + number);
            }

            Thread.Sleep(1000);
        }
    }

    public void Consume()
    {
        while(true)
        {
            int number;

            lock(locker)
            {
                if(queue.Count == 0)
                    continue;

                number = queue.Dequeue();
                Console.WriteLine("Consumed: " + number);
            }

            Thread.Sleep(2000);
        }
    }
}