数据结构与算法(6)-队列

  1. 1. 理解队列
  2. 2. 基于链表的队列实现方法
  3. 3. 循环队列
  4. 4. 阻塞队列和并发队列
  5. 5. 对比基于数组和基于链表实现的队列

CPU资源有限,任务的处理速度和线程个数并不是线性正相关的。相反的,过多的线程会导致CPU频繁切换,处理性能下降。因此,线程池的大小一般都是综合考虑要处理任务的特点和硬件环境,来事先设置的。

当我们向固定大小的线程池中请求一个线程的时候,如果线程池中没有空闲资源,如何处理这个请求呢? —–> 队列

操作受限的线性表。

1. 理解队列

  • 基本操作
    • 入队 enqueue() 入栈 push()
    • 出队 dequeue() 出栈 pop()
  • 操作受限的线性表数据结构
  • 带有一些特性的队列
    • 循环队列
    • 阻塞队列
    • 并发队列
    • 顺序队列 - 数组实现
    • 链式队列 - 链式队列

在很多偏底层系统,框架,中间件的开发当中,起到关键性作用。比如高性能disruptor,Linux环形缓存,都用到了循环并发队列; Java Concurrent并发包利用ArrayBlockingQueue来实现公平锁。

// 用数组实现的队列
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;
  }
}

2. 基于链表的队列实现方法

  • 两个指针
    • head指针 - 指向第一个结点
    • tail指针 - 指向最后一个结点

3. 循环队列

用数组实现的队列,在tail = n的时候,会有数据搬移操作。这样入队性能就会受到影响。循环队列的可以解决这个问题。

  • 如何确认队空和队满
    • 队空 head == tail
    • 队满 (tail+1)%n = head
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;
  }
}

4. 阻塞队列和并发队列

  • 阻塞队列
    • 在队列基础上增加了阻塞操作
    • 队列为空的时候,从队头取数据会被阻塞
    • 如果队列已经满了,那么插入数据的操作会被阻塞,直到队列中有空闲位置后再插入数据,然后再返回
    • 生产者 消费者模型 相当于
    • 基于阻塞队列,我们可以通过协调生产者和消费者的个数来提高数据的处理效率
    • 我们可以通过配置多几个的消费者,来应对一个生产者
  • 并发队列
    • 实现方法
      • 在enquue()和dequeue()方法上加锁
      • 基于CAS原子操作

5. 对比基于数组和基于链表实现的队列

  • 基于链表的实现方式
    • 可以实现一个支持无限排队的无界队列
    • 可能会导致过多的请求排队等待
    • 请求处理的响应时间会长很多
    • 因此对于响应时间比较敏感的系统来说,基于链表实现的无限排队的线程池就不是很合适了
  • 基于数组实现的有界队列
    • 队列大小是有限的
    • 超过一定数量以后,请求就会被拒绝
    • 队列的大小设置就会是个trade off了

转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 stone2paul@gmail.com

文章标题:数据结构与算法(6)-队列

文章字数:981

本文作者:Leilei Chen

发布时间:2020-02-09, 09:45:37

最后更新:2020-02-09, 09:45:58

原始链接:https://www.llchen60.com/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95-6-%E9%98%9F%E5%88%97/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

目录
×

喜欢就点赞,疼爱就打赏