相思资源网

算法系列15天速成 第九天 队列
站长资源 2024/11/5 佚名
64 1538
相思资源网 Design By www.200059.com

一：概念

          队列是一个”先进先出“的线性表，牛X的名字就是“First in First Out(FIFO)”，生活中有很多这样的场景，比如读书的时候去食堂打饭时的”排队“。当然我们拒绝插队。

二：存储结构

         前几天也说过，线性表有两种”存储结构“，① 顺序存储,②链式存储。当然“队列”也脱离不了这两种服务，这里我就分享一下“顺序存储”。

     顺序存储时，我们会维护一个叫做”head头指针“和”tail尾指针“，分别指向队列的开头和结尾。

算法系列15天速成 第九天 队列


代码段如下：

复制代码 代码如下:
#region 队列的数据结构
    /// <summary>
/// 队列的数据结构
/// </summary>
/// <typeparam name="T"></typeparam>
    public class SeqQueue<T>
    {
        private const int maxSize = 100;

        public int MaxSize
        {
            get { return maxSize; }
        }

        /// <summary>
/// 顺序队列的存储长度
/// </summary>
        public T[] data = new T[maxSize];

        //头指针
        public int head;

        //尾指针
        public int tail;

    }
    #endregion

三：常用操作

      队列的操作一般分为：

      ①： 初始化队列。

      ②:   出队。

      ③： 入队。

      ④： 获取队头。

      ⑤： 获取队长。


1：初始化队列

        这个很简单，刚才也说过了，队列是用一个head和tail的指针来维护。分别设置为0即可。

2：出队

       看着“队列”的结构图，大家都知道，出队肯定跟head指针有关，需要做两件事情，

       第一： 判断队列是否为空，这个我想大家都知道。
       第二： 将head头指针向后移动一位，返回head移动前的元素，时间复杂度为O(1)。

算法系列15天速成 第九天 队列

代码段如下：

复制代码 代码如下:
#region 队列元素出队
        /// <summary>
/// 队列元素出队
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <returns></returns>
        public T SeqQueueOut<T>(SeqQueue<T> seqQueue)
        {
            if (SeqQueueIsEmpty(seqQueue))
                throw new Exception("队列已空，不能进行出队操作");

            var single = seqQueue.data[seqQueue.head];

            //head指针自增
            seqQueue.data[seqQueue.head++] = default(T);

            return single;

        }
        #endregion

3：入队

      这个跟”出队“的思想相反，同样也是需要做两件事情。

      第一：判断队列是否已满。

      第二：将tail指针向后移动一位，时间复杂度为O(1)。

代码段如下：

复制代码 代码如下:
#region 队列元素入队
        /// <summary>
/// 队列元素入队
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <param name="data"></param>
/// <returns></returns>
        public SeqQueue<T> SeqQueueIn<T>(SeqQueue<T> seqQueue, T data)
        {
            //如果队列已满，则不能进行入队操作
            if (SeqQueueIsFull(seqQueue))
                throw new Exception("队列已满,不能入队操作");

            //入队操作
            seqQueue.data[seqQueue.tail++] = data;

            return seqQueue;
        }
        #endregion

4： 获取队头

       知道”出队“和”入队“的原理，相信大家都懂的如何进行”获取队头“操作，唯一不一样的就是

       他是只读操作，不会破坏”队列“结构，时间复杂度为O（1）。

 

代码段如下：

复制代码 代码如下:
#region 获取队头元素
        /// <summary>
        /// 获取队头元素
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="seqQueue"></param>
        /// <returns></returns>
        public T SeqQueuePeek<T>(SeqQueue<T> seqQueue)
        {
            if (SeqQueueIsEmpty(seqQueue))
                throw new Exception("队列已空，不能进行出队操作");

            return seqQueue.data[seqQueue.head];
        }
        #endregion

5: 获取队长

       大家都知道，我们是用数组来实现队列，所以千万不要想当然的认为数组长度是XXX，

       我们维护的是一个head和tail的指针，所以长度自然就是tail-head咯，时间复杂度为O(1)。

算法系列15天速成 第九天 队列

代码段如下：

复制代码 代码如下:
/// <summary>
/// 获取队列长度
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <returns></returns>
        public int SeqQueueLen<T>(SeqQueue<T> seqQueue)
        {
            return seqQueue.tail - seqQueue.head;
        }

然后上一下总的运行代码：

复制代码 代码如下:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace SeqQueue
{
    public class Program
    {
        static void Main(string[] args)
        {
            SeqQueue<Student> seqQueue = new SeqQueue<Student>();

            SeqQueueClass queueManage = new SeqQueueClass();

            Console.WriteLine("目前队列是否为空：" + queueManage.SeqQueueIsEmpty(seqQueue) + "\n");

            Console.WriteLine("将ID=1和ID=2的实体加入队列");
            queueManage.SeqQueueIn(seqQueue, new Student() { ID = 1, Name = "hxc520", Age = 23 });
            queueManage.SeqQueueIn(seqQueue, new Student() { ID = 2, Name = "一线码农", Age = 23 });

            Display(seqQueue);

            Console.WriteLine("将队头出队");
            //将队头出队
            var student = queueManage.SeqQueueOut(seqQueue);

            Display(seqQueue);

            //获取队顶元素
            student = queueManage.SeqQueuePeek(seqQueue);

            Console.Read();
        }
        //展示队列元素
        static void Display(SeqQueue<Student> seqQueue)
        {
            Console.WriteLine("******************* 链表数据如下 *******************");

            for (int i = seqQueue.head; i < seqQueue.tail; i++)
                Console.WriteLine("ID:" + seqQueue.data[i].ID +
                                  ",Name:" + seqQueue.data[i].Name +
                                  ",Age:" + seqQueue.data[i].Age);

            Console.WriteLine("******************* 链表数据展示完毕 *******************\n");
        }
    }

    #region 学生数据实体
    /// <summary>
/// 学生数据实体
/// </summary>
    public class Student
    {
        public int ID { get; set; }

        public string Name { get; set; }

        public int Age { get; set; }
    }
    #endregion

    #region 队列的数据结构
    /// <summary>
/// 队列的数据结构
/// </summary>
/// <typeparam name="T"></typeparam>
    public class SeqQueue<T>
    {
        private const int maxSize = 100;

        public int MaxSize
        {
            get { return maxSize; }
        }

        /// <summary>
/// 顺序队列的存储长度
/// </summary>
        public T[] data = new T[maxSize];

        //头指针
        public int head;

        //尾指针
        public int tail;

    }
    #endregion

    #region 队列的基本操作
    /// <summary>
/// 队列的基本操作
/// </summary>
    public class SeqQueueClass
    {
        #region 队列的初始化操作
        /// <summary>
/// 队列的初始化操作
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
        public SeqQueue<T> SeqQueueInit<T>(SeqQueue<T> seqQueue)
        {
            seqQueue.head = 0;
            seqQueue.tail = 0;

            return seqQueue;
        }
        #endregion

        #region 队列是否为空
        /// <summary>
/// 队列是否为空
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <returns></returns>
        public bool SeqQueueIsEmpty<T>(SeqQueue<T> seqQueue)
        {
            //如果两指针重合，说明队列已经清空
            if (seqQueue.head == seqQueue.tail)
                return true;
            return false;
        }
        #endregion

        #region 队列是否已满
        /// <summary>
/// 队列是否已满
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <returns></returns>
        public bool SeqQueueIsFull<T>(SeqQueue<T> seqQueue)
        {
            //如果尾指针到达数组末尾，说明队列已经满
            if (seqQueue.tail == seqQueue.MaxSize)
                return true;
            return false;
        }
        #endregion

        #region 队列元素入队
        /// <summary>
/// 队列元素入队
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <param name="data"></param>
/// <returns></returns>
        public SeqQueue<T> SeqQueueIn<T>(SeqQueue<T> seqQueue, T data)
        {
            //如果队列已满，则不能进行入队操作
            if (SeqQueueIsFull(seqQueue))
                throw new Exception("队列已满,不能入队操作");

            //入队操作
            seqQueue.data[seqQueue.tail++] = data;

            return seqQueue;
        }
        #endregion

        #region 队列元素出队
        /// <summary>
/// 队列元素出队
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <returns></returns>
        public T SeqQueueOut<T>(SeqQueue<T> seqQueue)
        {
            if (SeqQueueIsEmpty(seqQueue))
                throw new Exception("队列已空，不能进行出队操作");

            var single = seqQueue.data[seqQueue.head];

            //head指针自增
            seqQueue.data[seqQueue.head++] = default(T);

            return single;

        }
        #endregion

        #region 获取队头元素
        /// <summary>
/// 获取队头元素
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <returns></returns>
        public T SeqQueuePeek<T>(SeqQueue<T> seqQueue)
        {
            if (SeqQueueIsEmpty(seqQueue))
                throw new Exception("队列已空，不能进行出队操作");

            return seqQueue.data[seqQueue.head];
        }
        #endregion

        /// <summary>
/// 获取队列长度
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <returns></returns>
        public int SeqQueueLen<T>(SeqQueue<T> seqQueue)
        {
            return seqQueue.tail - seqQueue.head;
        }
    }
    #endregion
}

算法系列15天速成 第九天 队列

三：顺序队列的缺陷

算法系列15天速成 第九天 队列

大家看这张图，不知道可有什么异样的感觉，在这种状态下，我入队操作，发现程序提示队列

已满，但是tnd我这个数组还有一个空间啊，是的，这就是所谓的“假溢出”。

四：循环队列
 

俗话说的好啊，“没有跨不过的坎”。

1: 概念

       之所以叫“循环”，得益于神奇的“%”。他让队列的首位进行相连，形成了一个我们思维中的

       “圈圈”。
 

2：循环公式

      tail=(tail+1)%array.Length;

      多看几眼，大家就看通了其中循环的道理，我要做成如下的图:

3：对循环的改造

      先前看了一些资料，有的压根就是错的，有的说想要循环，就要牺牲一个单位的空间。

      我觉得没必要。我既要循环又不牺牲空间，所以反射了一下framework中的Queue类。

      改造后代码如下：

复制代码 代码如下:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace SeqQueue
{
    public class Program
    {
        static void Main(string[] args)
        {
            SeqQueue<Student> seqQueue = new SeqQueue<Student>();

            SeqQueueClass queueManage = new SeqQueueClass();

            Console.WriteLine("目前队列是否为空：" + queueManage.SeqQueueIsEmpty(seqQueue) + "\n");

            Console.WriteLine("将ID=1，2，3的实体加入队列\n");
            queueManage.SeqQueueIn(seqQueue, new Student() { ID = 1, Name = "hxc520", Age = 23 });
            queueManage.SeqQueueIn(seqQueue, new Student() { ID = 2, Name = "一线码农", Age = 23 });
            queueManage.SeqQueueIn(seqQueue, new Student() { ID = 3, Name = "51cto", Age = 23 });

            Console.WriteLine("\n当前队列个数：" + queueManage.SeqQueueLen(seqQueue) + "");

            Console.WriteLine("\n*********************************************\n");

            Console.WriteLine("我要出队了\n");
            queueManage.SeqQueueOut(seqQueue);

            Console.WriteLine("哈哈，看看跟顺序队列异样之处，我再入队，看是否溢出\n");
            queueManage.SeqQueueIn(seqQueue, new Student() { ID = 4, Name = "博客园", Age = 23 });
            Console.WriteLine("\n....一切正常，入队成功");

            Console.WriteLine("\n当前队列个数：" + queueManage.SeqQueueLen(seqQueue) + "");

            Console.Read();
        }
    }

    #region 学生数据实体
    /// <summary>
/// 学生数据实体
/// </summary>
    public class Student
    {
        public int ID { get; set; }

        public string Name { get; set; }

        public int Age { get; set; }
    }
    #endregion

    #region 队列的数据结构
    /// <summary>
/// 队列的数据结构
/// </summary>
/// <typeparam name="T"></typeparam>
    public class SeqQueue<T>
    {
        private const int maxSize = 3;

        public int MaxSize
        {
            get { return maxSize; }
        }

        /// <summary>
/// 顺序队列的存储长度
/// </summary>
        public T[] data = new T[maxSize];

        //头指针
        public int head;

        //尾指针
        public int tail;

        //队列中有效的数字个数
        public int size;
    }
    #endregion

    #region 队列的基本操作
    /// <summary>
/// 队列的基本操作
/// </summary>
    public class SeqQueueClass
    {
        #region 队列的初始化操作
        /// <summary>
/// 队列的初始化操作
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
        public SeqQueue<T> SeqQueueInit<T>(SeqQueue<T> seqQueue)
        {
            seqQueue.size = seqQueue.head = seqQueue.tail = 0;

            return seqQueue;
        }
        #endregion

        #region 队列是否为空
        /// <summary>
/// 队列是否为空
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <returns></returns>
        public bool SeqQueueIsEmpty<T>(SeqQueue<T> seqQueue)
        {
            //如果两指针重合，说明队列已经清空
            if (seqQueue.size == 0)
                return true;
            return false;
        }
        #endregion

        #region 队列是否已满
        /// <summary>
/// 队列是否已满
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <returns></returns>
        public bool SeqQueueIsFull<T>(SeqQueue<T> seqQueue)
        {
            //采用循环队列后，头指针
            if (seqQueue.size == seqQueue.MaxSize)
                return true;
            return false;
        }
        #endregion

        #region 队列元素入队
        /// <summary>
/// 队列元素入队
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <param name="data"></param>
/// <returns></returns>
        public SeqQueue<T> SeqQueueIn<T>(SeqQueue<T> seqQueue, T data)
        {
            //如果队列已满，则不能进行入队操作
            if (SeqQueueIsFull(seqQueue))
                throw new Exception("队列已满，还入啥队列啊！");

            //采用循环队列,必须先赋值，在自增tail指针
            seqQueue.data[seqQueue.tail] = data;
            seqQueue.tail = (seqQueue.tail + 1) % seqQueue.MaxSize;

            //队列实际元素增加
            seqQueue.size++;

            return seqQueue;
        }
        #endregion

        #region 队列元素出队
        /// <summary>
/// 队列元素出队
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <returns></returns>
        public T SeqQueueOut<T>(SeqQueue<T> seqQueue)
        {
            if (SeqQueueIsEmpty(seqQueue))
                throw new Exception("队列已空，大哥，不要在出队了！");

            //循环队列出队，展现的是head的灵活性
            seqQueue.head = (seqQueue.head + 1) % seqQueue.MaxSize;

            //队列实际元素递减
            seqQueue.size--;

            return seqQueue.data[seqQueue.head];
        }
        #endregion

        #region 获取队头元素
        /// <summary>
/// 获取队头元素
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <returns></returns>
        public T SeqQueuePeek<T>(SeqQueue<T> seqQueue)
        {
            if (SeqQueueIsEmpty(seqQueue))
                throw new Exception("队列已空，不能进行出队操作");

            return seqQueue.data[seqQueue.head];
        }
        #endregion

        #region 获取队列长度
        /// <summary>
/// 获取队列长度
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqQueue"></param>
/// <returns></returns>
        public int SeqQueueLen<T>(SeqQueue<T> seqQueue)
        {
            return seqQueue.size;
        }
        #endregion
    }
    #endregion
}


算法系列15天速成 第九天 队列

标签：
队列
相思资源网 Design By www.200059.com
广告合作：本站广告合作请联系QQ：858582 申请时备注：广告合作（否则不回）
免责声明：本站文章均来自网站采集或用户投稿，网站不提供任何软件下载或自行开发的软件！ 如有用户或公司发现本站内容信息存在侵权行为，请邮件告知！ 858582#qq.com
相思资源网 Design By www.200059.com

评论“算法系列15天速成 第九天 队列”

暂无算法系列15天速成 第九天 队列的评论...
www.200059.com 相思资源网
139,976影音资源
144,792福利资源
21,817软件资源
631,128技术资源
一句话新闻
一口气升级7个大模型SaaS应用，百度智能云：突出一个“开箱即用” - 2024/11/5

这一波大模型产业落地浪潮里，不少企业其实处在 “干瞪眼“的状态。

一种情况是，很多大模型产品看得见却摸不着，在台上一个个遥遥领先——今天Sora技精四座，明天英伟达的机器人又赢得满堂彩，可是到了台下一问：啥时候能用上啊？答曰：遥遥无期。

另一种情况是，企业想用上大模型，却又难免瞻前顾后——既要考虑场景融合，又得兼顾安全性，还要考虑打通现有系统，再加上各种部署成本和繁琐的采购流程……最后只能拂袖：罢了，再等等吧。

稳了！魔兽国服回归的3条重磅消息！官宣时间再确认！

昨天有一位朋友在大神群里分享，自己亚服账号被封号之后居然弹出了国服的封号信息对话框。

这里面让他访问的是一个国服的战网网址，com.cn和后面的zh都非常明白地表明这就是国服战网。

而他在复制这个网址并且进行登录之后，确实是网易的网址，也就是我们熟悉的停服之后国服发布的暴雪游戏产品运营到期开放退款的说明。这是一件比较奇怪的事情，因为以前都没有出现这样的情况，现在突然提示跳转到国服战网的网址，是不是说明了简体中文客户端已经开始进行更新了呢？

友情链接

杰晶网络 DDR爱好者之家 桃源资源网 杰网资源 富贵资源网 南强小屋 铁雪资源网 幽灵资源网 万梅资源网 狼山资源网 白云岛资源网 昆仑资源网 相思资源网 明霞山资源网 内蒙古资源网 黑松山资源网 茶园资源网 饿虎岗资源网 大旗谷资源网 常春岛资源网 岱庙资源网 兴国资源网 快活林资源网 蝙蝠岛资源网 帝王谷资源网 白云城资源网 伏龙阁资源网 清风细雨楼 天枫庄资源网 圆月山庄资源网 无争山庄资源网 神水资源网 移花宫资源网 神剑山庄资源网 无为清净楼资源网 金钱帮资源网 丐帮资源网 华山资源网 极乐门资源网 小李飞刀资源网 凤求凰客栈 风云阁资源网 金狮镖局 鸳鸯亭资源网 千金楼资源网 更多链接
相思资源网 Design By www.200059.com