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, Peek | Enqueue, 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 原则。它们在算法设计、任务调度、表达式求值等场景中有着广泛的应用。通过本文的学习,你应该能够理解堆栈和队列的基本概念、操作方法以及实际应用。
附加资源与练习
- 练习 1:尝试实现一个堆栈,支持返回最小值(Min Stack)。
- 练习 2:使用队列实现一个简单的消息队列系统。
- 推荐阅读:
提示
如果你对堆栈和队列的概念还有疑问,可以尝试在代码中多实践,或者参考相关的算法书籍和教程。