AI 助理
备案控制台
开发者社区 人工智能 文章 正文

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

2016-04-13 1408
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介：

 

可能大家都知道，线性表的变种非常非常多，比如今天讲的“队列”，灰常有意思啊。

 

一：概念

          队列是一个”先进先出“的线性表，牛X的名字就是“First in First Out(FIFO)”，

      生活中有很多这样的场景，比如读书的时候去食堂打饭时的”排队“。当然我们拒绝插队。

 

二：存储结构

         前几天也说过，线性表有两种”存储结构“，① 顺序存储,②链式存储。当然“队列”也脱离

     不了这两种服务，这里我就分享一下“顺序存储”。

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

 

代码段如下：

#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)。

   

代码段如下：

#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)。

代码段如下：

/// <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
}

 

 

 

三：顺序队列的缺陷

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

已满，但是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
}

 

文章标签：
存储
算法
关键词：
算法队列
一线码农
目录
相关文章
肾透侧视攻城狮
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总（10）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子；这都学不会；能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛？！！！
肾透侧视攻城狮
21 1
java冯坚持
|
2月前
|
存储 算法 定位技术
数据结构与算法学习二、稀疏数组与队列，数组模拟队列，模拟环形队列
这篇文章主要介绍了稀疏数组和队列的概念、应用实例以及如何使用数组模拟队列和环形队列的实现方法。
java冯坚持
25 0
数据结构与算法学习二、稀疏数组与队列，数组模拟队列，模拟环形队列
倔强的石头_
|
6月前
|
算法 C语言
【数据结构与算法 经典例题】使用栈实现队列（图文详解）
【数据结构与算法 经典例题】使用栈实现队列（图文详解）
倔强的石头_
92 0
反季雪
|
6月前
|
存储 算法
【数据结构和算法】--队列的特殊结构-循环队列
【数据结构和算法】--队列的特殊结构-循环队列
反季雪
35 0
肥猪肥猪-17824
|
3月前
|
存储 算法 前端开发
深入理解操作系统：进程调度与优先级队列算法
【9月更文挑战第25天】在操作系统的复杂世界中，进程调度是维持系统稳定运行的核心机制之一。本文将深入探讨进程调度的基本概念，分析不同的进程调度算法，并着重介绍优先级队列算法的原理和实现。通过简洁明了的语言，我们将一起探索如何优化进程调度，提高操作系统的效率和响应速度。无论你是计算机科学的初学者还是希望深化理解的专业人士，这篇文章都将为你提供有价值的见解。
肥猪肥猪-17824
109 8
服务端技术栈
|
4月前
|
缓存 算法 Java
刷算法，你应该知道的队列经典应用
文章介绍了队列的基本特性和经典应用，包括如何用队列实现栈、使用优先级队列解决Top K问题，并通过LeetCode题目示例展示了队列在算法实现中的应用。
服务端技术栈
50 1
刷算法，你应该知道的队列经典应用
国中之林
|
4月前
|
算法
【数据结构与算法】优先级队列
【数据结构与算法】优先级队列
国中之林
19 0
国中之林
|
4月前
|
存储 算法
【数据结构与算法】队列(顺序存储)
【数据结构与算法】队列(顺序存储)
国中之林
34 0
倔强的石头_
|
6月前
|
算法 C语言
【数据结构与算法 经典例题】使用队列实现栈（图文详解）
【数据结构与算法 经典例题】使用队列实现栈（图文详解）
倔强的石头_
95 1
24k纯甄
|
6月前
|
算法
【C/数据结构和算法】：栈和队列
【C/数据结构和算法】：栈和队列
24k纯甄
51 1

热门文章

最新文章

  • 1
    openssl中算法的组织方式
  • 2
    九连环的递归算法（C和C++）
  • 3
    判断一个数字是否为素数的基于C语言的算法
  • 4
    【字符串处理算法】删除特定的字符的算法设计及C代码实现
  • 5
    双层优化入门(3)—基于智能优化算法的求解方法(附matlab代码)
  • 6
    平滑过渡的战争迷雾(一) 原理：Warcraft3地形拼接算法
  • 7
    算法精解:最小二乘法C实现
  • 8
    OpenCV 1 图像分割--分水岭算法代码
  • 9
    希尔排序(shellsort)算法实现
  • 10
    缓存、缓存算法(转)
  • 1
    算法人生（1）：从“强化学习”看如何“战胜拖延”
    111
  • 2
    理解并应用机器学习算法：决策树
    136
  • 3
    【机器学习】在使用K-means聚类算法时，如何选择K的值？
    396
  • 4
    【机器学习】为什么K-means算法使用欧式距离度量？
    381
  • 5
    【机器学习】描述K-means算法的步骤
    149
  • 6
    【机器学习】K-means和KNN算法有什么区别？
    622
  • 7
    C语言易混淆、简单算法、结构体题目练习、常见关键字总结-2
    49
  • 8
    C语言易混淆、简单算法、结构体题目练习、常见关键字总结-1
    53
  • 9
    图搜索算法详解
    128
  • 10
    R语言实现蒙特卡洛模拟算法
    301

    • 相关课程

    更多
  • 智能运维赛（复赛）：利用数据和算法，快速定位系统异常并进行根因分析
  • 智能创作赛（复赛）：相册应用中的视频故事生成算法介绍
  • 智能创作赛（初赛）：相册应用中的故事生成算法介绍
  • 相册服务中的故事生成算法介绍
  • Go语言核心编程 - 数据结构和算法
  • 神经网络概览及算法详解

    • 相关电子书

    更多
  • 数据+算法定义新世界
  • 袋鼠云基于实时计算的反黄牛算法
  • Alink：基于Apache Flink的算法平台

    • 相关实验场景

    更多
  • 使用Swing算法实现商品推荐
  • RSA密码算法设计与实现
  • 欧拉图的构造性证明与算法实现
  • 推荐系统入门之使用ALS算法实现打分预测
    • 下一篇
    阿里云无影云电脑免费试用，最长可试用3个月