+
+

数据结构与算法之美:队列

先进者先出(FIFO),这就是典型的“队列”。同栈一样,队列支持的操作也很有限,入队(enqueue)和出队(dequeue)。

队列的应用非常广泛,特别是一些具有额外特性的队列,比如循环队列、阻塞队列、并发队列等。它们在很多偏底层的系统、框架、中间件的开发中起着关键性的作用。像在高性能队列Disrupter、Linux环形存储中,都用到了循环并发队列;Java concurrent并发包利用ArrayBlockingQueue来实现公平锁等。

顺序队列和链式队列

同理,用数组实现的队列叫做顺序队列,用链表实现的队列叫做链式队列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//顺序队列
class ArrayQueue{
constructor(){
this.items = [];
this.head = 0;//队头下标
this.tail = 0;//队尾下标,指向下一个空位置
}

enqueue(element){
this.items[this.tail++] = element;
return true;
}

dequeue(){
if (this.head===this.tail) return null;
return this.items[this.head++];
}
}

上面是JavaScript语言的实现,在C或者Java等语言中,声明items数组需要给定数组的容量,因此还需要考虑数据搬移。为了简化操作,在出队时可以不用搬移数据,只有在入队时集中触发一次数据的搬移操作。

基于链表实现的顺序队列,实现图解如图所示:

循环队列

在刚才用数组来实现队列的时候,每dequeue一个元素时,head就往后移一位,前面的空间就被浪费了,在tail触底而还有前面空间可用时,入队还需要耗时进行数据搬移操作,影响了入队的操作性能。如何避免这些问题呢?让我们来看看循环队列的解决思路。

队列每添加(enqueue)一个元素时,要判断队列是否已经被占满;每删除(dequeue)一个元素时,要判断队列是否为空。在非循环队列中,队满的判断条件是tail=n,队空的判断条件是head=tail。而对于循环队列来说,队空的条件同非循环一样,队满的条件却因为循环队列的循环特性不再适用了。那要如何判断循环队列的「队满」呢?
有这么一个规律:

1
(tail+1)%n=head //队满条件

阻塞队列和并发队列

阻塞队列其实就是在队列的基础上增加了阻塞操作——当队列为空时,从队头取数据会被阻塞,直到非空时才返回;当队满时,插入数据的操作被阻塞,直到有空位后再插入。

这个阻塞队列的定义其实和「生产-消费者模型」不谋而合:当供过于求时,生产者被阻塞等待消费者消费数据;当供不应求时,消费者被阻塞等待生产者产出数据。

不仅如此,还可以通过调整阻塞队列中生产者和消费者的个数,来提高数据的处理效率。

除了阻塞队列,还存在并发队列——在多线程的情况下,一个队列同时被多个线程操作,存在线程安全问题,并发队列可在enqueue()dequeue()上加锁,同一时刻仅允许一个存/取操作。实际上,基于数组的循环队列,利用 CAS 原子操作,可以实现非常高效的并发队列。

CAS (Compare and Swap) 比较并交换:判断一个内存上的数据是否为所判断的值,如果是则执行修改,否则不做修改并返回当前值。CAS是一种乐观锁,多线程执行过程中,多个线程去修改内存中的数据,有且只有一个能修改成功,但是失败的线程不会中断或者挂起。

参考链接:实现无锁的栈与队列(3)

满的线程池如何处理新的线程任务

一般有两种处理策略,一是非阻塞的处理方式,直接拒接任务请求;二是阻塞的处理方式,将请求搁置排队,等到有空闲线程时取出排队的请求继续处理。这其中的排队过程就是通过队列来实现的。

基于链表实现的链式队列,可以实现一个支持无限排队的无界队列,但是可能导致过多请求排队等待,从而延长处理请求的响应时间。所以,针对响应时间比较敏感的系统,基于链表实现的无限排队的线程池是不合适的。

基于数组实现的顺序队列,队列的容量有限,当队满时,新的请求将会以非阻塞的方式被直接拒接。这种方式对响应时间敏感的系统来说,就相对更加合理。不过,如何设置一个合理的队列大小也是非常讲究的。队列太大导致等待的请求太多,队列太小会导致无法充分利用系统资源,无法发挥最大性能。

除了应用在线程池请求排队外,队列还可以应用在任何有限资源池中,用于排队请求,比如数据库连接池等。实际上,对于大部分资源有限的场景,当没有空闲资源时,基本上都可以通过队列这种数据结构来实现请求排队。

课后思考

  1. 除了线程池这种池结构会用到队列排队请求,你还知道有哪些类似的池结构或者场景中会用到队列的排队请求呢?
    • 分布式应用中的消息队列 eg. kafka
    • 网卡的收发数据包操作
  2. 如何实现无锁并发队列?
    使用CAS实现无锁队列,在入队前获取tail位置,入队时比较tail是否发生变化,若无变化则允许入队,反之入队失败;出队则获取head位置。

本文作者: rhinoc

本文链接: https://www.rhinoc.top/cid216_7/

版权声明: 本博客所有文章除特别声明外,均采用BY-NC-SA 4.0国际许可协议,转载请注明。

打赏
Love U 3000
  • Through WeChat
  • Through Alipay
0%