跳到主要内容

C# 堆栈与队列

介绍

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

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


堆栈(Stack)

什么是堆栈?

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

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

堆栈的基本操作

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

csharp
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:获取队列中元素的数量。

队列的基本操作

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

csharp
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:使用堆栈实现括号匹配

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

csharp
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:使用队列实现任务调度

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

csharp
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 原则。它们在算法设计、任务调度、表达式求值等场景中有着广泛的应用。通过本文的学习,你应该能够理解堆栈和队列的基本概念、操作方法以及实际应用。


附加资源与练习

提示

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