文章目录
- 队列Queue
- 优先队列PriorityQueue
- 双端队列Deque
队列Queue
在Java的标准库中，队列接口Queue定义了以下几个方法：
- int size()：获取队列长度；
- boolean add(E)/boolean offer(E)：添加元素到队尾；
- E remove()/E poll()：获取队首元素并从队列中删除；
- E element()/E peek()：获取队首元素但并不从队列中删除。
注意到添加、删除和获取队列元素总是有两个方法，这是因为在添加或获取元素失败时，这两个方法的行为是不同的。我们用一个表格总结如下：
队列的实现类：LinkedList
优先队列PriorityQueue
PriorityQueue和Queue的区别在于，它的出队顺序与元素的优先级有关，对PriorityQueue调用remove()或poll()方法，返回的总是优先级最高的元素。
要使用PriorityQueue，我们就必须给每个元素定义“优先级”。
要实现放入优先队列元素的优先级，方法为：
- 放入PriorityQueue的元素，必须实现Comparable接口，PriorityQueue会根据元素的排序顺序决定出队的优先级。
- PriorityQueue允许我们提供一个Comparator对象来判断两个元素的顺序
可以这样理解优先队列：
- 始终构建小顶堆，即堆顶的元素按排序算法始终最小（返回-1）.
- 排序算法是这样的：返回0，表示相等，返回整数表示大于，返回复数表示小于
- 由于优先队列即是对堆的实现，其底层也是基于动态数组加上扩容机制，只不过加了个堆排序
源码
public class PriorityQueue<E> extends AbstractQueue<E>
implements java.io.Serializable {
private static final long serialVersionUID = -7720805057305804111L;
//动态数组默认大小
private static final int DEFAULT_INITIAL_CAPACITY = 11;
/**
* Priority queue represented as a balanced binary heap: the two
* children of queue[n] are queue[2*n+1] and queue[2*(n+1)]. The
* priority queue is ordered by comparator, or by the elements'
* natural ordering, if comparator is null: For each node n in the
* heap and each descendant d of n, n <= d. The element with the
* lowest value is in queue[0], assuming the queue is nonempty.
*/
transient Object[] queue; // non-private to simplify nested class access
/**
* The number of elements in the priority queue.
*/
int size;
/**
* The comparator, or null if priority queue uses elements'
* natural ordering.
*/
private final Comparator<? super E> comparator;
transient int modCount; // non-private to simplify nested class access
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);
}
动态扩容
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);
}
双端队列Deque
Java集合提供了接口Deque来实现一个双端队列，它的功能是：
- 既可以添加到队尾，也可以添加到队首；
- 既可以从队首获取，又可以从队尾获取。
我们来比较一下Queue和Deque出队和入队的方法：
对于添加元素到队尾的操作，Queue提供了add()/offer()方法，而Deque提供了addLast()/offerLast()方法。添加元素到对首、取队尾元素的操作在Queue中不存在，在Deque中由addFirst()/removeLast()等方法提供。
注意到Deque接口实际上扩展自Queue：
public interface Deque<E> extends Queue<E> {
...
}
因此，Queue提供的add()/offer()方法在Deque中也可以使用，但是，使用Deque，最好不要调用offer()，而是调用offerLast()：
Deque是一个接口，它的实现类有ArrayDeque和LinkedList。