Java 集合 (16) -- PriorityQueue 类 ConcurrentLinkedQueue 类 ArrayDeque 类_综合

文章目录

- 1. PriorityQueue 类
- - 1. 简介
  - 2. 继承体系
  - 3. 字段
  - 4. 构造器
  - 5. 常用方法
- 2. ConcurrentLinkedQueue 类
- - 1. 简介
  - 2. 继承体系
  - 3. 字段
  - 4. 内部类
  - 5. 构造器
  - 6. 常用方法
  - 7. ConcurrentLinkedQueue 与 LinkedBlockingQueue
- 3. ArrayDeque 类
- - 1. 简介
  - 2. 继承体系
  - 3. 字段
  - 4. 构造器
  - 5. 常见方法

1. PriorityQueue 类

1. 简介

public class PriorityQueue<E> extends AbstractQueue<E>implements java.io.Serializable {
    }

PriorityQueue，即优先级队列，是 0 个或多个元素的集合，集合中的每个元素都有一个权重值，每次出队都弹出优先级最大或最小的元素；其底层数据结构是一个小顶堆，是非线程安全的，不是有序的，只有堆顶存储着最小的元素，通过堆的插入操作实现入队，通过堆的删除操作实现出队。

2. 继承体系

在这里插入图片描述

3. 字段

// 默认容量
private static final int DEFAULT_INITIAL_CAPACITY = 11;// 存储元素的地方,存储在数组中
transient Object[] queue; // non-private to simplify nested class access// 元素个数
private int size = 0;// 比较器,在优先级队列中，也有两种方式比较元素，一种是元素的自然顺序，一种是通过比较器来比较；
private final Comparator<? super E> comparator;// 修改次数
transient int modCount = 0; // non-private to simplify nested class access

4. 构造器

public PriorityQueue() {
      this(DEFAULT_INITIAL_CAPACITY, null);
}

public PriorityQueue(int initialCapacity) {
      this(initialCapacity, null);
}

public PriorityQueue(Comparator<? super E> comparator) {
      this(DEFAULT_INITIAL_CAPACITY, comparator);
}

public PriorityQueue(int initialCapacity,Comparator<? super E> comparator) {
      // Note: This restriction of at least one is not actually needed,// but continues for 1.5 compatibilityif (initialCapacity < 1)throw new IllegalArgumentException();this.queue = new Object[initialCapacity];this.comparator = comparator;
}

public PriorityQueue(Collection<? extends E> c) {
      if (c instanceof SortedSet<?>) {
      SortedSet<? extends E> ss = (SortedSet<? extends E>) c;this.comparator = (Comparator<? super E>) ss.comparator();initElementsFromCollection(ss);}else if (c instanceof PriorityQueue<?>) {
      PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;this.comparator = (Comparator<? super E>) pq.comparator();initFromPriorityQueue(pq);}else {
      this.comparator = null;initFromCollection(c);}
}

public PriorityQueue(PriorityQueue<? extends E> c) {
      this.comparator = (Comparator<? super E>) c.comparator();initFromPriorityQueue(c);
}

public PriorityQueue(SortedSet<? extends E> c) {
      this.comparator = (Comparator<? super E>) c.comparator();initElementsFromCollection(c);
}

5. 常用方法

public boolean add(E e)：入队，其底层调用了 offer()，e 为 null 则抛空指针异常，添加元素到队尾后会进行小顶堆的整理
public boolean offer(E e)：入队，e 为 null 则抛空指针异常，添加元素到队尾后会进行小顶堆的整理
public E remove()：出队，其底层调用了 poll()，只是没有元素的时候会抛出异常
public E poll()：出队，没有元素的时候不会抛出异常，而是返回 null
public E element()：取队首元素，其底层调用了 peek()，只是没取到元素时会抛出异常。
public E peek()：取队首元素,没有元素的时候不会抛出异常，而是返回 null

2. ConcurrentLinkedQueue 类

1. 简介

public class ConcurrentLinkedQueue<E> extends AbstractQueue<E>implements Queue<E>, java.io.Serializable {
    }

ConcurrentLinkedQueue 只实现了 Queue 接口，并没有实现 BlockingQueue 接口，所以它不是阻塞队列，也不能用于线程池中，但是它是线程安全的，可用于多线程环境中。

它使用 CAS + 自旋来更新头尾节点以控制出队入队操作。

2. 继承体系

在这里插入图片描述

3. 字段

// 链表头节点
private transient volatile Node<E> head;// 链表尾节点
private transient volatile Node<E> tail;

4. 内部类

//典型的单链表结构
private static class Node<E> {
    volatile E item;volatile Node<E> next;
}

5. 构造器

public ConcurrentLinkedQueue() {
      // 初始化头尾节点head = tail = new Node<E>(null);
}

public ConcurrentLinkedQueue(Collection<? extends E> c) {
      Node<E> h = null, t = null;// 遍历c，并把它元素全部添加到单链表中for (E e : c) {
      checkNotNull(e);Node<E> newNode = new Node<E>(e);if (h == null)h = t = newNode;else {
      t.lazySetNext(newNode);t = newNode;}}if (h == null)h = t = new Node<E>(null);head = h;tail = t;
}

两个构造器都是用一个无界的单链表实现并发队列

6. 常用方法

public boolean add(E e)：添加到队尾，其底层调用了 offer()，e 为 null 则抛空指针异常，但因为是无界队列，所以不存在队列满无法添加的异常情况。如果成功了，就返回true，如果不成功则重新获取尾部，再重试。
public boolean offer(E e)：添加到队尾，e 为 null 则抛空指针异常，但因为是无界队列，所以不存在队列满无法添加的异常情况。如果成功了，就返回true，如果不成功则重新获取尾部，再重试。
public E remove()：移除队首元素并返回，底层调用了 poll()，若没有相应元素则抛出异常。如果成功了，就成功出队；如果失败或者头节点变化了，就重新寻找头节点，并重试。
public E poll()：移除队首元素并返回，没有元素则返回 null。如果成功了，就成功出队；如果失败或者头节点变化了，就重新寻找头节点，并重试。

7. ConcurrentLinkedQueue 与 LinkedBlockingQueue

两者都是线程安全的队列；
两者都可以实现取元素时队列为空直接返回null，后者的poll()方法可以实现此功能；
前者全程无锁，后者全部都是使用重入锁控制的；
前者效率较高，后者效率较低；
前者无法实现如果队列为空等待元素到来的操作；
前者是非阻塞队列，后者是阻塞队列；
前者无法用在线程池中，后者可以。

3. ArrayDeque 类

1. 简介

public class ArrayDeque<E> extends AbstractCollection<E>implements Deque<E>, Cloneable, Serializable {
    }

ArrayDeque 是一种以数组方式实现的双端队列，它是非线程安全的；它的出队入队是通过头尾指针循环利用数组来实现的，容量不足时会自动扩容，每次扩容容量会增加一倍，可以直接作为栈来使用。

2. 继承体系

在这里插入图片描述

3. 字段

// 存储元素的数组
transient Object[] elements; // non-private to simplify nested class access// 队列头位置
transient int head;// 队列尾位置
transient int tail;// 最小初始容量
private static final int MIN_INITIAL_CAPACITY = 8;

4. 构造器

默认构造方法，默认初始容量为16

public ArrayDeque() {
      elements = new Object[16];
}

指定元素个数初始化

public ArrayDeque(int numElements) {
      allocateElements(numElements);
}

将集合c中的元素初始化到数组中

public ArrayDeque(Collection<? extends E> c) {
      allocateElements(c.size());addAll(c);
}

// 初始化数组
private void allocateElements(int numElements) {
    elements = new Object[calculateSize(numElements)];
}// 计算容量，这段代码的逻辑是算出大于numElements的最接近的2的n次方且不小于8
// 比如，3算出来是8，9算出来是16，33算出来是64
private static int calculateSize(int numElements) {
    int initialCapacity = MIN_INITIAL_CAPACITY;// Find the best power of two to hold elements.// Tests "<=" because arrays aren't kept full.if (numElements >= initialCapacity) {
    initialCapacity = numElements;initialCapacity |= (initialCapacity >>>  1);initialCapacity |= (initialCapacity >>>  2);initialCapacity |= (initialCapacity >>>  4);initialCapacity |= (initialCapacity >>>  8);initialCapacity |= (initialCapacity >>> 16);initialCapacity++;if (initialCapacity < 0)   // Too many elements, must back offinitialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements}return initialCapacity;
}

5. 常见方法

public void addFirst(E e)：从队列头入队，若 e 为 null ，则抛出异常
public void addLast(E e)：从队列尾入队，若 e 为 null ，则抛出异常
public E pollFirst()：从队列头出队，若无则返回 null
public E pollLast()：从队列头出队，若无则返回 null