直播预告-鸿蒙创想开发实例详解：从需求到上线的全流程解决方案

[TOC]

数据结构与算法笔记-数据结构-队列

队列(queue)

关键词

• 队列先进先出

• 队列和栈一样都是,操作受限的线性表数据结构

• 队列可以分为: 根据基于数组的顺序队列和基于链表的链式队列

  • 队列可延伸出另一种队列: 循环队列, 即把数组的首尾相连形成一个循环度列

• 队列又可以分为: 阻塞队列和并发队列

  • 阻塞队列: 队列为空时消费者被阻塞,队列满员时生产者阻塞
  • 并发队列: 又叫线程安全的队列,可以通过锁(低效)和循环队列的CAS原子操作(高效)来实现;

队列和栈的区别

队列和栈的区别

• 队列先进先出
• 队列和栈一样都是,操作受限的线性表数据结构
• 栈只支持两个基础操作,入栈(push)和出栈(pop),队列与之类似,支持的操作也非常有限,只有两个.入列(enqueue)和出列(dequeue)
• 入列: 推入一个数据到队尾,出列: 从队列头部取出一个数据.
• 队列也根据底层实现的不同分为顺序队列和链式队列,顺序队列就是以数组实现,链式就是以链表实现

基于数组的队列

数组队列需要两个指针:

1. head指针指向头部
2. tail指针指向队尾

代码分析,基于数组实现的顺序队列:

// 用数组实现的队列
public class ArrayQueue {
  // 数组：items，数组大小：n
  private String[] items;
  private int n = 0;
  // head表示队头下标，tail表示队尾下标
  private int head = 0;
  private int tail = 0;

  // 申请一个大小为capacity的数组
  public ArrayQueue(int capacity) {
    items = new String[capacity];
    n = capacity;
  }

  // 入队
  public boolean enqueue(String item) {
    // 如果tail == n 表示队列已经满了
    if (tail == n) return false;
    items[tail] = item;
    ++tail;
    return true;
  }

  // 出队
  public String dequeue() {
    // 如果head == tail 表示队列为空
    if (head == tail) return null;
    // 为了让其他语言的同学看的更加明确，把--操作放到单独一行来写了
    String ret = items[head];
    ++head;
    return ret;
  }
}

上面的代码操作步骤如下图:

1. 当a,b,c,d一次入列后
2. 此时队列的tail指针指向下标4
3. 队列的head指针指向下标0

调用两次出队操作之后,队列指针如下图:

1. head指针指向下标为2
2. tail指针依然指向下标为4
3. 随着不停的入列出列,head和tail指针会主键向后移动
4. 当tail指向最后一个下标时,及时数组还有空间,也无法再向队列中添加数据了,因为代码19行if (tail == n) return false;
5. 在之前的数组中也遇到这个问题,即数组的删除操作会导致数据小标不连续,当时用的是数据搬移,这里的队列也可以这样做.
   1. 方案1每次出列都相当于删除数组下标为0的数据,我们只要搬移整个队列中的数据即可.但此时出列的时间复杂度从O(1)变成O(n)
   2. 方案2,在入列时如果没有空间,此时再集中触发一次数据搬运操作.就是说出列函数保持不变,只需要稍加改造一下入列函数即可.

代码分析,改造后的入列方法:

   // 入队操作，将item放入队尾
  public boolean enqueue(String item) {
    // tail == n表示队列末尾没有空间了
    if (tail == n) {
      // tail ==n && head==0，表示整个队列都占满了
      if (head == 0) return false;
      // 数据搬移
      for (int i = head; i < tail; ++i) {
        items[i-head] = items[i];
      }
      // 搬移完之后重新更新head和tail
      tail -= head;
      head = 0;
    }
    
    items[tail] = item;
    ++tail;
    return true;
  }

改造后的流程如下图:

当队列tail指针移动到数组的最后一个下标,此时若有新的数据要入列,就把head到tail之间的数据全部搬运到0至tail-head的位置.

因为:

1. head<tail
2. head之前是没有数据的, 所以将数据搬运到head下标之前是没有问题的
   1. 比如,数组长度为10, 此时的head为5,tail为10.
   2. 那么搬运的情况应该是, 将head到tail之间的数据全部搬运到下标从0开始至10-5的位置
3. 此时出列的时间复杂度还是O(1),如果的最佳时间复杂度依然为O(1),最差时间复杂度为O(n)

基于链表的队列

同样需要两个指针,head和tail.分别指向链表的第一个节点和最后一个节点

如下图:

链表实现的队列如上图:

1. 入列时: tail->next = new_node, tail = tail->next; 即,将尾节点的指针next指向一个新的节点new_node,然后移动tail指针到new_node
2. 出列时: head = head->next;

循环队列

再说上面用数组实现队列时,当tail==n时会触发数据搬运操作,导致入列的性能受到影响.

想要避免入列时的数据搬运操作,我们可以使用循环队列.

循环队列,就是一个队列环.

本身数组是有头有尾的一条直线,我们把数组的首尾相连,就形成了一个环,如下图:

上图队列的大小为8,当前head=4,tail=7

1. 元素a入列,将其放在下标为7的位置,但此时是并不会把tail搬运到下标为8的位置.
2. 而是将其在环中后移一位到下标为0的位置
3. 下一个元素b入列,将b放入下标为0的位置,然后将tail下标+1,将其从下标0的位置更新为1

所以循环队列中的元素如下图:

循环队列可以避免数据搬运操作,但是实现相较于非循环队列来说难度巨大.

要写好最关键的地方是: 确定好队列为空和队列满员的判断条件

• 基于数组的非循环队列中判断满员的条件是tail==n,队列为空的条件是head==tail

• 基于数组的循环队列为空的条件依然是head==tail,队列满员的条件则较为复杂,如下图所示:

  • tail=3, head=4,n=8 总结的规律就是(3+1)%8=4
  • 当队列满员时,公式为: (tail+1)%n=head
  • 当队列满员时,图中的tail指向的位置实际上是没有存储数据的,所以循环队列会浪费一个数组的存储空间

循环队列的代码案例:

public class CircularQueue {
  // 数组：items，数组大小：n
  private String[] items;
  private int n = 0;
  // head表示队头下标，tail表示队尾下标
  private int head = 0;
  private int tail = 0;

  // 申请一个大小为capacity的数组
  public CircularQueue(int capacity) {
    items = new String[capacity];
    n = capacity;
  }

  // 入队
  public boolean enqueue(String item) {
    // 队列满了
    if ((tail + 1) % n == head) return false;
    items[tail] = item;
    tail = (tail + 1) % n;
    return true;
  }

  // 出队
  public String dequeue() {
    // 如果head == tail 表示队列为空
    if (head == tail) return null;
    String ret = items[head];
    head = (head + 1) % n;
    return ret;
  }
}

阻塞队列和并发队列

阻塞队列就是在队列的基础上增加了阻塞操作,即:

1. 队列为空时,从队列头部取数据(出栈)时会被阻塞,直到有数据时才会返回
2. 队列满员时,插入数据(入栈)时会被阻塞,直到有空间时才能插入数据.
3. 使用阻塞队列, 可以很随意的实现一个生产者和消费者的模型

基于阻塞队列实现的生产者和消费者模型,可以协调生产和消费的速度.

当生产者速度过快,消费者来不及消费,存储数据的队列很快就会满员(通常情况下队列都支持动态扩容)

此时生产者就会被阻塞等待,直到消费者消费了数据,生产者才能继续生产

而且,基于阻塞队列,还可以协调生产者和消费者的个数来提高处理效率,

为队列多配备几个消费者提高消费能力,以应对生产者:

在多线程情况下会有多个线程同时操作队列,此时就会出现线程安全的问题.

线程安全的队列,又叫并发队列, 最简单的方法是在入列(enqueue)和出列(dequeue)的方法上加锁,

但是锁的颗粒太大并发度会比较低,同一时刻仅允许一个存或取.

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

案例

CPU的资源很有限,,任务的处理速度与线程个数并非是线性正相关的.

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

线程池的大小一般都是要总和考虑,根据处理任务的特点和硬件环境来事先设置.

假设我们向一个固定大小的线程池中请求一个线程,此时线程池中没有空闲资源了,线程池就可以拒绝我们或者将请求进行排队操作.

当线程池没有空闲线程时,新的任务请求线程资源有两种操作

1. 非阻塞式, 直接拒绝任务请求
2. 阻塞式,将请求排队,等到有空闲线程时取出队列的请求继续处理

阻塞式这种,用队列的先进先出原则来做是最合适的,但是队列有基于链表和基于数组两种

1. 基于链表的队列,可以是一个无限排队的无界队列(unbounded queue),但会导致过多的请求排队,请求处理的响应时间过长.
2. 基于数组的队列的有界队列(bounded queue), 队列大小有限, 当线程池中排队的请求超多队列大小时,接下来的请求会被拒绝.

除了度列应用在线程池请求排队之外,队列可也应用在任何资源有限的资源池中,用于排队,比如数据库连接池等等.

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