源码均以JDK8作为参考
队列是一种先进先出(FIFO)的数据结构。
ArrayDeque<E>:
1.简介:
ArrayDeque<E>是JDK1.6中引入的实现。
ArrayDeque<E>继承了AbsrtactCollection<E>抽象类,实现了Deque<E>接口。
因此ArrayDeque同时拥有这两者的特性,本身队列是基于先进先出(FIFO)的,但是由于JDK1.6中Deque<E>接口的实现,ArrayDeque<E>拥有了Deque<E>双端队列的特
性可以在队列的头部和尾部进行操作。
2.实现:
ArrayDeque<E>的内部实现依然是数组(elements),ArrayDeque<E>通过头部索引-tail、尾部索引-tail、内部数组-elements维护队列的结构。
ArrayDeque<E>重载了两个构造方法:
public ArrayDeque()
:无参构造函数,默认初始一个长度为16的数组。
public ArrayDeque(int numElements)
:有参构造函数,当指定的numElements小于8时,初始化一个长度为8的数组。若指定的numElements大于8时,则根据运算规则:向大于numElements的最近的2
的n次方作为初始长度。例如:当numElements为9时,默认长度为16,当numElements为45时,默认长度为64.
public ArrayDeque(Collection<? extends E> c)
:根据集合c的size按照上一个重载的构造函数进行初始化操作,并将集合c中的元素加入到队列中。
注:ArrayDeque<E>内部数组的长度始终保证是在2的n次方的数字上。
3.ArrayDeque<E>在方法实现上,由于ArrayDeque<E>实现了Queue<E>和Deque<E>接口,ArrayDeque<E>拥有了Queue<E>的单向队列的特性,同时也拥有了
Deque<E>的双端队列的特性。
在使用上,既可以按照单向队列来使用(经典的FIFO),也可以按照双端队列来使用(可以选择从头部和尾部操作队列)
4.对于队列的其他功能可以参见上一篇的Queue<E>和Deque<E>分析,总之ArrayDeque提供了一种模拟队列的数据结构,为Java中数据结构的实现增加了一种新的格式。
5.ArrayDeque<E>使用简单示例:
Queue<E>下方法使用:
Queue<String> queue = new ArrayDeque<String>();
queue.add("1");
queue.add("2");
queue.add("3");queue.poll();
queue.poll();
queue.poll();
注:Queue<E>接口下的方法只能按照经典的队列方式使用队列,先进先出(FIFO)。
Deque<E>下方法使用:
Deque<String> deque = new ArrayDeque<String>();
deque.add("1");
deque.add("2");
deque.add("3");System.out.println(deque.pollFirst());
System.out.println(deque.pollLast());
System.out.println(deque.poll());
注:Deque<E>接口下的方法,提供了一个双端队列的实现,可以自前或者自后的方式使用队列。
PriorityQueue<E>:
1.简介:
JDK1.5集合重做过程中,引入了PriorityQueue<E>,PriorityQueue<E>意为优先级队列,优先级队列不同于常规的先进先出(FIFO)队列,
比如ArrayDeque<E>,PriorityQueue<E>每次从队列中取出的是具有最高优先权的元素。
如果不提供Comparator<E>接口的实现,优先队列中的元素默认按照自然顺序排列(数组默认小的在前,字符串按照编码计算)。
如果提供了Comparator<E>接口的实现,那么就会按照Comparator<E>提供的规则进行排序。
2.实现:
PriorityQueue<E>内部实现依然是数组,PriorityQueue<E>使用queue-数组、size-长度、comparator-比较机制。
PriorityQueue<E>重载了7个构造方法:
public PriorityQueue()
public PriorityQueue(int initialCapacity)
public PriorityQueue(Comparator<? super E> comparator)
public PriorityQueue(int initialCapacity, Comparator<? super E> comparator)
public PriorityQueue(Collection<? extends E> c)
public PriorityQueue(PriorityQueue<? extends E> c)
public PriorityQueue(SortedSet<? extends E> c)
注:无参构造函数初始化时,队列默认长度为11,当使用其他构造函数时,默认长度是显示指定的长度或者传入集合的长度。
3.方法:
PriorityQueue<E>的方法实现是完全遵照Queue<E>接口定义的,但是在内部实现上,没加入一个新的元素会对队列进行重排序构造。
4.简单的示例:
Queue<Integer> priorityQueue = new PriorityQueue<Integer>();
priorityQueue.add(1);
priorityQueue.add(4);
priorityQueue.add(2);
priorityQueue.add(3);System.out.println(priorityQueue.poll());
System.out.println(priorityQueue.poll());