Java Queue接口的那些实现类

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线程退出,其他三个线程还在阻塞,可以通过调整线程数量,打印不同的信息来观察。

阅读(28)
评论(0)
updated@2020-11-10
评论区
目录