关于java中的Queue、Deque、PriorityQueue

2024-11-23 来源：个人技术集锦

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

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

//************************队列接口
public interface Queue<E> extends Collection<E> {
    // 继承自Collection接口的方法，
    // 在容量允许的情况下将元素放入队列返回true，空间不够时抛出异常
    boolean add(E e);
    // 在容量允许的情况下插入元素，在容量限制时，优于add方法，空间不够导致添加失败返回false，
    boolean offer(E e);
    // 返回并且删除队列头的元素，队列为空抛出异常
    E remove();
	// 返回并且删除队列头的元素，队列为空返回null
    E poll();
	//返回但不删除队列头的元素，队列为空抛出异常
    E element();
	//返回但不删除队列头的元素，队列为空返回null
    E peek();
}


//********************双端队列接口
public interface Deque<E> extends Queue<E> {
	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();
}

ArrayDeque扩容机制可以看到。如果当前容量小于64，则容量增加2；如果当前容量大于等于64，则变为原来的1.5倍。

PriorityQueue
底层数组
扩容和ArrayDeque 差不多

PriorityQueue是基于优先级堆的无界优先级队列。优先级队列的元素根据其自然顺序或在队列构造时提供的Comparator进行排序，具体取决于所使用的构造函数。优先级队列不允许空元素。依赖自然顺序的优先级队列也不允许插入不可比较的对象（这样做可能会导致ClassCastException）。

简单来说PriorityQueue就是一个优先级队列，在我们需要堆的时候可以使用PriorityQueue当作堆进行使用，因为PriorityQueue继承自AbstractQueue，而AbstractQueue实现Queue，所以PriorityQueue的方法和Queue差不多，使用起来也比较方便

并发

PriorityQueue优先队列没有对应的并发类。但是Queue接口有对应的并发实现类：java.util.concurrent.ConcurrentLinkedQueue类。
Deque接口有对应的并发实现类：java.util.concurrent.ConcurrentLinkedDeque类。

总结：
PriorityQueue可以作为堆使用，而且可以根据传入的Comparator实现大小的调整，会是一个很好的选择。
ArrayDeque通常作为栈或队列使用，但是栈的效率不如LinkedList高。
LinkedList通常作为栈或队列使用，但是队列的效率不如ArrayQueue高。
在java中，Queue被定义成单端队列使用，Deque被定义成双端队列使用。
而由于双端队列的定义，Deque可以作为栈或者队列使用，而Queue只能作为队列或者依赖于子类的实现作为堆使用。

显示全文

全部栏目

关于java中的Queue、Deque、PriorityQueue