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
)
|