0%

数据结构之队列

上一篇文章说了一种“功能受限”的顺序表——栈,现在再来说一个 “功能受限”的顺序表 —— 队列(queue)。

队列也是一个常用的数据结构,在大部分资源有限的情况下,当没有空闲资源的时候,基本上都是使用队列这种数据结构来实现请求排队的。

队列,顾名思义,就是排的一条队,比如在买票的时候排的一条队伍,先来的先买,后来的后买,不允许插队,也就是先进先出的方式,栈是后进先出的方式。

栈支持入栈(push)和出栈(pop)两种操作,队列也是类似的,支持入队(enqueue)和出队(dequeue)两种操作,入队就是在尾部追加一个数据,出队就是在头部取走一个数据。

队列作为一种非常基础的数据结构,应用是非常广泛的,特别是一些具有某些额外特性的队列,比如循环队列、阻塞队列、并发队列。它们在很多偏底层系统、框架、中间件的开发中,起着关键性的作用。


队列在实现上跟栈也是类似的,可以使用数组或链表来进行实现,使用数组实现的叫做顺序队列,使用链表实现的叫做链式队列。但是栈只需要一个栈顶指针top就可以了,队列则需要头部head指针和尾部tail指针两个来标识。

比如说a、b、c、d四个数据入队以后,head指针将指向下标为0的位置,tail指针指向下标为4的位置

当进行两次出队的操作后,head指针将指向下标为2的位置

那如果不断的往后走,一直到下标为7后,不能再继续增加了怎么办,那就可以使用数组实现时的数据移动的方式,将数据向前迁移,那如果每进行一次出栈就迁移一次,那不就相当于一直在删除下标为0的元素,然后将整个队列都拷贝一边,操作的时间复杂度就为O(n)了呀,其实完全可以用另一种思路,在每次出栈的时候不进行迁移数据的操作,而是在数据入栈的时候,发现没有位置了,再将所有的数据向前迁移,这样时间复杂度就变成了O(1),即队列未满时,直接入队,时间复杂度为O(1),当队列已满时,也就是tail=n时,时间复杂度变为了O(n),如果将最后一次的n次迁移,平均到前面的n-1次上,那它们的均摊时间复杂度就变为了O(1)。

上面说的是顺序队列,对于链式队列来说,就更加容易了,因为不会涉及到队满的情况了,只需要处理好指针的移动问题就可以了。

但是它还有一个比较严重的问题,因为它的长度是可以无限长的,所以当请求的任务特别多时,后面的任务将会等待相当长的时间,这对于对时间比较敏感的系统来说,是会出问题的。

顺序队列因为大小有限,如果请求的任务超过了队列长度,将会直接将后续的任务拒绝掉,这对于对时间比较敏感的系统来说,是比较合理的方式,但是如何设置队列的大小又是一个问题,队列太大导致等待的请求太多,队列太小会导致无法充分利用系统资源、发挥最大性能。


前面顺序队列的实现时,当tail=n时,会有大量数据迁移的操作,如果使用循环队列就可以完美的解决这个问题了。

循环队列,顾名思义,就是将队列的首尾相连,组成环状

就拿上图来说,这个循环队列n=8,当前head=4,tail=7,当我们再插入一个数据的时候,会插入到下标为7的位置,tail将会向后挪一个,到达了0的位置,再插入数据,依旧像上面说的一样执行,tail将指向了下标为1的地方。

通过这样的方法,就节省了很多数据迁移的操作,但是在代码实现上就会更加的复杂,其中最关键的地方还是确定好队空和队满的判定条件。

队列为空的条件仍然是head=tail,那什么情况下是队满呢?

在一般情况下,很明显的可以看出来,当tail+1=head的时候,即为队满

但是还有一个情况比较特殊,并不适用这个规则,就是当head=0,tail=7时,此时再插入一个数据的时候,观察图可以发现,此时tail将等于head,但是tail=head的时候,是我们所说的队列为空的时候,这也就是为什么循环队列会浪费一个数组空间的原因;这个情况明显已经属于队满的情况了,如果套用上面的公式,tail+1=8,head=0,并不满足我们前面所提到的常规情况。

那么如何才能将tail+1在最大的情况下等于0呢,这里可以引入取余的方法。当tail=7时,tail+1=8,将它与n=8取余,8%8=0,就可以满足这个要求了,通用的公式就变成了 (tail+1)%n=head ,那一般情况满不满足这个公式呢,因为在一般情况下,tail+1都是小于n的,只有在上面所说的特殊情况时tail+1=n,所以不管怎么取余都是tail+1本身,也就是等于head了,所以队满的条件为 (tail+1)%n=head

上面在解释的时候也说了循环队列会浪费一个数组空间的原因,那如果我们专门用一个记录队列大小的值size,当这个值与数组大小相等时,表示队列已满,当tail达到最底时,size不等于数组大小时,tail就指向数组第一个位置。当出队时,size–,入队时size++。

这种的记录方法跟之前实现栈时候的思路类似,但是这样依旧会新创建一个内存空间来存放size值,最后消耗的大小是一样的。


到这里基础的队列就说完了,但是这样基础的队列在实际的业务开发中都不大会直接用到,常用的是一些比较特殊的队列,比如阻塞队列和并发队列。

阻塞队列其实就是在正常的队列操作中加上了阻塞操作,当队列为空时,在对头取数据的时候,会被阻塞,因为队列中还没有任何可以取的数据,直到队列中有数据时,才会取出数据并返回;如果队列已经满了,那插入数据将会被阻塞,直到有空闲位置后,将数据插入才会返回。

通过阻塞队列,很轻松就可以实现“生产者 – 消费者模型”,它可以有效的协调生产与消费的速度,当生产过快的时候,队列就无法再加入了,生产者就会被阻塞,直到出现空余位置的时候才会继续生产。

那我们设想一个场景,如果消费者方面已经不需要这个东西了,那生产方还是在不断的往进放东西,这样就会造成极大的浪费,这样的情况让我想起了我们现在全面深化改革的一点——供给侧结构性改革,不再让供给方无限的供给了,要在可能快出现问题的时候,便让供给方减少供给,以便让资源得到更好的利用。

插了点题外话,我们继续说阻塞队列,为了让数据更加高效的处理,我们还可以协调供给者和消费者的的数量。

那并发队列又是什么,并发队列就是在多线程的情况下,由于有多个线程同时操作,可能会存在一些安全问题,为了实现线程安全的队列就是并发队列,与阻塞队列类似,并发队列就是在入队和出队上加锁,同一时刻仅允许一个存或取的操作,但是锁粒度大并发度就会比较低,这个也是一个需要协调的东西。

实际上,基于数组的循环队列,利用 CAS 原子操作 (Compare & Set,或是 Compare & Swap),可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛的原因。


参考文档

极客时间-数据结构与算法之美