400-1100-266

9:00-24:00（工作日）
主页 > 知识库 > 算法系列15天速成 第九天 队列

算法系列15天速成 第九天 队列
热门标签：呼叫中心市场需求 服务器配置 铁路电话系统 检查注册表项 网站文章发布 银行业务 美图手机 智能手机

一：概念

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

二：存储结构

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

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


代码段如下：

复制代码 代码如下:

#region 队列的数据结构
    /// summary>
/// 队列的数据结构
/// /summary>
/// typeparam name="T">/typeparam>
    public class SeqQueueT>
    {
        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)。



代码段如下：

复制代码 代码如下:

#region 队列元素出队
        /// summary>
/// 队列元素出队
/// /summary>
/// typeparam name="T">/typeparam>
/// param name="seqQueue">/param>
/// returns>/returns>
        public T SeqQueueOutT>(SeqQueueT> 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 SeqQueueT> SeqQueueInT>(SeqQueueT> 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 SeqQueuePeekT>(SeqQueueT> seqQueue)
        {
            if (SeqQueueIsEmpty(seqQueue))
                throw new Exception("队列已空，不能进行出队操作");

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

5: 获取队长

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

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

代码段如下：

复制代码 代码如下:

/// summary>
/// 获取队列长度
/// /summary>
/// typeparam name="T">/typeparam>
/// param name="seqQueue">/param>
/// returns>/returns>
        public int SeqQueueLenT>(SeqQueueT> 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)
        {
            SeqQueueStudent> seqQueue = new SeqQueueStudent>();

            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(SeqQueueStudent> 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 SeqQueueT>
    {
        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 SeqQueueT> SeqQueueInitT>(SeqQueueT> 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 SeqQueueIsEmptyT>(SeqQueueT> 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 SeqQueueIsFullT>(SeqQueueT> 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 SeqQueueT> SeqQueueInT>(SeqQueueT> 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 SeqQueueOutT>(SeqQueueT> 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 SeqQueuePeekT>(SeqQueueT> 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 SeqQueueLenT>(SeqQueueT> seqQueue)
        {
            return seqQueue.tail - seqQueue.head;
        }
    }
    #endregion
}

三：顺序队列的缺陷

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

已满，但是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)
        {
            SeqQueueStudent> seqQueue = new SeqQueueStudent>();

            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 SeqQueueT>
    {
        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 SeqQueueT> SeqQueueInitT>(SeqQueueT> 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 SeqQueueIsEmptyT>(SeqQueueT> 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 SeqQueueIsFullT>(SeqQueueT> 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 SeqQueueT> SeqQueueInT>(SeqQueueT> 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 SeqQueueOutT>(SeqQueueT> 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 SeqQueuePeekT>(SeqQueueT> 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 SeqQueueLenT>(SeqQueueT> seqQueue)
        {
            return seqQueue.size;
        }
        #endregion
    }
    #endregion
}



您可能感兴趣的文章:
  • 算法系列15天速成 第十四天 图【上】
  • 算法系列15天速成——第十三天 树操作【下】
  • 算法系列15天速成 第十二天 树操作【中】
  • 算法系列15天速成 第十一天 树操作（上）
  • 算法系列15天速成 第十天 栈
  • 算法系列15天速成 第八天 线性表【下】
  • 算法系列15天速成 第七天 线性表【上】
  • 算法系列15天速成 第六天 五大经典查找【下】
  • 算法系列15天速成 第五天 五大经典查找【中】
  • 算法系列15天速成 第四天 五大经典查找【上】
  • 算法系列15天速成 第三天 七大经典排序【下】
  • 算法系列15天速成 第二天 七大经典排序【中】
  • 算法系列15天速成 第一天 七大经典排序【上】
  • 算法系列15天速成——第十五天 图【下】（大结局）

标签：长治 沧州 新疆 沈阳 乐山 上海 红河 河南

巨人网络通讯声明：本文标题《算法系列15天速成 第九天 队列》，本文关键词  ；如发现本文内容存在版权问题，烦请提供相关信息告之我们，我们将及时沟通与处理。本站内容系统采集于网络，涉及言论、版权与本站无关。
  • 相关文章
  • 推荐文章

    上一篇：算法系列15天速成 第七天 线性表【上】

    下一篇：算法系列15天速成 第八天 线性表【下】

     
    微信咨询办理
    在线QQ客服
    ( 客服小王 )
    ( 客服小李 )
    ( 客服小刘 )
    ( 客服小张 )
    关于我们 | 荣誉资质 | 呼叫中心 | 代理加盟 | 客户案例 | 服务支持 | 产品介绍 | 行业资讯

    Copyright © 1999-2012 诚信 合法 规范的巨人网络 www.1330.cn 始建于2005年

    全国网站建设网站开发咨询热线：400-1100-266   0514-86177077

    江苏扬州巨人网络科技有限公司   总部地址：江苏省扬州信息产业基地11号楼4层

    《增值电信业务经营许可证》苏B2-20120278    苏ICP备15040257号 网站地图
    全国咨询热线
    400-1100-266
    在线客服( QQ：340506921 )
    版权所有：巨人网络(扬州)科技有限公司——拥有网站建设十年经验，具备独立网站开发能力，能够提供完善的网站设计及相关的网站制作服务！     全国统一服务热线：400-1100-266
    收缩
    • 微信客服
    • 微信二维码

    • 电话咨询

    • 400-1100-266