java集合框架Queue(E)、LinkedList、PriorityQueue的深入理解

18-06-28 来源：[db:作者]

收藏我要投稿

什么是Queue

先百度翻译一下Queue:

队列是一种特殊的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

Queue是一个接口，其子类是一种实现了队列的集合，Queue接口扩展了Collection。

在队列这种数据结构中，按照元素出入顺序，最先插入的元素将是最先被删除的元素；反之最后插入的元素将是最后被删除的元素，称为“先进先出”（FIFO—first in first out）。

Queue接口添加了多个用来操作head的特殊方法：

操作元素	抛出异常	返回特殊值
查询	element()：返回队列的头，但不移除它。如果队列为空，会抛出NoSuchElementException异常	peek()：返回队列的头，但是不移除它。如果队列是空的，则返回null。它与element()方法的区别只是在与对空队列的处理。
删除	remove()：返回队列的头，并从队列中移除它。如果队列为空，则抛出NoSuchElementException异常	poll():返回队列的头，并从队列中移除它。如果队列为空，则返回null。它与remove()方法的区别只是在与对空队列的处理。
插入	add(E elem):尝试将给定的元素elem插入当前队列尾部。如果尝试成功，返回true，如果当前没有空间，则返回 IllegalStateException。	offer(E elem)：尝试将给定的元素elem插入当前队列尾部。如果尝试成功，返回true，否则返回false。该方法比Collection的add方法更可取，因为在添加失败的情况下，add方法只能通过抛出异常来表示操作失败。

注意：队列一般不应该接受null元素，因为null是poll和peek方法用以表示队列为空的“警戒值”。

LinkedList类提供了Queue的最简单的实现。由于历史原因，LinkedList类可以接受null元素，但是在将LinkedList实例作为队列使用时，应该避免插入null元素。

LinkedList是一个双向链表，它的特性与ArrayList相反：其在中间添加或移除一个元素的代价是O(1)，因为不需要进行复制，而从指定位置i获取一个元素的代价是O(i)，因为需要从列表的某一端开始依次遍历到列表的第i个元素。所以集合容器适合增删改，但不适合查询。

什么是链表？

由一个链子把多个节点连接起来组成的数据。

节点：由数据和地址组成。(数据域和指针域组成)

上面这段话可能有点难理解，下面简单画个图：

解释一下：链表就如上图那些个连起来的框框一样。负责把这些框框连起来的线就叫指针域，其在内存中的表现就是在当前元素中记录下一个元素的地址值。每一个元素都记录下一个元素的地址值，我们如果要查找一个元素，从头开始遍历下一个元素的地址值并校验其中的元素值，直到找到位置。

这样我们就不难理解为什么LinkedList找一个元素会这么费劲了。因为你要查找任意一个元素都要从头开始遍历。

那为什么说它增删快呢？

看下图：假如我要在这个链表6元素后添加一个元素9怎么办？

在链表中只需把6框的下一元素地址值擦写为9，9框的下一元素地址值存为8即可。没有对比就没有伤害，相较于数组的操作规模，这个添加数据的代价简直可忽略不计。

LinkedList的特有功能

添加	获取	删除
addFirst(Object e)：将元素添加到列表中作为第一个元素	getFirst(Object e)：返回列表中的第一个对象	removeFirst()：移除列表中的第一个对象
addLast(Object e)：将元素添加到列表中作为最后一个元素	getLast(Object e)：返回列表中的最后一个对象	removeLast()：移除列表中的最后一个对象

PriorityQueue是Queue的另一个实现，它是基于优先级堆的无边界队列。队列的头是队列中最小的元素，这里的”最小”取决于元素的自然顺序或者另外提供的比较器。

PriorityQueue不是一般意义上的有序队列，我们不能将它作为参数传给一个接受有序集合的方法，因为它的iterator方法返回的迭代器不能保证按照优先级顺序对元素进行遍历，而只能保证从队列中移除元素时是按照给定顺序进行的。

迭代器可以按任意顺序对元素进行遍历，如果需要对其进行有序的遍历，可以把元素解析成数组，然后对数组进行排序。