背景图

Java中Queue学习

在上一篇的博文中,我们分析了Deque的知识,其实感觉是反了,应该是先分析Queue,分析完之后再去分析Deque,不过这都没啥关系,单向的队列或许更容易学习。

Queue接口

还是先从Queue接口开始吧,这个接口继承Collection,Queue接口定义了几个方法。

方法名 功能 说明
add 增加一个元索 如果队列已满,则抛出一个IIIegaISlabEepeplian异常
remove 移除并返回队列头部的元素 如果队列为空,则抛出一个NoSuchElementException异常
element 返回队列头部的元素 如果队列为空,则抛出一个NoSuchElementException异常
offer 添加一个元素并返回true 如果队列已满,则返回false
poll 移除并返问队列头部的元素 如果队列为空,则返回null
peek 返回队列头部的元素 如果队列为空,则返回null

AbstractQueue

1
2
3
public abstract class AbstractQueue<E>
extends AbstractCollection<E>
implements Queue<E> {

继承了AbstractCollection,实现了Queue接口。主要是提供了Queue的基础实现。都是一些常规的方法,这里就不做更多的介绍了。

一些基础实现

我们知道Deque是继承于Queue的,所以只要实现Deque的类基本上都是Queue的实现。在上一篇的博文中我们提到了LinkedList、ArrayDeque和LinkedBlockingDeque都是Queue的实现了,这里就不多介绍了。

优先队列 PriorityQueue

实际上是一个堆(不指定Comparator时默认为最小堆)。队列既可以根据元素的自然顺序来排序,也可以根据 Comparator来设置排序规则。队列的头是按指定排序方式的最小元素。如果多个元素都是最小值,则头是其中一个元素。新建对象的时候可以指定一个初始容量,其容量会自动增加。

继承结构

继承自AbstractQueue,实现了序列化接口。

属性

1
2
3
4
5
6
private static final int DEFAULT_INITIAL_CAPACITY = 11;
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private transient Object[] queue;
private int size = 0;
private final Comparator<? super E> comparator;
private transient int modCount = 0;

感觉这里面的都是老朋友了,默认初始化容量是11个。基础的数据结构是数组,优先级通过比较器来进行实现。最大无限制,应该是留下来进行扩展使用的。

构造方法

就是进行数组的初始化(必须大于1)和比较器的传入(可为空)。比较值得一看的构造器应该是下面的两个:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
@SuppressWarnings("unchecked")
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);
}
}

private void initFromPriorityQueue(PriorityQueue<? extends E> c) {
if (c.getClass() == PriorityQueue.class) {
this.queue = c.toArray();
this.size = c.size();
} else {
initFromCollection(c);
}
}

private void initElementsFromCollection(Collection<? extends E> c) {
Object[] a = c.toArray();
// If c.toArray incorrectly doesn't return Object[], copy it.
if (a.getClass() != Object[].class)
a = Arrays.copyOf(a, a.length, Object[].class);
int len = a.length;
if (len == 1 || this.comparator != null)
for (int i = 0; i < len; i++)
if (a[i] == null)
throw new NullPointerException();
this.queue = a;
this.size = a.length;
}

private void initFromCollection(Collection<? extends E> c) {
initElementsFromCollection(c);
// 在整个树中建立堆不变量(如上所述),在调用之前不假设元素的顺序。
heapify();
}

主要是通过原来的集合中的比较器作为当前PriorityQueue的比较器而已,插入的方式就不说了,原来是数组,所以直接调用toArray方法进行赋值即可。如果原来不是有序的话,可能还要进行排序吧!可能比较器不一样,排序的规则也不一样,这个就是下面三个方法在处理的一些事情。这里注意的是,如果是Collection的话,需要进行排序。heapify()的目的是建立一个二叉树,其实就是堆结构。

扩展策略

1
2
3
4
5
6
7
8
9
10
11
private void grow(int minCapacity) {
int oldCapacity = queue.length;
// Double size if small; else grow by 50%
int newCapacity = oldCapacity + ((oldCapacity < 64) ?
(oldCapacity + 2) :
(oldCapacity >> 1));
// overflow-conscious code
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
queue = Arrays.copyOf(queue, newCapacity);
}

原来容量大小小于64时双倍扩展还要加上一个2;大于64,50%扩展.

插入

以offer方法为例吧!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public boolean offer(E e) {
if (e == null)
throw new NullPointerException();
modCount++;
int i = size;
// 这是队列满了才进行扩容吗?>=可能会发生同步问题,而导致大于问题的存在。
if (i >= queue.length)
// 最起码保证当前容量能加1
grow(i + 1);
size = i + 1;
if (i == 0)
// 如果没有元素的话,不用移位操作
queue[0] = e;
else
// 如果队列有元素.就要通过当前位置
siftUp(i, e);
return true;
}

神奇,居然是队列满了,才进行相应的扩容操作。接着分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
private void siftUp(int k, E x) {
// 是否使用comparator比较器
if (comparator != null)
siftUpUsingComparator(k, x);
else
siftUpComparable(k, x);
}

private void siftUpUsingComparator(int k, E x) {
while (k > 0) {
// 很像是在使用二分法
int parent = (k - 1) >>> 1;
// 取得parent处的元素
Object e = queue[parent];
if (comparator.compare(x, (E) e) >= 0)
break;
// 将e移出来,放到后面,原来是这样的。
queue[k] = e;
k = parent;
}
// 如果k<0,不是会有异常吗?,其实就是找到了合适的位置插入
queue[k] = x;
}

一开始没有看明白这里面在干啥,现在明白了,原来是使用类似二分法,将比插入元素大的值,不停地向后移,直到找到合适的位置插入。siftUpComparable(k, x);的实现是相似的。可是如果插入的X是最大的,最后的key会不会小于0,如果key小于0,最后那句执行不就出现异常了么?注意经过推演,初始k一定大于0,而且k永远是整数,而k右移一位也不会改变属性还是大于0,所以最终k只能为0跳出循环,因为k-1会先减到0。所以k最小值为0,也就是如果出现上述情况,会按照理想的状态放入到索引0处。

其实这个操作是在向二叉树里面插入元素而已。因为正常大家都是通过链表实现二叉树,这里是通过数组来实现二叉树,所以一时间没有看懂。这里也可以看出,这个是一个小根堆的结构。

获取

我们以poll为例吧!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public E poll() {
if (size == 0)
return null;
int s = --size;
modCount++;
E result = (E) queue[0];
// 取得最后一个元素
E x = (E) queue[s];
// 最后的元素清除
queue[s] = null;
// 如果是0的话,队列是空的啥都不做。
if (s != 0)
// 从最后一个元素开始,找到一个新的最小值。
siftDown(0, x);
return result;
}

这里看起来是只要返回最前面的那个元素就好了,的确每次插入都能保证,最小的值在前面,也好理解。 这样看来siftDown就是再将最小的值移到前面去。我们看一下这里面的实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
private void siftDown(int k, E x) {
if (comparator != null)
siftDownUsingComparator(k, x);
else
siftDownComparable(k, x);
}
private void siftDownUsingComparator(int k, E x) {
int half = size >>> 1;
while (k < half) {
int child = (k << 1) + 1;
Object c = queue[child];
int right = child + 1;
if (right < size &&
comparator.compare((E) c, (E) queue[right]) > 0)
c = queue[child = right];
if (comparator.compare(x, (E) c) <= 0)
break;
queue[k] = c;
k = child;
}
queue[k] = x;
}

这是堆的维护,关于堆的实现请看下面的引用。

遍历

看了一下内部的迭代器实现,并没有按照堆内顺序进行返回,而是按照数组的顺序进行返回,所以返回的数组并不是有序的,这点要注意。

关于堆

其实堆就是一个完全二叉树,分为小端堆和大端堆。与平衡二叉树相比:

  • 堆整体没有顺序,但是每条路径有顺序。
  • 堆维护成本比较低,每次调整,都要取最右边的那个元素过来进行重新调整。但是调整要比平衡二叉树要快很多。
  • 如果是用来排序的话,堆的成本还是挺高的。如果是动态排序,堆的维护成本却能大大降低。

引用和参考

java中queue的使用
大话数据结构十四:二叉树的顺序存储结构(数组实现)
堆排序HeapSort(Java)

0%