跳到主要内容

C# 堆栈与队列

介绍​

在 C# 中，堆栈（Stack）和队列（Queue）是两种常见的数据结构，它们分别遵循 后进先出（LIFO） 和 先进先出（FIFO） 的原则。堆栈和队列在编程中有着广泛的应用，例如在算法设计、任务调度、表达式求值等场景中。

本文将详细介绍堆栈和队列的概念、基本操作以及实际应用场景，并通过代码示例帮助初学者更好地理解。

堆栈（Stack）​

什么是堆栈？​

堆栈是一种遵循 后进先出（LIFO） 原则的数据结构。这意味着最后添加到堆栈中的元素会最先被移除。堆栈的常见操作包括：

  • Push：将元素添加到堆栈的顶部。
  • Pop：移除并返回堆栈顶部的元素。
  • Peek：返回堆栈顶部的元素但不移除它。
  • Count：获取堆栈中元素的数量。

堆栈的基本操作​

以下是一个简单的堆栈示例：

using System;
using System.Collections;

class Program
{
    static void Main()
    {
        // 创建一个堆栈
        Stack stack = new Stack();

        // 添加元素到堆栈
        stack.Push("Apple");
        stack.Push("Banana");
        stack.Push("Cherry");

        // 查看堆栈顶部的元素
        Console.WriteLine("Top element: " + stack.Peek()); // 输出: Cherry

        // 移除堆栈顶部的元素
        Console.WriteLine("Popped element: " + stack.Pop()); // 输出: Cherry

        // 遍历堆栈
        Console.WriteLine("Stack elements:");
        foreach (var item in stack)
        {
            Console.WriteLine(item);
        }
    }
}

输出：

Top element: Cherry
Popped element: Cherry
Stack elements:
Banana
Apple

堆栈的实际应用​

堆栈常用于以下场景：

  • 撤销操作：例如文本编辑器中的撤销功能，最后输入的内容最先撤销。
  • 递归算法：递归调用本质上使用了堆栈来保存函数调用的上下文。
  • 表达式求值：例如计算后缀表达式（逆波兰表达式）。

队列（Queue）​

什么是队列？​

队列是一种遵循 先进先出（FIFO） 原则的数据结构。这意味着最先添加到队列中的元素会最先被移除。队列的常见操作包括：

  • Enqueue：将元素添加到队列的末尾。
  • Dequeue：移除并返回队列开头的元素。
  • Peek：返回队列开头的元素但不移除它。
  • Count：获取队列中元素的数量。

队列的基本操作​

以下是一个简单的队列示例：

using System;
using System.Collections;

class Program
{
    static void Main()
    {
        // 创建一个队列
        Queue queue = new Queue();

        // 添加元素到队列
        queue.Enqueue("Apple");
        queue.Enqueue("Banana");
        queue.Enqueue("Cherry");

        // 查看队列开头的元素
        Console.WriteLine("Front element: " + queue.Peek()); // 输出: Apple

        // 移除队列开头的元素
        Console.WriteLine("Dequeued element: " + queue.Dequeue()); // 输出: Apple

        // 遍历队列
        Console.WriteLine("Queue elements:");
        foreach (var item in queue)
        {
            Console.WriteLine(item);
        }
    }
}

输出：

Front element: Apple
Dequeued element: Apple
Queue elements:
Banana
Cherry

队列的实际应用​

队列常用于以下场景：

  • 任务调度：例如打印任务队列，先提交的任务先执行。
  • 消息队列：例如在分布式系统中处理异步消息。
  • 广度优先搜索（BFS）：在图或树的遍历中使用队列来管理待访问的节点。

堆栈与队列的比较​

特性堆栈（Stack）队列（Queue）
原则后进先出（LIFO）先进先出（FIFO）
主要操作Push, Pop, PeekEnqueue, Dequeue, Peek
应用场景撤销操作、递归、表达式求值任务调度、消息队列、BFS

实际案例​

案例 1：使用堆栈实现括号匹配​

以下代码演示了如何使用堆栈检查字符串中的括号是否匹配：

using System;
using System.Collections;

class Program
{
    static bool IsBalanced(string input)
    {
        Stack stack = new Stack();
        foreach (char ch in input)
        {
            if (ch == '(' || ch == '[' || ch == '{')
            {
                stack.Push(ch);
            }
            else if (ch == ')' || ch == ']' || ch == '}')
            {
                if (stack.Count == 0) return false;
                char top = (char)stack.Pop();
                if ((ch == ')' && top != '(') ||
                    (ch == ']' && top != '[') ||
                    (ch == '}' && top != '{'))
                {
                    return false;
                }
            }
        }
        return stack.Count == 0;
    }

    static void Main()
    {
        string input = "({[]})";
        Console.WriteLine("Is balanced: " + IsBalanced(input)); // 输出: True
    }
}

输出：

Is balanced: True

案例 2：使用队列实现任务调度​

以下代码演示了如何使用队列管理任务调度：

using System;
using System.Collections;

class Program
{
    static void Main()
    {
        Queue taskQueue = new Queue();
        taskQueue.Enqueue("Task 1");
        taskQueue.Enqueue("Task 2");
        taskQueue.Enqueue("Task 3");

        while (taskQueue.Count > 0)
        {
            string task = (string)taskQueue.Dequeue();
            Console.WriteLine("Processing: " + task);
        }
    }
}

输出：

Processing: Task 1
Processing: Task 2
Processing: Task 3

总结​

堆栈和队列是 C# 中两种重要的数据结构，分别遵循 LIFO 和 FIFO 原则。它们在算法设计、任务调度、表达式求值等场景中有着广泛的应用。通过本文的学习，你应该能够理解堆栈和队列的基本概念、操作方法以及实际应用。

附加资源与练习​

提示

如果你对堆栈和队列的概念还有疑问，可以尝试在代码中多实践，或者参考相关的算法书籍和教程。