Queue
Queue接口是Java 5.0新引入的一個(gè)接口，位于java.util包中，它通常用來(lái)處理所有的FIFO隊(duì)列，當(dāng)然依據(jù)實(shí)現(xiàn)的不同，Queue的具體實(shí)現(xiàn)也可以處理FILO棧，或者是依據(jù)固定順序?qū)υ嘏判颉ＥcList不同，從Queue中不能通過(guò)Index取值；與Set不一樣，你可以往Queue中插入重復(fù)值。
Queue接口提供了五個(gè)方法：offer方法用于將元素插入到隊(duì)列尾中，和add方法不同的是，當(dāng)Queue已經(jīng)滿了，不能再插入數(shù)據(jù)時(shí)，offer方法會(huì)直接返回false，而不會(huì)拋出任何異常；remove方法和poll方法會(huì)從隊(duì)列頭中取出數(shù)據(jù)，并且將元素從隊(duì)列中刪除，兩個(gè)方法幾乎完全相同，唯一的差別之處在于對(duì)空隊(duì)列的處理不同，前者會(huì)拋出NoSuchElementException異常并返回null，而后者只是簡(jiǎn)單地返回null；element方法和peek方法用于從隊(duì)列頭中獲取元素，但不對(duì)隊(duì)列做刪除操作，兩個(gè)方法的差別與前兩個(gè)方法的差別相同，element方法會(huì)拋出異常。
下面，我們看一個(gè)簡(jiǎn)單的示例：
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?
{
????
//
往隊(duì)列中插入數(shù)據(jù)；
????q.add(
"
First
"
);
????q.add(
"
Second
"
);
????q.add(
"
Third
"
);
??
????Object?o;
????
//
從隊(duì)列頭中取出元素，并且將該元素中刪除。
????
while
?((o?
=
?q.poll(?))?
!=
?
null
)?
{
??????out.println(o);
????}
??}
上面的示例十分簡(jiǎn)單，運(yùn)行結(jié)果讀者自己猜猜看。
優(yōu)先級(jí)隊(duì)列
某些時(shí)候，我們可能希望我們插入隊(duì)列中的數(shù)據(jù)不是按插入的時(shí)間來(lái)排序，而是按照我們指定的順序來(lái)排序。為了實(shí)現(xiàn)此功能，Java 5.0為我們提供了一個(gè)新類－PriorityQueue。
當(dāng)采用該類時(shí)，若不提供Comparator，則優(yōu)先級(jí)隊(duì)列會(huì)以數(shù)據(jù)的自然順序(natural order)對(duì)數(shù)據(jù)排序。對(duì)于數(shù)值類型而言，其自然順序就是比較其數(shù)值大小；對(duì)于實(shí)現(xiàn)了Comparable接口的類而言，其自然順序就是comapareTo方法指定的順序；如果給定的數(shù)據(jù)類型是一個(gè)引用類型，然而該類型卻沒(méi)有實(shí)現(xiàn)Comaprable接口，則運(yùn)行時(shí)會(huì)出錯(cuò)。
簡(jiǎn)短的解釋后，我們來(lái)看一個(gè)示例：
package
?com.jiang.tiger.chap1;
import
?java.util.Comparator;
import
?java.util.PriorityQueue;
public
?
class
?PriorityQueueTester?
{
??
public
?
static
?
void
?main(String[]?args)?
{
?????
//
新建一個(gè)優(yōu)先級(jí)隊(duì)列，排序依據(jù)為Integer的自然規(guī)則（natural?ordering）。?
?????PriorityQueue
<
Integer
>
?queue?
=
?
new
?PriorityQueue
<
Integer
>
(
20
);
?????
//
?????按指定的順序加入數(shù)據(jù)。
?????
for
?(
int
?i
=
0
;?i
<
20
;?i
++
)?
{
???????queue.offer(
20
-
i);
?????}
?????
?????
//
?打印數(shù)據(jù)
?????
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(?));
?????}
?????
?????
//
新建一個(gè)優(yōu)先級(jí)隊(duì)列，并且為其指定數(shù)據(jù)排序的依據(jù)：偶數(shù)優(yōu)先，小數(shù)優(yōu)先。
?????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;
??????????}
????????}
??????);
??????
//
?按指定的順序加入數(shù)據(jù)。
??????
for
?(
int
?i
=
0
;?i
<
20
;?i
++
)?
{
????????pq.offer(
20
-
i);
??????}
??????
??????
//
?打印數(shù)據(jù)
??????
for
?(
int
?i
=
0
;?i
<
20
;?i
++
)?
{
??????????System.out.print(pq.poll(?)?
+
?
"
\t
"
);
??????????
if
?(
0
?
==
?(i?
+
?
1
)?
%
?
5
)?System.out.println();
??????}
??????
??????
//
優(yōu)先級(jí)隊(duì)列中存放的數(shù)據(jù)類型沒(méi)有實(shí)現(xiàn)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?
{
???????
//
????為簡(jiǎn)化，省略了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?自動(dòng)生成方法存根
????????
return
?(
this
.age?
-
?((Person)person).age);
????}
}
????
class
?Person2?
{
???????
//
????為簡(jiǎn)化，省略了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;
??????}
}
????
上面程序的執(zhí)行結(jié)果為：
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
)
|