基本概念
泛型栈(Stack<T>)
栈是一种后进先出(LIFO, Last In First Out)的数据结构。栈中最后添加的元素最先被移除。可以把栈想象成一叠盘子,最后放上去的盘子最先被拿走。
泛型队列(Queue<T>)
队列是一种先进先出(FIFO, First In First Out)的数据结构。队列中第一个添加的元素最先被移除。可以把队列想象成排队买票,最先排队的人最先买到票。
语法规则及声明
在 C# 中,栈和队列都有泛型版本,分别是 Stack<T>
和 Queue<T>
,它们都在 System.Collections.Generic
命名空间下。
声明栈和队列
csharp
Copy
// 声明一个存储整数的栈
Stack<int> stack = new Stack<int>();
// 声明一个存储字符串的队列
Queue<string> queue = new Queue<string>();
常用方法
栈(Stack<T>)
Push(T item)
:将元素压入栈顶。Pop()
:移除并返回栈顶元素。Peek()
:返回栈顶元素但不移除。Count
:获取栈中元素的数量。Clear()
:清空栈中的所有元素。
队列(Queue<T>)
Enqueue(T item)
:将元素添加到队列的末尾。Dequeue()
:移除并返回队列的头部元素。Peek()
:返回队列的头部元素但不移除。Count
:获取队列中元素的数量。Clear()
:清空队列中的所有元素。
示例代码及解释
示例1:栈的基本操作
using System;
using System.Collections.Generic;
public class Program
{
public static void Main()
{
Stack<int> stack = new Stack<int>();
// 压入元素
stack.Push(1);
stack.Push(2);
stack.Push(3);
// 输出栈顶元素但不移除
Console.WriteLine($"Peek: {stack.Peek()}"); // 输出 3
// 移除并输出栈顶元素
Console.WriteLine($"Pop: {stack.Pop()}"); // 输出 3
// 再次输出栈顶元素但不移除
Console.WriteLine($"Peek: {stack.Peek()}"); // 输出 2
// 输出栈中元素的数量
Console.WriteLine($"Count: {stack.Count}"); // 输出 2
}
}
示例2:队列的基本操作
using System;
using System.Collections.Generic;
public class Program
{
public static void Main()
{
Queue<string> queue = new Queue<string>();
// 添加元素到队列末尾
queue.Enqueue("Alice");
queue.Enqueue("Bob");
queue.Enqueue("Charlie");
// 输出队列头部元素但不移除
Console.WriteLine($"Peek: {queue.Peek()}"); // 输出 "Alice"
// 移除并输出队列头部元素
Console.WriteLine($"Dequeue: {queue.Dequeue()}"); // 输出 "Alice"
// 再次输出队列头部元素但不移除
Console.WriteLine($"Peek: {queue.Peek()}"); // 输出 "Bob"
// 输出队列中元素的数量
Console.WriteLine($"Count: {queue.Count}"); // 输出 2
}
}
在游戏开发中的用途
栈在游戏开发中的用途
撤销操作:保存玩家的操作记录,以便玩家可以撤销之前的操作。
递归处理:用于处理递归算法,如迷宫求解、深度优先搜索等。
状态管理:保存游戏状态栈,以实现状态的回退和恢复。
队列在游戏开发中的用途
任务队列:管理游戏中的任务队列,按顺序处理任务。
事件处理:处理游戏中的事件队列,按顺序处理事件。
路径查找:用于广度优先搜索(BFS)算法,查找最短路径。
优点和缺点
栈的优点和缺点
优点:
操作简单,时间复杂度为 O(1)。
适用于后进先出的场景。
缺点:
只能访问栈顶元素,限制了操作的灵活性。
不适合需要随机访问的场景。
队列的优点和缺点
优点:
操作简单,时间复杂度为 O(1)。
适用于先进先出的场景。
缺点:
只能访问队列头部元素,限制了操作的灵活性。
不适合需要随机访问的场景。
基础题目和进阶题目
基础题目
创建一个
Stack<int>
,压入 5 个整数,然后依次弹出并输出这些整数。创建一个
Queue<string>
,添加一些名字,然后依次移除并输出这些名字。创建一个
Stack<char>
,实现一个方法,检查字符串中的括号是否匹配。
进阶题目
创建一个
Stack<int>
,实现一个方法,反转栈中的元素顺序。创建一个
Queue<int>
,实现一个方法,计算队列中所有元素的平均值。使用
Queue<int>
实现一个简单的任务调度系统,每个任务有一个执行时间,按顺序执行每个任务并输出执行顺序。使用
Stack<int>
实现一个简单的计算器,支持加减乘除操作。