队列Queue-08

举报
kwan的解忧杂货铺 发表于 2024/08/05 23:04:56 2024/08/05
【摘要】 1.ArrayDeque 类特点:由数组组成的双端队列。没有容量限制,根据需要扩容。不是线程安全的。禁止插入 null 元素。当用作栈时,比栈速度快,当用作队列时,速度比 LinkList 快。大部分方法的算法时间复杂度为 O(1)。remove、removeFirstOccurrence、removeLastOccurrence、contains、remove 和批量操作的算法时间复杂度...

1.ArrayDeque 类

特点:

  • 由数组组成的双端队列。
  • 没有容量限制,根据需要扩容。
  • 不是线程安全的。
  • 禁止插入 null 元素。
  • 当用作栈时,比栈速度快,当用作队列时,速度比 LinkList 快。
  • 大部分方法的算法时间复杂度为 O(1)。
  • remove、removeFirstOccurrence、removeLastOccurrence、contains、remove 和批量操作的算法时间复杂度 O(n)

使用:

ArrayDeque arrayDeque = new ArrayDeque();
for (int i = 0; i < 50; i++) {
    arrayDeque.add(buildingBlock); // add方法等价于addLast方法
}

2.LinkedTransferQueue 类

LinkedTransferQueue原理:

LinkedTransferQueue = 阻塞队列+链表结构+TransferQueue

之前我们讲“使命必达 TransferQueue 接口时已经介绍过了 TransferQueue 接口 ,所以 LinkedTransferQueue 接口跟它相似,只是加入了阻塞插入和移除的功能,以及结构是链表结构。

之前的 TransferQueue 也讲到了 3 个案例来说明 TransferQueue 的原理,大家可以回看 TransferQueue。

LinkedTransferQueue接口比其他阻塞队列多了5个方法:

  • transfer(E e)
  • tryTransfer(E e)
  • tryTransfer(E e, long timeout, TimeUnit unit)
  • getWaitingConsumerCount()
  • hasWaitingConsumer()

LinkedTransferQueue实现了哪些接口:

  • LinkedBlockingDeque 继承了 BlockingQeque 类,可作为阻塞队列使用
  • LinkedBlockingDeque 继承了 AbstractQueue 抽象类,具有队列的功能

3.SynchronousQueue 类

SynchronousQueue原理:

  • 我称 SynchronousQueue 为”传球好手“。想象一下这个场景:小明抱着一个篮球想传给小花,如果小花没有将球拿走,则小明是不能再拿其他球的。
  • SynchronousQueue 负责把生产者产生的数据传递给消费者线程。
  • SynchronousQueue 本身不存储数据,调用了 put 方法后,队列里面也是空的。
  • 每一个 put 操作必须等待一个 take 操作完成,否则不能添加元素。
  • 适合传递性场景。
  • 性能高于 ArrayBlockingQueue 和 LinkedBlockingQueue。

SynchronousQueue应用场景:

  • 吞吐量通常要高于 LinkedBlockingQueue。创建线程池时,参数 runnableTaskQueue(任务队列),用于保存等待执行的任务的阻塞队列可以选择 SynchronousQueue。静态工厂方法 Executors.newCachedThreadPool()使用了这个队列

SynchronousQueue和LinkedTransferQueue的区别:

  • SynchronousQueue 不存储元素,而 LinkedTransferQueue 存储元素。
  • SynchronousQueue 队列里面没有元素,而 LinkedTransferQueue 可以有多个存储在队列等待传输。
  • LinkedTransferQueue 还支持若传输不了,则丢到队列里面去。
  • LinkedTransferQueue 还支持若超过一定时间传输不了,则丢到队列里面去。

4.DelayQueue 类

image-20230723112117252

DelayQueue原理:

  • DelayQueue = Delayed + BlockingQueue。队列中的元素必须实现 Delayed 接口。
  • 在创建元素时,可以指定多久可以从队列中获取到当前元素。只有在延时期满才能从队列中获取到当前元素。
public class DelayQueue<E extends Delayed> extends AbstractQueue<E>
    implements BlockingQueue<E> {

源码解析:

  • 添加元素时,指定延时多久可以从队列中获取元素
public boolean offer(E e, long timeout, TimeUnit unit) {
    return offer(e);
}
  • 获取元素的方法 poll 需要等待延时时间过了才能获取到元素
if (first == null || first.getDelay(NANOSECONDS) > 0)
    return null;
else
    return q.poll();

应用场景:

  • 缓存系统的设计:可以用 DelayQueue 保存缓存元素的有效期。然后用一个线程循环的查询 DelayQueue 队列,一旦能从 DelayQueue 中获取元素时,表示缓存有效期到了。
  • 定时任务调度:使用 DelayQueue 队列保存当天将会执行的任务和执行时间,一旦从 DelayQueue 中获取到任务就开始执行。比如 Java 中的 TimerQueue 就是使用 DelayQueue 实现的。

DelayQueue实现了哪些接口:

  • DelayQueue 实现了 BlockingQueue 接口,可作为阻塞队列使用
【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。