java队列deque,集合之队列[Queue, Deque],双端队列[ArrayDeque, LinkedList],优先级队列[PriorityQueue]...

数据结构中的队列了解以下，"先进先出"是队列的最大的特点，也就是只能在头部访问一个元素，在尾部添加一个元素。还有一种叫做双端队列。可以有效地在头部和尾部同时添加或删除元 素。 不支持在队列中间添加元素。

在 JDK6 中引人了 Deque 接口， 并由 ArrayDeque 和 LinkedList 类实现。这两个类都提供了双端队列， 而且在必要时可以增加队列的长度。在并发包下还提供了有限队列和有限双端队列。

队列接口Queue

首先看看在JDK中，队列接口中都定义了哪些方法：

public interface Queue extends Collection {

// 继承自Collection接口的方法，

// 在容量允许的情况下将元素放入队列返回true，空间不够时抛出异常

boolean add(E e);

// 在容量允许的情况下插入元素，在容量限制时，优于add方法，空间不够导致添加失败返回false，

boolean offer(E e);

// 返回并且删除队列头的元素，队列为空抛出异常

E remove();

// 返回并且删除队列头的元素，队列为空返回null

E poll();

返回但不删除队列头的元素，队列为空抛出异常

E element();

返回但不删除队列头的元素，队列为空返回null

E peek();

}

双端队列接口Deque

public interface Deque extends Queue {

void addFirst(E e);

void addLast(E e);

boolean offerFirst(E e);

boolean offerLast(E e);

E removeFirst();

E removeLast();

E pollFirst();

E pollLast();

E getFirst();

E getLast();

E peekFirst();

E peekLast();

void push(E e);

E pop();

}

是不是很简单，方法都是见名知意，而且还是成双成对的出现，需要注意的系列区别就是为空时访问元素是抛出异常还是返回null。

还有一些方法继承自Queue接口和Collection接口：

数组实现的双端队列ArrayDeque

仍然先看ArrayDeque的继承层次：

先看看ArrayDeque中定义的属性和构造函数：

public class ArrayDeque extends AbstractCollection

implements Deque, Cloneable, Serializable {

transient Object[] elements;

transient int head;

transient int tail;

/**

* The minimum capacity that we'll use for a newly created deque.

* Must be a power of 2.

* 保证队列中最小的容量，必须2的n次幂

*/

private static final int MIN_INITIAL_CAPACITY = 8;

// 默认构造16容量的数组构建队列

public ArrayDeque() {

elements = new Object[16];

}

// 构建指定容量的队列

public ArrayDeque(int numElements) {

allocateElements(numElements);

}

// 根据别的集合构建队列

public ArrayDeque(Collection extends E> c) {

allocateElements(c.size());

addAll(c);

}

}

从属性中我们可以看出，ArrayDeque是基于循环数组实现的双端队列，默认构造的容量是16，最小也要保证8个容量，当我们使用指定数量的容量时，需要进行计算才能得到。那么是怎么计算的呢，需要遵循什么原则：

// 根据别的集合构建队列

public ArrayDeque(Collection extends E> c) {

allocateElements(c.size());

addAll(c);

}

// numElements 指定的容量大小

public ArrayDeque(int numElements) {

allocateElements(numElements);

}

// 根据用户传入的计算允许的容量，并创建数组

private void allocateElements(int numElements) {

elements = new Object[calculateSize(numElements)];

}

// 为了计算得到比numElements大的最小2的n次幂

private static int calculateSize(int numElements) {

int initialCapacity = MIN_INITIAL_CAPACITY; // MIN_INITIAL_CAPACITY = 8

// Find the best power of two to hold elements.

// Tests "<=" because arrays aren't kept full.

if (numElements >= initialCapacity) {

initialCapacity = numElements;

// 系列的移位、或操作，只是为了得到大于numElements的最小2次幂

initialCapacity |= (initialCapacity >>> 1);

initialCapacity |= (initialCapacity >>> 2);

initialCapacity |= (initialCapacity >>> 4);

initialCapacity |= (initialCapacity >>> 8);

initialCapacity |= (initialCapacity >>> 16);

initialCapacity++;

// 如果进过移为操作后，得到的结果第32位为1，1代表负数，那么就需要回退一位。

if (initialCapacity < 0) // Too many elements, must back off

initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements

}

return initialCapacity;

}

还有一点就是添加元素的过程中，如果超出了数组的限制，那么怎么做的，其实和ArrayList一样，动态的增加数组的容量：

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倍，然后拷贝数据到新数组中

知道了ArrayDeque是基于循环数组的实现，那么对于接口方法的实现就不列举了，具体可以查看API文档。

链表实现的双端队列 LinkedList

优先队列

优先队列按照任意的顺序将元素插入到队列中，但是出队的时候却按照从小到大的顺序取出，它使用的是一种高效的数据结构——堆(Heap),是一种自我调整的二叉树。元素之间需要比较，所以插入的元素需要实现Comparable接口，当然，也可以在构造器中提供一个Compator。

它的继承层次比较简单，如下：

需要注意的是PriorityQueue并没有实现Cloneable接口，也就是说它不能被克隆

PriorityQueue每次访问的总是队列中最小的元素。

public class PriorityQueue extends AbstractQueue

implements java.io.Serializable {

private static final int DEFAULT_INITIAL_CAPACITY = 11;

transient Object[] queue;

private final Comparator super E> comparator;

}

基于数组实现，默认容量为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);

}

private static int hugeCapacity(int minCapacity) {

if (minCapacity < 0) // overflow

throw new OutOfMemoryError();

return (minCapacity > MAX_ARRAY_SIZE) ?

Integer.MAX_VALUE :

MAX_ARRAY_SIZE;

}

至此，JDK中常用的集合类就完毕了。