ArrayDeque
- ArrayDeque 维护一个数组,一个head索引和一个tail索引
- head和tail索引提高了内存使用率。
- 数组弄人初始长度为16
private void grow(int needed) {
// overflow-conscious code
final int oldCapacity = elements.length;
int newCapacity;
// Double capacity if small; else grow by 50%
// 现有容量小于64时,增量为double + 2, 否则增量为 50%
int jump = (oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1);
if (jump < needed
|| (newCapacity = (oldCapacity + jump)) - MAX_ARRAY_SIZE > 0)
newCapacity = newCapacity(needed, jump); // 增量不足或者超容时,调用newCapacity(need, jump) 重新计算容量
final Object[] es = elements = Arrays.copyOf(elements, newCapacity);
// Exceptionally, here tail == head needs to be disambiguated
if (tail < head || (tail == head && es[head] != null)) {
// wrap around; slide first leg forward to end of array
// 尾在头前或(头尾相连并且元素不为空),把头尾分离
int newSpace = newCapacity - oldCapacity;
System.arraycopy(es, head,
es, head + newSpace,
oldCapacity - head);
for (int i = head, to = (head += newSpace); i < to; i++)
es[i] = null;
}
}
private int newCapacity(int needed, int jump) {
final int oldCapacity = elements.length, minCapacity;
if ((minCapacity = oldCapacity + needed) - MAX_ARRAY_SIZE > 0) {
if (minCapacity < 0) // 超过Integer.MAX_VALUE
throw new IllegalStateException("Sorry, deque too big");
return Integer.MAX_VALUE;
}
if (needed > jump)
return minCapacity;
return (oldCapacity + jump - MAX_ARRAY_SIZE < 0)
? oldCapacity + jump
: MAX_ARRAY_SIZE;
}
LinkedList 实现Queue接口
双向链表实现的FIFO队列,没什么特殊的
Stackc (没有实现Queue接口)
- 继承Vector实现的栈结构,LIFO
- 没有实现Queue接口,需要使用LIFO Queue的时候可以使用Stack来实现Queue接口。
- 线程安全。
PriorityQueue
- 一个排序Queue,二叉堆实现
- 需要提供一个Comparator或者插入的元素实现Comparable接口来提供排序依据,Comparator接口优先
- 使用最小堆,poll()和remove()取出的元素永远是Comparator定义最小的
- 数组默认初始长度为11
- 扩容策略与ArrayDeque大同小异,容量小于64时double+2,否则扩容50%
- 不允许存储null值
ArrayBlockingQueue
- 有界阻塞队列,循环数组实现,容量不可变, FIFO
- ReentrantLock 和 Condition 实现阻塞
- 不存储null元素
- 默认不公平,线程随机竞争,可通过构造器初始化时设置为公平,这样做会带来额外的性能消耗
public ArrayBlockingQueue(int capacity, boolean fair) {
if (capacity <= 0)
throw new IllegalArgumentException();
this.items = new Object[capacity];
lock = new ReentrantLock(fair);
notEmpty = lock.newCondition();
notFull = lock.newCondition();
}
LinkedBlockingQueue
- 可选有界阻塞队列,链表实现,默认最大长度为Integer.MAX_VALUE(我觉得是受限于size()方法只能返回int)
- FIFO队列
- 持有两个ReentrantLock,读写分离
PriorityBlockingQueue
PriorityQueue的阻塞版
DelayQueue
一个带有延迟功能的无界阻塞队列,继承自PriorityQueue, 插入的元素需要实现Delayd接口,不太懂Delayd接口,有空了解了更新
SynchronousQueue
- 一个奇怪的队列,插入和移除操作必须同时进行,也就是说,单方面的put或者take不会发生,因为这个队列里根本没有容量的概念。
- 实际上阻塞的是一系列执行put和take操作的线程
- 被阻塞的线程是单方面的,要么全是put操作,要么全是take操作
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.SynchronousQueue;
public class Test {
public static void main(String[] args) {
BlockingQueue<Integer> queue = new SynchronousQueue<>();
for (int i = 0; i < 5; i++) {
final int count = i;
new Thread(() -> {
// System.out.println("offer " + count);
try {
queue.put(count);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
// System.out.println("Offer " + count + "执行完毕");
}).start();
}
for (int i = 0; i < 8; i++) {
final int count = i;
new Thread(() -> {
// System.out.println("remove " + count);
try {
System.out.println("remove " + count + ", 实际结果: " + queue.take());
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}).start();
}
}
}
这段测试代码,使用了5个线程去执行put操作,8个线程执行take操作,最后只有5个take线程退出,其他三个线程还在阻塞,可以通过调整线程数量,打印不同的信息来观察。