LinkedBlockingQueue
LinkedBlockingDeque在结构上有别于之前讲解过的阻塞队列,它不是Queue而是Deque,中文翻译成双端队列,双端队列指可以从任意一端入队或者出队元素的队列,实现了在队列头和队列尾的高效插入和移除
LinkedBlockingDeque是链表实现的线程安全的无界的同时支持FIFO、LIFO的双端阻塞队列,可以回顾下之前的LinkedBlockingQueue阻塞队列特点,本质上是类似的,但是又有些不同:
Queue和Deque的关系有点类似于单链表和双向链表,LinkedBlockingQueue和LinkedBlockingDeque的内部结点实现就是单链表和双向链表的区别,具体可参考源码。
在第二点中可能有些人有些疑问,两个互斥锁和一个互斥锁的区别在哪里?我们可以考虑以下场景:
A线程先进行入队操作,B线程随后进行出队操作,如果是LinkedBlockingQueue,A线程入队过程还未结束(已获得锁还未释放),B线程出队操作不会被阻塞等待(锁不同),如果是LinkedBlockingDeque则B线程会被阻塞等待(同一把锁)A线程完成操作才继续执行
LinkedBlockingQueue一般的操作是获取一把锁就可以,但有些操作例如remove操作,则需要同时获取两把锁,之前的LinkedBlockingQueue讲解曾经说明过
LinkedBlockingQueue 由于是单链表结构,只能一端操作,读只能在头,写只能在尾,因此两把锁效率更高。LinkedBlockingDeque 由于是双链表结构,两端头尾都能读写,因此只能用一把锁保证原子性。 当然效率也就更低
ArrayBlockingQueue
LinkedBlockingQueue
问题,为什么ArrayBlockingQueue 不能用两把锁
因为取出后,ArrayBlockingQueue 的元素需要向前移动。
LinkedBlockingQueue内部由单链表实现,只能从head取元素,从tail添加元素。添加元素和获取元素都有独立的锁,也就是说LinkedBlockingQueue是读写分离的,读写操作可以并行执行。LinkedBlockingQueue采用可重入锁(ReentrantLock)来保证在并发情况下的线程安全。
LinkedBlockingQueue一共有三个构造器,分别是无参构造器、可以指定容量的构造器、可以穿入一个容器的构造器。如果在创建实例的时候调用的是无参构造器,LinkedBlockingQueue的默认容量是Integer.MAX_VALUE,这样做很可能会导致队列还没有满,但是内存却已经满了的情况(内存溢出)。
size()方法会遍历整个队列,时间复杂度为O(n),所以最好选用isEmtpy
1.判断元素是否为null,为null抛出异常
2.加锁(可中断锁)
3.判断队列长度是否到达容量,如果到达一直等待
4.如果没有队满,enqueue()在队尾加入元素
5.队列长度加1,此时如果队列还没有满,调用signal唤醒其他堵塞队列
1.加锁(依旧是ReentrantLock),注意这里的锁和写入是不同的两把锁
2.判断队列是否为空,如果为空就一直等待
3.通过dequeue方法取得数据
3.取走元素后队列是否为空,如果不为空唤醒其他等待中的队列
原理:在队尾插入一个元素, 如果队列没满,立即返回true; 如果队列满了,立即返回false。
原理:如果没有元素,直接返回null;如果有元素,出队
1、具体入队与出队的原理图 :
图中每一个节点前半部分表示封装的数据x,后边的表示指向的下一个引用。
1.1、初始化
初始化之后,初始化一个数据为null,且head和last节点都是这个节点。
1.2、入队两个元素过后
1.3、出队一个元素后
表面上看,只是将头节点的next指针指向了要删除的x1.next,事实上这样我觉的就完全可以,但是jdk实际上是将原来的head节点删除了,而上边看到的这个head节点,正是刚刚出队的x1节点,只是其值被置空了。
2、三种入队对比:
3、三种出队对比:
2024-11-24 广告