队列(queue)
Varsion

队列这个概念非常好理解。

可以把它想象成排队买票,先来的先买,后来的人只能站末尾,不允许插队。先进者先出,这就是典型的“队列”。

队列跟栈非常相似,支持的操作也很有限,最基本的操作也是两个:入队 enqueue(),放一个数据到队列尾部;出队 dequeue(),从队列头部取一个元素。队列跟栈一样,也是一种操作受限的线性表数据结构。

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

Ruby的链式队列实现

1
2
3
4
5
6
7
8
# Node
class Node
attr_accessor :item, :next
def initialize(item)
@item = item # 用来保存信息
@next = nil # 用来指向下一个节点
end
end
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Queue
attr_reader :first, :length
def initialize # 初始化一个队列
@first = nil
@last = nil
@length = 0
end

def enqueue(item) # 向队列的末尾添加一个元素
node = Node.new(item) # 新建一个节点
if is_empty? # 当队列为空的时候,首节点和尾节点都设置为这个新加入的节点
@first = node
@last = @first
else
@last.next = node # 当队列不为空的时候,就将尾节点的下一个节点设置为新节点
@last = @last.next # 让后将队列的尾节点更新为新节点
end
@length += 1 # 新节点加入完成后,队列的长度增加1
end

def dequeue # 删除队列的第一个元素
return nil if @first == nil # 当队列为空的时候,什么也不做,直接返回空值
item = @first.item # 队列不为空的时候,先保存会被删掉的节点的值
@first = @first.next # 将首节点重置为之前的第二个节点。这样我们就访问不到原来的首节点了。因此它成了孤儿,就被删除了。
@length -= 1 # 删除后队列的长度减去1
@last = nil if is_empty? # 删除节点后队列为空的话,就将队列的最后一个节点也设置为空
return item # 返回之前保存的被删除的节点的值
end

def is_empty? # 返回队列是否为空(即队列中是否没有节点)
return @length == 0
end

end

阻塞队列和并发队列

阻塞队列其实就是在队列基础上增加了阻塞操作。简单来说,就是在队列为空的时候,从队头取数据会被阻塞。因为此时还没有数据可取,直到队列中有了数据才能返回

如果队列已经满了,那么插入数据的操作就会被阻塞,直到队列中有空闲位置后再插入数据,然后再返回。

阻塞队列的定义定义就是一个”生产者 - 消费者模型”

这种基于阻塞队列实现的”生产者 - 消费者模型”,可以有效地协调生产和消费的速度。当“生产者”生产数据的速度过快,“消费者”来不及消费时,存储数据的队列很快就会满了。这个时候,生产者就阻塞等待,直到“消费者”消费了数据,“生产者”才会被唤醒继续“生产”。

线程安全的队列我们叫作并发队列。

最简单直接的实现方式是直接在 enqueue()、dequeue() 方法上加锁,但是锁粒度大并发度会比较低,同一时刻仅允许一个存或者取操作。

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

线程池没有空闲线程时,新的任务请求线程资源时,线程池该如何处理?

第一种是非阻塞的处理方式,直接拒绝任务请求;另一种是阻塞的处理方式,将请求排队,等到有空闲线程时,取出排队的请求继续处理。

我们希望公平地处理每个排队的请求,先进者先服务,所以队列这种数据结构很适合来存储排队请求。我们前面说过,队列有基于链表和基于数组这两种实现方式。这两种实现方式对于排队请求又有什么区别呢?

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

而基于数组实现的有界队列,队列的大小有限,所以线程池中排队的请求超过队列大小时,接下来的请求就会被拒绝,这种方式对响应时间敏感的系统来说,就相对更加合理。

对于大部分资源有限的场景,当没有空闲资源时,基本上都可以通过“队列”这种数据结构来实现请求排队。


  • Post title:队列(queue)
  • Post author:Varsion
  • Create time:2020-08-03 21:59:56
  • Post link:https://blog.varsion.cn/post/26a3f7fd.html
  • Copyright Notice:All articles in this blog are licensed under BY-NC-SA unless stating additionally.
Comments