当前位置: 代码迷 >> 综合 >> Java ArrayDeque、PriorityQueue 先进先出队列(FIFO)
  详细解决方案

Java ArrayDeque、PriorityQueue 先进先出队列(FIFO)

热度:60   发布时间:2024-01-17 01:35:15.0

源码均以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());




 

  相关解决方案