ArrayDeque

双端队列Deque的一个实现

数组实现

数组实现,用下标head和tail表示头尾.

public class ArrayDeque<E> extends AbstractCollection<E>
                           implements Deque<E>, Cloneable, Serializable
{
    private transient E[] elements;

    private transient int head;

    private transient int tail;
}

默认大小16

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

保证容量的策略,始终保证容量大小为2的幂次方.

private void allocateElements(int numElements) {
        int initialCapacity = MIN_INITIAL_CAPACITY; //MIN_INITIAL_CAPACITY = 8
        // 能容纳numElements个元素的最小的2的幂次方
        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 off
                initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
        }
        elements = (E[]) new Object[initialCapacity];
    }

扩容策略

double扩容

private void doubleCapacity() {
        assert head == tail;
        int p = head;
        int n = elements.length;    // 当前容量大小
        int r = n - p;              // 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 = (E[])a;
        head = 0;
        tail = n;
    }

PriorityQueue

优先级队列的一个实现数组实现,默认大小11,带比较器.优先级队列不允许 null 元素.

public class PriorityQueue<E> extends AbstractQueue<E>
    implements java.io.Serializable {
    private transient Object[] queue;

    private final Comparator<? super E> comparator; //比较器

    public PriorityQueue() {
        this(DEFAULT_INITIAL_CAPACITY, null);   //DEFAULT_INITIAL_CAPACITY = 11
    }
}

实现原理

PriorityQueue使用的是二叉堆实现的,用数组实现很方便.这里的实现和<算法导论>里面讲的基本一致.这里以小顶堆为例子.这个实现是非线程安全的.

二叉堆保证孩子节点大于等于父亲节点.同时它又具有完全二叉树(除了底层,其他层是满的)的性质.如下:

    1
  /   \
 2     3
/ \   / \
   4   5  6  7
  / \ / \
 8  9 10 11

二叉堆是专门为取出最大或最小节点而设计点数据结构，这种数据结构在查找一般元素方面性能和一般数组是没有多大区别的。

二叉堆在取出最大或最最小值的性能表现是O(1),取出操作完成之后，二叉堆需要一次整形操作，以便得到下一个最值，这个操作复杂度O(logn)。

但是二叉堆也有一个缺点，就是二叉堆对存储在内存中的数据操作太过分散，这导致了二叉堆在cpu高速缓存的利用与内存击中率上面表现不是很好，这也是一个二叉堆理想操作时间所需要付出的代价。

这里有我的一个二叉堆的简单实现

xiaobaoqiu Blog

Think More, Code Less

Java Queue