OneBigLoser
OneBigLoser
发布于 2024-07-20 / 23 阅读
0
0

泛型栈(Stack<T>)和泛型队列(Queue<T>)

基本概念

泛型栈(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
    }
}

在游戏开发中的用途

栈在游戏开发中的用途

  1. 撤销操作:保存玩家的操作记录,以便玩家可以撤销之前的操作。

  2. 递归处理:用于处理递归算法,如迷宫求解、深度优先搜索等。

  3. 状态管理:保存游戏状态栈,以实现状态的回退和恢复。

队列在游戏开发中的用途

  1. 任务队列:管理游戏中的任务队列,按顺序处理任务。

  2. 事件处理:处理游戏中的事件队列,按顺序处理事件。

  3. 路径查找:用于广度优先搜索(BFS)算法,查找最短路径。

优点和缺点

栈的优点和缺点

优点

  1. 操作简单,时间复杂度为 O(1)。

  2. 适用于后进先出的场景。

缺点

  1. 只能访问栈顶元素,限制了操作的灵活性。

  2. 不适合需要随机访问的场景。

队列的优点和缺点

优点

  1. 操作简单,时间复杂度为 O(1)。

  2. 适用于先进先出的场景。

缺点

  1. 只能访问队列头部元素,限制了操作的灵活性。

  2. 不适合需要随机访问的场景。

基础题目和进阶题目

基础题目

  1. 创建一个 Stack<int>,压入 5 个整数,然后依次弹出并输出这些整数。

  2. 创建一个 Queue<string>,添加一些名字,然后依次移除并输出这些名字。

  3. 创建一个 Stack<char>,实现一个方法,检查字符串中的括号是否匹配。

进阶题目

  1. 创建一个 Stack<int>,实现一个方法,反转栈中的元素顺序。

  2. 创建一个 Queue<int>,实现一个方法,计算队列中所有元素的平均值。

  3. 使用 Queue<int> 实现一个简单的任务调度系统,每个任务有一个执行时间,按顺序执行每个任务并输出执行顺序。

  4. 使用 Stack<int> 实现一个简单的计算器,支持加减乘除操作。


评论