专栏首页苦逼的码农三分钟基础:什么是队列?

三分钟基础:什么是队列?

作者 | 小鹿

来源 | 小鹿动画学编程

写在前边

像线程池、异步队列、消息队列等有限的资源容器中,往往存储大量的任务事件,这些大量的任务事件需要进行有条理的进行任务分发以及各种情况处理,为了能够使得资源容器的正常运行,不得不使用一定的容器结构设计和策略,那么这些结构和策略如何实现的呢?

那小鹿不买官司了,就是用我们今天即将学到的数据结构“队列”。虽然我们初学者实际中接触的少,但是它的实际用途广着呢,学好这部分是非常关键的。

思维导图

1

什么是队列?

何为队列?顾名思义,排队就是一个很好的例子。如果我们餐厅刷卡买饭,学生依次排队,已购买完饭的在队头走了,刚来的同学就要排在队尾后边排队。而不能直接在排好队中插队,这样也坏了排队这种“先来先去”规矩。

2

队列的特点?

栈有出栈和入栈两种,队列也有入队和出队两种操作,只不过是栈是先来后走,队列则相反,先来先走。

正是因为队列这种特点,使得它在一些有限的资源容器中的到广泛的应用,比如线程池、资源池、消息队列等。

3

如何实现队列?

队列和栈一样,也有两种实现方式,一种是顺序队列,一种是链式队列。但是我们之前的文章中说过,无论是顺序还是链式,都是由数组和链表演化而来,只不过是操作上进行了改进。

1、顺序队列

对于上边的数组顺序队列,不知道大家有没有发现一个问题就是,如果我一直的出队、入队会出现下边这样一种情况。

此时队列再入队,但是队尾已满,但是我们看到的明明队头还有空间的,如果此时扩大容量不就相当于浪费空间吗?

那还有一个方法就是,每入队一个元素,整体数据就往前移动一个空间,你可能会说,这样操作起来是不是很费劲,而且效率不高,是的,这样的确效率不高。

如果我们稍微改进一下,如果队尾有空间,我们就让元素一直入队,直到队尾没有空间位置,然后进行整体进行一次搬移,这样优化了入队的效率。将这一次性进行大量搬移数据平均到每次上,平均时间复杂度还是 O(1)。

2、链式队列

链式队列是以链表组成的,它的优点就是可以无限的进行入队,不用动态扩容。

4

队列的种类?

4.1 循环队列

循环队列,顾名思义,将一般的队列进行头尾相接,形成一个圆,声明两个指针,一个带边队头,一个代表队尾,入队和出队的时候,直接操作对应的指针即可。

但是为什么会出现循环队列呢?是否还记得我们上边所述,普通的队列需要进行大量数据搬移,而循环队列则没有这个缺点。

但是循环队列有一个比较重要的点就是判空和判断是否已满。

如上图所示,判空的条件很简单,头指针等于尾指针的时候,此时循环队列为空。

循环队列满的时候,我们要发现其上边的规律得出队满的条件,(尾指针 + 1)% n = 头指针。此时的循环队列会浪费一个空间。

上边我们涉及到的队列是从结构上进行来区分的,下面我们就从实际开发功能上进行划分。其实就是对一些功能的需求对队列操作上设定了一定的要求。

4.2 阻塞队列

我们拿一个例子入手,如果你学习过Android开发,里边有个MessageQueue消息队列。如果没有接触过,也没关系,可以将其理解为放置消息的一个容器。

这个容器主要存放系统给它分发的任务消息,然后当有线程来分配任务的时候,此时该容器,也就是消息队列就会在队列中拿出任务然后分发给线程去执行。但是有这样两种情况需要进行设计。

第一种情况就是当任务消息队列没有任务的时候,此时线程来拿任务,该怎么办?

第二种情况就是,当没有空闲线程来取任务,此时任务消息队列已经满了,系统再分发新的任务时,又该如何处理呢?

那我相对于这两种情况,就用到我们的阻塞队列。当遇到第一种情况时,此时消息队列为空,在队头拿数据的时候会被阻塞,也就是被阻止了,因为队列中为空,只有等到队列中有新的数据时,线程才可以拿去新的任务。

当遇到第二种情况,如果队列已经满了,此时没有空余线程来取任务,此时队列也被阻塞了,当有空余线程来获取任务的时候,任务队列才可取数据。

其实上边的设计思路和我们所涉及到的设计模式中的 “发布-订阅者模式”相同。

生产者代表往消息队列中增加数据,消费者代表线程不断的拿去任务去执行,我们可以通过调节生产着和消费者的数量来调节队列汇总的任务数量,从而达到高效的系统运行。

4.3 并发队列

上边我们涉及到的阻塞队列会有很多的消费者(线程)去操作队列。我们举个具体点的例子,还是拿排队打饭的例子,如果一个窗口没有排序秩序,100 多个人都往窗口买饭,如果你作为卖饭的,想象一下会出现什么情况呢?

学生争来争去到底先给哪一个盛饭呢?一旦人一多,可能整个餐厅窗口挤爆,会出现打架的情况。

话说回来,在系统中也可能出现这种情况的,那我们怎么对付这种情况呢?此时的队列不再叫做阻塞队列,叫做并发队列。

我们只需要设置一个锁机制,当有一个消费者来取任务的时候,我们此时加一个锁,说明其他的消费者不能进行操作了,当这个消费者读取完任务时,在解锁,依次类推,这样保证了系统的正常运行。

总结

最后我们来总结一下队列的应用,像我们开篇所说,队列一般应用在有限的资源场景中,比如消息队列、异步队列、CPU 的线程执行队列等。对于这些应用场景,都是利用了队列先来先去的服务调度方式,从而能够准确的对资源进行把控。

队列在实际应用中也分为两种,一种是基于数组的顺序队列,另一种是基于链表的链式队列。它们两者各有优缺点,所谓的优缺点也是由数组和两边本身的优缺点演化而来。

数组大小固定,如果有过多的请求,就会导致长时间排队等候,请求响应时间过长。而链式队列虽然可以动态的添加任务,但是如果过于太长,在实际应用中也是不允许的。

对于如何在实际应用中设计一个合适的队列,需要根于已有的资源容量以及需求,还有系统的响应时间要求进行设计。如果队列太长,会导致等待请求过多,队列太小,就无法充分利用系统的资源。

本文分享自微信公众号 - 苦逼的码农(di201805),作者:小鹿

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-11-08

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 如何自己打造一个阻塞队列

    较长一段时间以来我都发现不少开发者对 jdk 中的 J.U.C(java.util.concurrent)也就是 Java 并发包的使用甚少,更别谈对它的理解了...

    帅地
  • TCP 半连接队列和全连接队列满了会发生什么?又该如何应对?

    很简单呀,因为我做了实验和看了 TCP 协议栈的内核源码,发现要增大这两个队列长度,不是简简单单增大某一个参数就可以的。

    帅地
  • 从本质上搞懂头痛的乱码问题!

    字符集 和 编码无疑是IT菜鸟甚至是各种大神的头痛问题。当遇到纷繁复杂的字符集,各种火星文和乱码时,问题的定位往往变得非常困难。本文将会从原理方面对字符集和编码...

    帅地
  • Hadoop FairScheduler

    本文档描述FairScheduler,一个允许YARN应用程序公平共享集群资源的调度插件。

    用户1217611
  • BlockingQueue源码分析

    * ArrayBlockingQueue :一个由数组结构组成的有界阻塞队列。 LinkedBlockingQueue :一个由链表结构组成的有界阻塞队列。 ...

    于霆霖
  • Java队列学习第一篇之列介绍

    队列大家都知道,但是在Java中队列分哪几种呢?清楚吗?都有哪些地方用到了队列呢?最常用的场景的就是消息中间件,比如各种MQ都是使用的队列来的。如果没有用过消息...

    凯哥Java
  • 算法与数据结构(二) 栈与队列的线性和链式表示(Swift版)

    数据结构中的栈与队列还是经常使用的,栈与队列其实就是线性表的一种应用。因为线性队列分为顺序存储和链式存储,所以栈可以分为链栈和顺序栈,队列也可分为顺序队列和链队...

    lizelu
  • 前端中的数据结构——队列篇

    队列是数据结构中的一种,它与实际生活中的排队相似:在一条队伍中,先来的人总是能够先得到服务,后来的人只能排在队伍末尾等候。队列也是一样,它符合先进先出 FIFO...

    企鹅号小编
  • 【数据结构(C语言版)系列三】 队列

    队列是一种先进先出的线性表,它只允许在表的一端进行插入,而在另一端删除元素。这和我们日常生活中的排队是一致的,最早进入队列的元素最早离开。在队列中,允许插入的一...

    闪电gogogo
  • AI_第一部分 数据结构与算法(8.队列)

    第四阶段我们进行深度学习(AI),本部分(第一部分)主要是对底层的数据结构与算法部分进行详尽的讲解,通过本部分的学习主要达到以下两方面的效果:

    还是牛6504957

扫码关注云+社区

领取腾讯云代金券