JAVA中的Queue与PriorityQueue

时间:2022-09-30 17:54:53

Queue是一个典型的先进先出容器,从容器的一段放入对象,从容器的另一段取出对象,所以对象放入容器的顺序便是取出时的顺序。正因为队列的此种特性,它也被经常当做一种可靠的将对象从程序的某个区域传输到另一个区域的途径,队列在并发编程中的运用会很多。

LinkedList提供了方法支持队列的行为,实现了Queue接口,LinkedList可以看做是Queue的一种实现,可以将LinkedList上转型为Queue使用,看下面一段代码:

package access;
import java.util.*;
public class QueueDemo {
public static void printQ(Queue queue){
while(queue.peek() != null)
System.out.print(queue.remove() + " ");
System.out.println();
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Queue<Integer> queue = new LinkedList<Integer>();
Random rand = new Random(47);
for(int i = 0; i < 10; i++)
queue.offer(rand.nextInt(i + 10));
printQ(queue);
Queue<Character> qc = new LinkedList<Character>();
for(char c : "Brontosaurus".toCharArray())
qc.offer(c);
printQ(qc);
}

}
此程序的运行结果为:

JAVA中的Queue与PriorityQueue
offer()方法:与Queue相关的方法之一,在允许的情况下,将一个元素插入到队尾,否则返回false。

peek()和element()方法:在不移除的情况下返回队头,但peek方法在队列为空时返回null,element方法则会抛出异常。

poll()和remove()方法:移除并返回队头,但poll方法在队列为空时返回null,remove方法则会抛出异常。

在随机数生成的时候,若有种子值,则通过伪随机算法得到的值均不变;若无种子值,则得到的值每次均不同。

自动包装机制自动将nextInt方法的int结果转化为Integer对象,将char结果转化为Character对象。

实际上Queue接口窄化了LinkedList的方法的访问权限,只有恰当的方法才可以使用,我们能够访问的LinkedList方法会减少,虽然可以将Queue转型会LinkedList,但这样做并不太合适。

与Queue相关的方法提供了完整独立的功能,对于Queue所继承的Collection,在不需要使用它的任何方法的情况下就可以拥有一个可以使用的Queue。

先进先出是一种典型的队列规则,队列规则指的是在给定一组队列中的元素的情况下确定下一个弹出队列元素的规则,先进先出声明的是下一个元素应该是等待时间最长的元素。

而在优先级队列中声明下一个弹出元素是最需要的元素,其具有最高优先级,PriorityQueue提供了这样的实现。当我们在PriorityQueue上调用offer方法来插入一个对象时,这个对象会在队列中自动被排序,默认的排序是自然顺序,但我们可以通过提供自己的Comparator来修改这一顺序。PriorityQueue可以确保当我们调用peek、poll、remove等方法时获取的元素是整个队列中优先级最高的元素。看下面一段代码:

package access;
import java.util.*;
public class PriorityQueueDemo {

public static void main(String[] args) {
// TODO Auto-generated method stub
PriorityQueue<Integer> priorityQueue =
new PriorityQueue<Integer>();
Random rand = new Random(47);
for(int i = 0; i < 10; i++)
priorityQueue.offer(rand.nextInt(i + 10));
QueueDemo.printQ(priorityQueue);
List<Integer> ints = Arrays.asList(25, 22, 20,
18, 14, 9, 3, 1, 1, 2, 3, 9, 14, 18, 21, 23, 25);
priorityQueue = new PriorityQueue<Integer>(ints);
QueueDemo.printQ(priorityQueue);
priorityQueue = new PriorityQueue<Integer>(
ints.size(), Collections.reverseOrder());
priorityQueue.addAll(ints);
QueueDemo.printQ(priorityQueue);

String fact = "EDUCATION SHOULD ESCHEW OBFUSCATION";
List<String> strings = Arrays.asList(fact.split(""));
PriorityQueue<String> stringPQ =
new PriorityQueue<String>(strings);
QueueDemo.printQ(stringPQ);
stringPQ = new PriorityQueue<String>(
strings.size(), Collections.reverseOrder());
stringPQ.addAll(strings);
QueueDemo.printQ(stringPQ);

Set<Character> charSet = new HashSet<Character>();
for(char c : fact.toCharArray())
charSet.add(c);
PriorityQueue<Character> characterPQ =
new PriorityQueue<Character>(charSet);
QueueDemo.printQ(characterPQ);
}

}
此程序的运行结果为:

JAVA中的Queue与PriorityQueue
可以看到的是在Queue中重复是被允许的,最小的值拥有最高的优先级,但如果是String,空格也算是值,并且空格的优先级比字母要高,在第四五行输出中可以看到空格的排序。

由于使用的是同样的随机种子47,所以二者生成的随机队列值一样,但存储顺序不同。

Collection.reverseOrder方法会产生反序的Collection。

最后的HashSet来消除重复的Character。