Queue
Queue接口是Java 5.0新引入的一个接口，位于java.util包中，它通常用来处理所有的FIFO队列，当然依据实现的不同，Queue的具体实现也可以处理FILO栈，或者是依据固定顺序对元素排序。与List不同，从Queue中不能通过Index取值；与Set不一样，你可以往Queue中插入重复值。
Queue接口提供了五个方法：offer方法用于将元素插入到队列尾中，和add方法不同的是，当Queue已经满了，不能再插入数据时，offer方法会直接返回false，而不会抛出任何异常；remove方法和poll方法会从队列头中取出数据，并且将元素从队列中删除，两个方法几乎完全相同，唯一的差别之处在于对空队列的处理不同，前者会抛出NoSuchElementException异常并返回null，而后者只是简单地返回null；element方法和peek方法用于从队列头中获取元素，但不对队列做删除操作，两个方法的差别与前两个方法的差别相同，element方法会抛出异常。
下面，我们看一个简单的示例：
import
java.io.IOException;
import
java.io.PrintStream;
import
java.util.LinkedList;
import
java.util.Queue;
 
public
class
QueueTester
{
public
Queue
<
String
>
q;
 
public
QueueTester( )
{
q
=
new
LinkedList
<
String
>
( );
 }
public
void
testFIFO(PrintStream out)
throws
IOException
{
//
往队列中插入数据；
q.add(
"
First
"
);
q.add(
"
Second
"
);
q.add(
"
Third
"
);
Object o;
//
从队列头中取出元素，并且将该元素中删除。
while
((o
=
q.poll( ))
!=
null
)
{
out.println(o);
}
}
上面的示例十分简单，运行结果读者自己猜猜看。
优先级队列
某些时候，我们可能希望我们插入队列中的数据不是按插入的时间来排序，而是按照我们指定的顺序来排序。为了实现此功能，Java 5.0为我们提供了一个新类－PriorityQueue。
当采用该类时，若不提供Comparator，则优先级队列会以数据的自然顺序(natural order)对数据排序。对于数值类型而言，其自然顺序就是比较其数值大小；对于实现了Comparable接口的类而言，其自然顺序就是comapareTo方法指定的顺序；如果给定的数据类型是一个引用类型，然而该类型却没有实现Comaprable接口，则运行时会出错。
简短的解释后，我们来看一个示例：
package
com.jiang.tiger.chap1;
import
java.util.Comparator;
import
java.util.PriorityQueue;
public
class
PriorityQueueTester
{
public
static
void
main(String[] args)
{
//
新建一个优先级队列，排序依据为Integer的自然规则（natural ordering）。
PriorityQueue
<
Integer
>
queue
=
new
PriorityQueue
<
Integer
>
(
20
);
//
按指定的顺序加入数据。
for
(
int
i
=
0
; i
<
20
; i
++
)
{
queue.offer(
20
-
i);
}
//
打印数据
for
(
int
i
=
0
; i
<
20
; i
++
)
{
System.out.print(queue.poll( )
+
"
\t
"
);
if
(
0
==
(i
+
1
)
%
5
) System.out.println();
}
PriorityQueue
<
Person
>
queue2
=
new
PriorityQueue
<
Person
>
(
5
);
queue2.offer(
new
Person(
"
jiang
"
,
24
));
queue2.offer(
new
Person(
"
lotus
"
,
29
));
queue2.offer(
new
Person(
"
swan
"
,
20
));
queue2.offer(
new
Person(
"
java
"
,
30
));
queue2.offer(
new
Person(
"
tiger
"
,
1
));
for
(
int
i
=
0
; i
<
5
; i
++
)
{
System.out.println(queue2.poll( ));
}
//
新建一个优先级队列，并且为其指定数据排序的依据：偶数优先，小数优先。
PriorityQueue
<
Integer
>
pq
=
new
PriorityQueue
<
Integer
>
(
20
,
new
Comparator
<
Integer
>
( )
{
public
int
compare(Integer i, Integer j)
{
int
result
=
i
%
2
-
j
%
2
;
if
(result
==
0
)
result
=
i
-
j;
return
result;
}
}
);
//
按指定的顺序加入数据。
for
(
int
i
=
0
; i
<
20
; i
++
)
{
pq.offer(
20
-
i);
}
//
打印数据
for
(
int
i
=
0
; i
<
20
; i
++
)
{
System.out.print(pq.poll( )
+
"
\t
"
);
if
(
0
==
(i
+
1
)
%
5
) System.out.println();
}
//
优先级队列中存放的数据类型没有实现Comparable接口
PriorityQueue
<
Person2
>
queue3
=
new
PriorityQueue
<
Person2
>
(
5
);
queue3.offer(
new
Person2(
"
jiang
"
,
24
));
queue3.offer(
new
Person2(
"
lotus
"
,
29
));
queue3.offer(
new
Person2(
"
swan
"
,
20
));
queue3.offer(
new
Person2(
"
java
"
,
30
));
queue3.offer(
new
Person2(
"
tiger
"
,
1
));
for
(
int
i
=
0
; i
<
5
; i
++
)
{
System.out.println(queue3.poll( ));
}
}
 }
class
Person
implements
Comparable
{
//
为简化，省略了getter方法，而直接采用了public
public
String name;
public
int
age;
public
Person(String name,
int
age)
{
this
.name
=
name;
this
.age
=
age;
}
public
String toString()
{
return
"
name =
"
+
name
+
"
, age =
"
+
age;
}
public
int
compareTo(Object person)
{
//
TODO 自动生成方法存根
return
(
this
.age
-
((Person)person).age);
}
}
class
Person2
{
//
为简化，省略了getter方法，而直接采用了public
public
String name;
public
int
age;
public
Person2(String name,
int
age)
{
this
.name
=
name;
this
.age
=
age;
}
public
String toString()
{
return
"
name =
"
+
name
+
"
, age =
"
+
age;
}
}
上面程序的执行结果为：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
name
=
tiger
,
age
=
1
name
=
swan
,
age
=
20
name
=
jiang
,
age
=
24
name
=
lotus
,
age
=
29
name
=
java
,
age
=
30
2
4
6
8
10
12
14
16
18
20
1
3
5
7
9
11
13
15
17
19
Exception in thread
"
main
"
java.lang.ClassCastException: com.jiang.tiger.chap1.Person2
at java.util.PriorityQueue.fixUp(Unknown Source)
at java.util.PriorityQueue.offer(Unknown Source)
at com.jiang.tiger.chap1.PriorityQueueTester.main(PriorityQueueTester.java:
58
)
|