Home Tags Posts tagged with "队列"

队列

0 58

队列是非常重要的数据结构,在许多模型或者架构中都能看到它的身影,今天就要仔细解剖一下它吧~

 

一、带着问题去学习

我们知道,CPU 资源是有限的,任务的处理速度与线程个数并不是线性正相关。

相反,过多的线程反而会导致 CPU 频繁切换,处理性能下降。

所以,线程池的大小一般都是综合考虑要处理任务的特点和硬件环境,来事先设置的。当我们向固定大小的线程池中请求一个线程时,如果线程池中没有空闲资源了,这个时候线程池如何处理这个请求?是拒绝请求还是排队请求?各种处理策略又是怎么实现的呢?

二、怎么理解“队列”?

想象成排队买票,先来的先买,后来的人只能站末尾,不允许插队。

 

特性:

先进者先出,这就是典型的“队列”。

我们知道,栈只支持两个基本操作:入栈 push()和出栈 pop()。队列跟栈非常相似,支持的操作也很有限,

 

最基本的操作也是两个:

  • 入队 enqueue(),放一个数据到队列尾部;
  • 出队 dequeue(),从队列头部取一个元素。

队列,也是一种操作受限的线性表数据结构(只允许在队尾插入,队头删除)

应用场景:

循环队列,阻塞队列,并发队列等等

 

三、队列的两种实现方式(顺序队列(数组实现),链式队列(链表实现))

队列是抽象的数据结构,跟栈一样,其实现也有两种方式:数组实现和链表实现

顺序队列随着入队出队会产生的问题(队列未满却无法添加)

当不停的入队,出队操作,head和tail都会持续往后移动。当tail移动到最右边,即使数组中还有空闲空间,也无法继续往队列中添加数据

类似问题:数组中的删除操作会导致数组中的数据不连续,解决办法是数据搬移(即移动数组中的元素)

在队列中每次出队操作都相当于删除数组下标为0的数据,要搬移整个队列的数组,出队的时间复杂度就会从O(1)上升到O(n),怎么进行优化呢?

思路:减少数据搬移的次数(进一步思考,出队时不用搬移空间;如果没有空闲空间了,在入队时,集中触发一次数据的搬移操作即可)


搬移过程:

 

四、循环队列

在使用数组实现队列的时候,当tail == n时,会友数据搬移操作,这样入队操作性能就会受到影响,那么有无办法去避免数据搬移?

循环队列,顾名思义,它长得像一个环。原本数组是有头有尾的,是一条直线。现在我们把首尾相连,扳成了一个环。

图中这个队列的大小为 8,当前 head=4,tail=7。当有一个新的元素 a 入队时,我们放入下标为 7 的位置。但这个时候,我们并不把 tail 更新为 8,而是将其在环中后移一位,到下标为 0 的位置。当再有一个元素 b 入队时,我们将 b 放入下标为 0 的位置,然后 tail 加 1 更新为 1。所以,在 a,b 依次入队之后,循环队列中的元素就变成了下面的样子:

通过这样的方法,我们成功避免了数据搬移操作。看起来不难理解,但是循环队列的代码实现难度要比前面讲的非循环队列难多了。要想写出没有 bug 的循环队列的实现代码,我个人觉得,最关键的是,确定好队空和队满的判定条件。

 

循环队列的判空条件:队列为空的判断条件仍然是 head == tail。

循环队列的判满条件:队列为满的判断条件是  (tail + 1 )%n == head   –> ( 3 + 1)%8 = 4;

循环队列的指针移动:tail = (tail + 1)% n;

 

当队列满时,图中的 tail 指向的位置实际上是没有存储数据的。所以,循环队列会浪费一个数组的存储空间。(tail指向下一个插入的位置) 如果不浪费的话,无法区别是队列满了还是队列为空,即变为 head == tail

 

五、阻塞队列、并发队列

阻塞队列:在队列基础上增加了阻塞操作

并发队列:线程安全的队列

 

六、解答开篇

队列的知识就讲完了,我们现在回过来看下开篇的问题。线程池没有空闲线程时,新的任务请求线程资源时,线程池该如何处理?各种处理策略又是如何实现的呢?我们一般有两种处理策略。

第一种是非阻塞的处理方式,直接拒绝任务请求;

另一种是阻塞的处理方式,将请求排队,等到有空闲线程时,取出排队的请求继续处理。

那如何存储排队的请求呢?我们希望公平地处理每个排队的请求,先进者先服务,所以队列这种数据结构很适合来存储排队请求。我们前面说过,队列有基于链表和基于数组这两种实现方式。这两种实现方式对于排队请求又有什么区别呢?基于链表的实现方式,可以实现一个支持无限排队的无界队列(unbounded queue),但是可能会导致过多的请求排队等待,请求处理的响应时间过长。所以,针对响应时间比较敏感的系统,基于链表实现的无限排队的线程池是不合适的。而基于数组实现的有界队列(bounded queue),队列的大小有限,所以线程池中排队的请求超过队列大小时,接下来的请求就会被拒绝,这种方式对响应时间敏感的系统来说,就相对更加合理。不过,设置一个合理的队列大小,也是非常有讲究的。队列太大导致等待的请求太多,队列太小会导致无法充分利用系统资源、发挥最大性能。除了前面讲到队列应用在线程池请求排队的场景之外,队列可以应用在任何有限资源池中,用于排队请求,比如数据库连接池等。实际上,对于大部分资源有限的场景,当没有空闲资源时,基本上都可以通过“队列”这种数据结构来实现请求排队。

0 86

队列,也是一种线性表,它的特性是先进先出,插入在一端,删除在另一端。就像排队一样,队(push)要排在队尾(rear),每次出队(pop)的都是队首(front)的人

队列与栈一样,是一种线性存储结果,它具有如下特点:

  1. 队列中的数据元素遵循“先进先出”(First In First Out)的原则,简称FIFO结构。
  2. 在队尾(移动rear指针)添加元素,在队头(移动front指针)删除元素

1.2 队列相关概念

  1. 队头与队尾: 允许元素插入的一端称为队尾,允许元素删除的一端称为队头。
  2. 入队:队列的插入操作。(push)
  3. 出队:队列的删除操作。(pop)

依次入队:{1,2,3}

入队时,元素只能从队尾一端进入队列,即2只能跟在1的后面,3只能跟在2的后面

依次出队:先进先出

元素只能从队首出队列,出队列的顺序为:1、2、3,与入队时的顺序一致,这就是所谓的“先进先出”。

1.3 队列的种类

单向队列

单向队列只能在队尾添加数据,在队首移除数据,是最简单的队列。

双端队列(deque)

双端队列是一种具有队列和栈性质的抽象数据类型,它可以在队尾、队首添加和移除数据,

优先队列(Priority queue)

优先队列中的每个元素都有各自的优先级,优先级最高的元素最先得到服务;优先级相同的元素按照其在优先队列中的顺序得到服务。优先队列往往用堆来实现。

循环队列 (克服假溢出现象)

为充分利用向量空间,克服”假溢出“现象的方法是:将向量空间想象为一个首尾相接的圆环,并称这种向量为循环向量。存储在其中的队列称为循环队列(Circular Queue)。这种循环队列可以以单链表的方式来在实际编程应用中来实现。

消除假溢出就是当队尾指针rear和队头指针front到达存储空间最大值QueueSize时,让队尾指针自动转化为存储空间的最小值0.

但是循环队列带来了新问题—front==rear 的二义性

在循环队列中,空队特征是front = rear, 队满时也会有front = rear; 判断条件将出现二义性

front==rear 二义性解决办法(三种):

1. 加设标志位,让删除动作使其为1,插入动作使其为0, 则可识别当前front == rear;
2. 使用一个计数器记录队列中元素个数(即队列长度)
3. 人为浪费一个单元,令队满特征为 front = (rear +1)%N—空闲单元法

空闲单元法:

1.4 队列的实现(Javascript)

class Queue {
  constructor(...items) {
    this.queue = [];
    this.enqueue(...items);
  }

  enqueue(...items) {
    items.forEach(item => this.queue.push(item));
    return this.queue;
  }

  dequeue(count = 1) {
    this.queue.splice(0, count);
    return this.queue;
  }

  peek() {
    return this.queue[0];
  }

  size() {
    return this.queue.length;
  }

  isEmpty() {
    return this.queue.length === 0;
  }
}

1.5 队列的应用

广泛应用在各种 广度优先搜索(Breadth-First-Search)中。

1.6 队列的操作

队列通常提供的操作:

  1. 入队: 通常命名为push()
  2. 出队: 通常命名为pop()
  3. 求队列中元素个数size()
  4. 判断队列是否为空isEmpty()
  5. 获取队首元素但不删除peek()

1.4 队列的存储结构

队列与栈一样是一种线性结构,因此以常见的线性表如数组、链表作为底层的数据结构。
本文中,我们以数组、链表为底层数据结构构建队列。

2.基于数组的循环队列实现

以数组作为底层数据结构时,一般讲队列实现为循环队列(为了解决队列假溢出)。这是因为队列在顺序存储上的不足:每次从数组头部删除元素(出队)后,需要将头部以后的所有元素往前移动一个位置,这是一个时间复杂度为O(n)的操作:3 队列假溢出

原因:

出队时,把队首标志往后移动不就不用移动元素了,的确,但那样会造成数组空间的“流失”。

解决办法:

我们希望队列的插入与删除操作都是O(1)的时间复杂度,同时不会造成数组空间的浪费,我们应该使用循环队列。
所谓的循环队列,可以把数组看出一个首尾相连的圆环,删除元素时将队首标志往后移动,添加元素时若数组尾部已经没有空间,则考虑数组头部的空间是否空闲,如果是,则在数组头部进行插入。