Java中的队列Queue,优先级队列PriorityQueue

时间:2021-12-28 17:56:21

队列Queue

在java5中新增加了java.util.Queue接口,用以支持队列的常见操作。该接口扩展了java.util.Collection接口。

Queue使用时要尽量避免Collection的add()和remove()方法,而是要使用offer()来加入元素,使用poll()来获取并移出元素。

它们的优点是通过返回值可以判断成功与否,add()和remove()方法在失败的时候会抛出异常。

如果要使用前端而不移出该元素,使用element()或者peek()方法。


值得注意的是LinkedList类实现了Queue接口,因此我们可以把LinkedList当成Queue来用。

eg:

                Queue<String> queue = new LinkedList<String>();
queue.offer(
"Hello");
queue.offer(
"World!");
queue.offer(
"你好!");
System.out.println(queue.size());
String str;
while ((str = queue.poll()) != null) {
System.out.print(str);
}
System.out.println();
System.out.println(queue.size());
输出:
04-01 09:57:15.665: I/System.out(21299): 3
04-01 09:57:15.665: I/System.out(21299): HelloWorld!你好!
04-01 09:57:15.665: I/System.out(21299): 0

 

优先级队列PriorityQueue

优先级队列PriorityQueue是不同于先进先出队列的另一种队列,每次从队列中取出的是具有最高优先权的元素。

优先队列可用有序数组或堆实现,但是常用堆来实现,下面是2种实现效率的比较:

 Java中的队列Queue,优先级队列PriorityQueue

 

使用:用于获取优先权最高的元素。

例如:在1000个数中找到最大的那个数。如果用快速排序对数就行排序,时间复杂度是O(NlogN);而用优先队列(用队实现)存储数据,然后取出最大元素(此处为优先权最大的元素)这种数据结构时间复杂度为O(logN)。

 

java.util.PriorityQueue方法

java.util.PriorityQueue是从JDK1.5开始提供的新的数据结构接口。如果不提供Comparator的话,优先队列中元素默认按自然顺序排列,也就是数字默认是小的在队列头,字符串则按字典序排列优先级队列不允许  null 元素。其提供的方法如下:

Java中的队列Queue,优先级队列PriorityQueue

Java中的队列Queue,优先级队列PriorityQueue

 

eg:

Java中的队列Queue,优先级队列PriorityQueueJava中的队列Queue,优先级队列PriorityQueue
<span style="font-size: 18px;">package zyang.priorityQueue;

/**
* Fuction:
*
@version 2013-2-24 下午8:15:59
*
@since 1.0
*/

public class Student {
private int number;
private String name;

public Student(int number,String name){
this.number=number;
this.name=name;
}

public int getNumber() {
return number;
}

public void setNumber(int number) {
this.number = number;
}

public String getName() {
return name;
}

public void setName(String name) {
this.name = name;
}

@Override
public String toString() {
return "Student [number=" + number + ", name=" + name + "]";
}
}
</span>
View Code
Java中的队列Queue,优先级队列PriorityQueueJava中的队列Queue,优先级队列PriorityQueue
<span style="font-size: 18px;">package zyang.priorityQueue;

import java.util.Comparator;

/**
* Fuction:
* 按学号排序 先按学号排序,学号相等时,按姓名排序 o1>o2返回-1,o1=o2返回0,o1<o2返回1
*
@author
*
@version 2013-2-24 下午8:16:26
*
@since 1.0
*/

public class ComparetorByNumber implements Comparator {

public int compare(Object o1, Object o2) {
Student s1
=(Student)o1;
Student s2
=(Student)o2;

//compare by number
int result=s1.getNumber() > s2.getNumber() ? 1 :(s1.getNumber() == s2.getNumber() ? 0 : -1);
//if number is equal, then compare by name
if (result==0){
int compareByName=s1.getName().compareTo(s2.getName());
if(compareByName>0)
result
=1;
else if(compareByName==0)
result
=0;
else
result
=-1;
}
//end if

return (-result); //如果是result,则a>b比较结果后排序是ba,-result代表倒序排序
}
}
</span>
View Code
Java中的队列Queue,优先级队列PriorityQueueJava中的队列Queue,优先级队列PriorityQueue
<span style="font-size: 18px;">package zyang.priorityQueue;

import java.util.PriorityQueue;

/**
* Fuction:
*
*
@author yangzhong E-mail:yangzhonglive@gmail.com
*
@version 2013-2-24 下午8:15:39
*
@since 1.0
*/

public class PriorityQueueApp {

/**
*
@param args
*/
public static void main(String[] args) {
PriorityQueue
<Student> priorityQueue=new PriorityQueue<Student>(3,new ComparetorByNumber());

Student[] student
={new Student(3,"wangwu"),new Student(2,"lisi"),
new Student(5,"xiaowang"),new Student(8,"lihua")};

for(Student s: student){
priorityQueue.offer(s);
//use offer() method to add elements to the PriorityQueue
}

System.out.println(
"size: " + priorityQueue.size()); //print size
System.out.println("peek: " + priorityQueue.peek()); //return highest priority element in the queue without removing it
System.out.println("size: " + priorityQueue.size()); //print size
System.out.println("poll: " + priorityQueue.poll()); //return highest priority element and removes it from the queue
System.out.println("size: " + priorityQueue.size()); //print size
while(!priorityQueue.isEmpty()) {
System.out.print(priorityQueue.poll()
+ " ");
}
System.out.println(
" the end!");
}
}
</span>
View Code


结果:

Java中的队列Queue,优先级队列PriorityQueue