当前位置：首页 > news >正文

集合Queue、Deque、LinkedList、ArrayDeque、PriorityQueue详解

news 来源：原创 2025/7/22 6:45:54

1、 Queue与Deque的区别

在研究java集合源码的时候，发现了一个很少用但是很有趣的点：Queue以及Deque；
平常在写leetcode经常用LinkedList向上转型Deque作为栈或者队列使用，但是一直都不知道Queue的作用，于是就直接官方文档好了。
Queue和Deque：
Deque是Queue的子接口；
从源码中可以得知：Queue以及Deque都是继承于Collection，Deque是Queue的子接口。
public interface Deque<E> extends Queue<E> {}

Queue——单端队列；Deque——双端队列；
从Deque的解释中，我们可以得知：Deque是double ended queue，我将其理解成双端队列，就是可以在首和尾都进行插入或删除元素。
而Queue的解释中，Queue就是简单的FIFO（先进先出）队列。所以在概念上来说，Queue是FIFO的单端队列，Deque是双端队列。

Queue常用子类——PriorityQueue；Deque常用子类——LinkedList以及ArrayDeque；
Queue有一个直接子类PriorityQueue。
而Deque中直接子类有两个：LinkedList以及ArrayDeque。

PriorityQueue：
我觉得重点就在圈定的两个单词：无边界的，优先级的堆。
从源码中，明显看到PriorityQueue的底层数据结构是数组，而无边界的形容，那么指明了PriorityQueue是自带扩容机制的，具体请看PriorityQueue的grow方法。

2 PriorityQueue源码解读

top k算法的经典实现是大顶堆和小顶堆，而在JAVA中可以用PriorityQueue实现小顶堆，话不多说，直接上代码

public static List<Integer> getTopMapNum(int[] arr, int k) {Queue<Integer> priorityQueue = new PriorityQueue();List<Integer> topKList = new ArrayList<>();if (arr == null || k > arr.length || k <= 0) {return topKList;}for (int i : arr) {if (priorityQueue.size() < k) {priorityQueue.add(i);} else {if (priorityQueue.peek() < i) {priorityQueue.poll();priorityQueue.add(i);}}}while (k-- > 0) {topKList.add(priorityQueue.poll());}return topKList;
}

作为程序员，只知道简单的如何实现是不够的，最好能够深入源码，下面我们就来聊一聊PriorityQueue
PriorityQueue是优先队列，作用是保证每次取出的元素都是队列中权值最小的，这里涉及到了大小关系，元素大小的评判可以通过元素自身的自然顺序（使用默认的比较器），也可以通过构造时传入的比较器。

Java中PriorityQueue实现了Queue接口，不允许放入null元素；其通过堆实现，具体说是通过完全二叉树（complete binary tree）实现的小顶堆（任意一个非叶子节点的权值，都不大于其左右子节点的权值），也就意味着可以通过数组来作为PriorityQueue的底层实现。

上图中我们给每个元素按照层序遍历的方式进行了编号，如果你足够细心，会发现父节点和子节点的编号是有联系的，更确切的说父子节点的编号之间有如下关系：

leftNo = parentNo*2+1
rightNo = parentNo*2+2
parentNo = (nodeNo-1)/2

通过上述三个公式，可以轻易计算出某个节点的父节点以及子节点的下标。这也就是为什么可以直接用数组来存储堆的原因。
PriorityQueue的peek()和element操作是常数时间，add(), offer(), 无参数的remove()以及poll()方法的时间复杂度都是log(N)。

方法解析（JDK 1.8）
add()和offer
add()方法内部是调用的offer()，所以两个方法没啥区别，都是向队列中插入元素

新加入的元素可能会破坏小顶堆的性质，所以需要进行调整

/*** The number of times this priority queue has been* <i>structurally modified</i>.  See AbstractList for gory details.*队列调整的次数*/
transient int modCount = 0; // non-private to simplify nested class access
/*** The number of elements in the priority queue.*队列中元素的个数*/
private int size = 0;
public boolean add(E e) {//add方法内部调用的offer方法return offer(e);
}
public boolean offer(E e) {if (e == null)throw new NullPointerException();//队列调整的次数modCount++;int i = size;//如果队列元素个数大于等于队列的长度，则需要进行扩容if (i >= queue.length)grow(i + 1);size = i + 1;//如果是第一个元素，直接插入即可if (i == 0)queue[0] = e;elsesiftUp(i, e);//如果不是第一个元素，则需要进行调整return true;
}
/*** Increases the capacity of the array.*队列扩容* @param minCapacity the desired minimum capacity*/
private void grow(int minCapacity) {//原始队列容量int oldCapacity = queue.length;// Double size if small; else grow by 50%//如果原始队列容量没有超过64，则翻倍扩容，否则扩容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) // overflowthrow new OutOfMemoryError();return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;
}
/*** Inserts item x at position k, maintaining heap invariant by* promoting x up the tree until it is greater than or equal to* its parent, or is the root.** To simplify and speed up coercions and comparisons. the* Comparable and Comparator versions are separated into different* methods that are otherwise identical. (Similarly for siftDown.)** @param k the position to fill* @param x the item to insert* 元素添加*/
private void siftUp(int k, E x) {//使用构造方法传进来的比较器if (comparator != null)siftUpUsingComparator(k, x);elsesiftUpComparable(k, x);//使用默认的比较器
}
private void siftUpComparable(int k, E x) {Comparable<? super E> key = (Comparable<? super E>) x;while (k > 0) {//获取父节点的下标int parent = (k - 1) >>> 1;//父节点的元素值Object e = queue[parent];//如果新插入的元素比父节点的元素值大，循环结束，新插入节点直接插入最后即可if (key.compareTo((E) e) >= 0)break;//否则需要把父节点元素值放到新插入节点的下标（可以理解为父节点与新插入元素调换位置）queue[k] = e;//重复进行，知道父节点比子节点小k = parent;}//新插入元素放入排序后的下标queue[k] = key;
}

poll 类似，poll 从上往下进行，然后将左右进行比较，将小的一个和父节点交换

3 LinkedList以及ArrayDeque：

从官方解释来看，ArrayDeque是无初始容量的双端队列，LinkedList则是双向链表。
而我们还能看到，ArrayDeque作为队列时的效率比LinkedList要高。
而在栈的使用场景下，无疑具有尾结点，不需判空的LinkedList更为高效。
演示ArrayDeque作为队列以及LinkedList作为栈的使用：

private static void usingAsQueue() {Deque<Integer> queue=new ArrayDeque<>();System.out.println("队列为空:"+queue.isEmpty());   //判断队列是否为空queue.addLast(12);   //添加元素System.out.println(queue.peekFirst());   //获取队列首部元素System.out.println(queue.pollFirst());   //获取并移除栈顶元素}private static void usingAsStack() {//作为栈使用Deque<Integer> stack=new LinkedList<>();System.out.println("栈为空:"+stack.isEmpty());   //判断栈是否为空stack.addFirst(12);//添加元素System.out.println(stack.peekFirst());   //获取栈顶元素System.out.println(stack.pollFirst());   //获取并移除栈顶元素}

小提示：
在Deque中，获取并移除元素的方法有两个，分别是removeXxx以及peekXxx。
存在元素时，两者的处理都是一样的。
但是当Deque内为空时，removeXxx会直接抛出NoSuchElementException，
而peekXxx则会返回null。
所以无论在实际开发或者算法时，推荐使用peekXxx方法。
其实ArrayDeque和LinkedList都可以作为栈以及队列使用，但是从执行效率来说，ArrayDeque作为队列，以及LinkedList作为栈使用，会是更好的选择。

注意：
ArrayDeque 是 Deque 接口的一种具体实现，是依赖于可变数组来实现的。ArrayDeque 没有容量限制，可根据需求自动进行扩容。ArrayDeque 可以作为栈来使用，效率要高于 Stack。ArrayDeque 也可以作为队列来使用，效率相较于基于双向链表的 LinkedList 也要更好一些。注意，ArrayDeque 不支持为 null 的元素。
之后，再说为什么建议使用ArrayDeque而不是LinkedList:
链表比数组花费更多空间
链表的随机访问性质比数组差（虽然这个对栈来说问题不大）
链表的每次插入和删除都涉及到一个节点对象的创建和弃用，非常低效和浪费空间，而动态数组几乎是0花费的(数组充满时重新拷贝除外)
链表是非连续的，访问时候不能充分利用cpu cache

所以无论是栈还是队列，JDK都是建议使用ArrayDeque而不是LinkedList实现，ArrayDeque比较复杂的一点就是需要指定初始大小，当然你不指定也行。但是它的效率确实是比LinkedList高的

小结：
PriorityQueue可以作为堆使用，而且可以根据传入的Comparator实现大小的调整，会是一个很好的选择。
ArrayDeque可以作为栈或队列使用，但是栈的效率不如LinkedList高，通常作为队列使用。
LinkedList可以作为栈或队列使用，但是队列的效率不如ArrayQueue高，通常作为栈使用。

Queue和Deque的方法区别：
在java中，Queue被定义成单端队列使用，Deque被定义成双端队列使用。
而由于双端队列的定义，Deque可以作为栈或者队列使用；
而Queue只能作为队列或者依赖于子类的实现作为堆使用。
方法上的区别如下：

add offer add 底层调用offer 无区别
remove 无元素抛出异常 poll 返回null 删除元素
peek element 不删除元素，element 无元素抛出异常，peek 返回null

LinkedList与ArrayDeque在栈与队列中的使用

LinkedList

增加：
add(E e)：在链表后添加一个元素；通用方法
addLast(E e)：在链表尾部添加一个元素；特有方法
offer(E e)：在链表尾部插入一个元素
offerLast(E e)：JDK1.6本之后，在尾部添加；特有方法

特点：add 与 addLast 一个有返回值 boolean，一个无
offer 与 add 与 offerLast 一样

addFirst(E e)：在链表头部插入一个元素；特有方法
offerFirst(E e)：JDK1.6版本之后，在头部添加；特有方法

特点：offerFirst 有返回值 addFirst无
add(int index, E element)：在指定位置插入一个元素。

删除：
remove() ：移除链表中第一个元素; 通用方法
removeFirst() 移除第一个元素
pollFirst()：删除头；特有方法
pop()：和removeFirst方法一致，删除头。 ==
poll()：查询并移除第一个元素特有方法 ==

特点：remove 抛异常，poll 返回null pop 与 removeFirst remove一致
remove(E e)：移除指定元素；通用方法
removeFirst(E e)：删除头，获取元素并删除；特有方法
removeLast(E e)：删除尾；特有方法

pollLast()：删除尾；特有方法

查：
poll()：查询并移除第一个元素特有方法
pollFirst()：查询并删除头；特有方法
getFirst()：获取第一个元素；特有方法
peek()：获取第一个元素，但是不移除；特有方法
peekFirst()：获取第一个元素，但是不移除；

特点：poll 弹出数据，无数据返回null ：getFirst 无数据抛出异常, peek 返回数据，无数据返回null
getLast()：获取最后一个元素；特有方法
peekLast()：获取最后一个元素，但是不移除；
pollLast()：删除尾；特有方法
get(int index)：按照下标获取元素；通用方法

ArrayDeque
特点：
ArrayDeque实现了Deque接口。可当作栈来用，效率高于stack。也可当作队列来用，效率高于LinkedList。
底层用可变数组实现，无容量限制。
ArrayDeque是不安全的。

增加:
addFirst(E e)在数组前面添加元素
addLast(E e)在数组后面添加元素
offerFirst(E e)在数组前面添加元素，并返回是否添加成功
offerLast(E e)在数组后添加元素，并返回是否添加成功
push(E e)：与addFirst方法一致
offer(E e)：在链表尾部插入一个元素

删除：
removeFirst()删除第一个元素，并返回删除元素的值，如果为null，将抛出异常
removeLast()删除最后一个元素，并返回删除元素的值，如果为null,将抛出异常
pollFirst()删除第一个元素，并返回删除元素的值，如果为null，将返回null
pollLast()删除最后一个元素，并返回删除元素的值，如果为null,将返回null

pop()：和removeFirst方法一致，删除头。 ==
poll()：查询并移除第一个元素特有方法

查：
getFirst()获取第一个元素，如果为null，将抛出异常
getLast()获取最后一个元素，如果为null，将抛出异常
peek()：获取第一个元素，但是不移除；特有方法

注意
add() 和 offer()的区别
在容量已满的情况下，add() 方法会抛出IllegalStateException异常，offer() 方法只会返回 false
remove方法和poll方法都是删除队列的头元素，remove方法，队列为空的情况下将抛异常，而poll方法将返回null；
element和peek方法都是返回队列的头元素，但是不删除头元素，区别在与element方法在队列为空的情况下，将抛异常，而peek方法将返回null。

1、 Queue与Deque的区别

2 PriorityQueue源码解读

3 LinkedList以及ArrayDeque：

相关文章：