队列 (Equeue)

问题向导

• 问题1：线程池没有空闲线程时，新的任务请求 线程资源时，线程池该如何处理？各种处理策略又是如何实现的呢？
• 思路：
  • 处理策略一：非阻塞的处理方式，直接拒绝任务请求
  • 处理策略二：阻塞的处理方式，将请求排队，等到有空闲线程时，取出排队的请求继续处理。
• 实现：
  • 对于处理策略二,引入队列来解决存储排队请求。
  • 对于此队列的实现，有两种方式，基于链表实现和基于数组实现，这两种方式实现思路如下：
    • 链式队列（基于链表实现）：实现一个支持无限排队的无界队列，但随着请求数的增加，请求排队和处理的响应时间也会随之增加，这对响应时间比较敏感的系统，基于链表实现的无限排队的线程池是不合适的。
    • 有界队列（基于数组实现）：队列的大小有限，故线程池中排队的请求超过队列大小时，后续请求将会被拒绝，此种方式对相应时间比较敏感的系统来说，就比较合适，但存在另外一个问题，如何设置队列的大小，就很考验开发者的经验和能力（队列太大导致请求太多，队列太小会导致无法充分利用系统资源，发挥最大性能）。

队列概述

• 概念：

  • 先进者先出的数据结构，就是队列
    • 类比排队买东西
  • 是一种抽象的数据结构
  • 是一种操作受限的线性表数据结构（栈也是如此）

• 特点：

  • 先进先出
  • 支持在队尾插入元素，在队头删除元素

• 实现

  • 数组实现->顺序队列

  • 链表实现->链式队列

队列的操作

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

队列的种类

• 顺序队列
• 链式队列
• 循环队列
• 阻塞队列
• 并发队列

队列—顺序队列

• 使用数组来实现
• 实现思路：
  • 引入两个指针：
    • head指针：指向队头
    • tail指针：指向队尾
  • 入队操作时：head指针指向下标为0的位置，tail顺次往后移动，当tail移动到最后，表明数组不能继续添加数据了
  • 出队操作时：tail指针指向队列的尾部，head指针顺次往后移动，当head移动tail的位置，表明数组已没有元素。
• 注意：当tail指针移动到最后，即使数组里还有空闲空间，队列也无法插入数据，这是一个问题
  • 解决方法：对数据进行搬移，在每次进行出队操作时，将出队的元素标记为删除，当队列没有空间时，再集中出发数据搬移操作，

队列—链式队列

• 使用链表实现
• 实现思路：
  • 引入两个指针：
    • head指针：指向链表的第一个结点
    • tail指针：指向链表的最后一个节点
  • 入队操作时：
    • tail->next= new_node, tail = tail->next；
  • 出队操作时：
    • head = head->next

队列—循环队列

• 主要是解决顺序队列数据搬移的问题，而是实现的一种队列

• 循环队列：把数组的收尾相连，折成一个环

• 实现思路：

  • 队列的大小为 8，当前 head=4，tail=7。当有一个新的元素 a 入队 时，我们放入下标为 7 的位置。但这个时候，我们并不把 tail 更新为 8，而是将其在环中后移一位，到下标为 0 的位置。当再有一个元素 b 入队时，我们将 b 放入下标为 0 的位置，然后 tail 加 1 更新为 1

• 注意点：需要确定好队空和队满的判定条件。

  • 对空判定： head == tail
  • 队满判定：(tail+1)%n=head。
    • 队满时，tail 指向的位置实际上是没有存储数据的。故循环队列 会浪费一个数组的存储空间。

队列—阻塞队列

• 在队列的基础上增加了阻塞操作，

• 若在队列为空时，从队头取数据会被阻塞，若在队列已满时，从队尾插入数据会被阻塞，直到队列中有空闲位置在插入数据，然后再返回。

• 实际应用：

  • 生产者-消费者模型

队列—并发队列

• 线程安全的队列就是并发队列
• 基于数组的循环队列，利用CAS原子操作，可以实现高效的并发队列。