Java集合框架中Queue接口有哪些实现？
作者：徐梦旗，发布于：2023年10月24日 20:37，字数：1.1k，预计阅读：5分钟
1. Queue接口详解
1.1. Queue接口有哪些实现？
2. ArrayDeque详解
2.1. ArrayDeque是如何设计的？
- 继承关系：
ArrayDeque继承了AbstractCollection，实现了Deque接口。 - 底层数据结构：
ArrayDeque使用了动态数组，当容量不足时会进行扩容。 - 存储元素：
ArrayDeque不允许存储null元素。 - 线程安全：
ArrayDeque是线程不安全的，采用fast-fail机制。
2.2. ArrayDeque是如何添加新元素的？
ArrayDeque用head记录头节点在数组中的下标，用tail记录尾节点的下一个节点在数组中的下标。
- 当调用
addFirst方法时，head减一同数组长度减一做且位运算（数组长度被限制为2的倍数，相当于取模运算）作为新的head的值，并设置新的元素。 - 当调用
addLast方法时，在tail下标设置新的元素，并tail加一同数组长度减一做且位运算作为新的tail的值。 - 当
head和tail相等时，意味着数组容量已满，需要进行扩容。
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
elements[head = (head - 1) & (elements.length - 1)] = e;
if (head == tail)
doubleCapacity();
}
public void addLast(E e) {
if (e == null)
throw new NullPointerException();
elements[tail] = e;
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();
}2.3. ArrayDeque是如何删除元素的？
- 当调用
pollFirst方法时，移除head下标处的元素，并拿head加一同数组长度减一做且位运算（数组长度被限制为2的倍数，相当于取模运算）作为新的head的值。 - 当调用
pollLast方法时，移除tail减一同数组长度减一做且位运算下标处的元素，并将该下标作为新的tail的值。
public E pollFirst() {
int h = head;
@SuppressWarnings("unchecked")
E result = (E) elements[h];
// Element is null if deque empty
if (result == null)
return null;
elements[h] = null; // Must null out slot
head = (h + 1) & (elements.length - 1);
return result;
}
public E pollLast() {
int t = (tail - 1) & (elements.length - 1);
@SuppressWarnings("unchecked")
E result = (E) elements[t];
if (result == null)
return null;
elements[t] = null;
tail = t;
return result;
}2.4. ArrayDeque是如何扩容的？
当head和tail相同时，也就是原数组容量已满时，ArrayDeque会进行扩容。ArrayDeque会将数组大小扩容为原数组大小的两倍，并将head节点及右侧的节点复制到新数组的左侧，将剩余的节点复制到新数组的右侧，最后将head设置为0，tail设置为原数组的大小。
private void doubleCapacity() {
assert head == tail;
int p = head;
int n = elements.length;
int r = n - p; // number of elements to the right of p
int newCapacity = n << 1;
if (newCapacity < 0)
throw new IllegalStateException("Sorry, deque too big");
Object[] a = new Object[newCapacity];
System.arraycopy(elements, p, a, 0, r);
System.arraycopy(elements, 0, a, r, p);
elements = a;
head = 0;
tail = n;
}2.5. ArrayDeque为了提升性能做了哪些设计？
- 使用动态数组维护队列，不存在节点的移动
- 限制数组长度为2的倍数，以便使用位运算代替取模运算；
- 扩容时只需要两次复制。
3. PriorityQueue详解
- 继承关系：
PriorityQueue继承了AbstractQueue。 - 底层数据结构：
PriorityQueue使用了基于数组实现的小顶堆，支持自然排序和比较器排序。 - 存储元素：
PriorityQueue不允许存储null元素。 - 线程安全：
PriorityQueue是线程不安全的，采用fast-fail机制。
3.1. PriorityQueue是如何维持优先级的？
当有新的元素入队时，会判断是否存在自定义比较器，如果存在则使用比较器，如果不存在则使用自然排序。元素的优先级取决于排序结果，排序越小的优先级越高，越先出队。
private void siftUp(int k, E x) {
if (comparator != null)
// 比较器排序
siftUpUsingComparator(k, x);
else
// 自然排序
siftUpComparable(k, x);
}
private
void siftUpComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>) x;
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = queue[parent];
if (key.compareTo((E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = key;
}
private void siftUpUsingComparator(int k, E x) {
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = queue[parent];
if (comparator.compare(x, (E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = x;
}4. 参考文档
目录
