初識java—（四十三）Queue集合

8.5 Queue集合

Queue用于模拟隊列資料結構，隊列是遵循“先進先出”，“後進後出”的存儲規範。第一個存放的元素對象存放在隊列隊首位置，後進入的元素插入到隊尾的位置，隊列不允許随機通路隊列中元素。

Queue接口定義的方法：

Ø Void add(Object obj)：将指定元素加入此隊列的尾部。

Ø Object element()：擷取隊列頭部的元素，但不删除該元素。

Ø Boolean offer(Object obj)：将指定元素加入此隊列的尾部，當使用有容量限制的隊列時，此方法比add()方法更好。

Ø Object peek()：擷取隊列頭部的元素，但不删除該元素。如果此隊列為空，傳回null。

Ø Object poll()：擷取隊列頭部的元素，并删除該元素，如果此隊列為空，傳回Null。

Ø Object remove()：擷取隊列頭部的元素，并删除該元素。

執行個體1：

建立一個容量有限的隊列 ArrayBlockingQueue

ArrayBlockingQueue<String> abq = new ArrayBlockingQueue<String>(2);

abq.add(“hello”);

abq.add(“world”);

System.out.println(abq.size);

System.out.println(abq);

abq.add(“langsin”);

System.out.println(abq.size);

System.out.println(abq);

8.5.1 PriorityQueue實作類

PriorityQueue是一個比較标準的Queue實作類，而不是絕對标準的隊列實作，是因為PriorityQueue儲存隊列元素的順序并不是按照加入隊列的順序進行儲存。而是按照隊列元素的大小進行重新一次排序。是以使用peek()或者poll()方法擷取元素隊列位置時，并不一定就是首先存入的元素對象，而是隊列中最小的元素。

舉例1：

public static void main(String[] args) throws Exception{

pq = new ();

;

;

;

;

System.out.println(pq.toString()); //

while(pq.size()>0){

System.out.print(pq.poll() + " "); // -3 3 6 9

}

}

注意：PriorityQueue不允許插入null值，它需要對隊列元素進行排序，PriorityQueue的元素排序分兩種情況，自然排序和定制排序，參照TreeSet。

8.5.2 Deque接口與ArrayDeque實作類

Deque接口是Queue接口的子接口，它代表一個雙端隊列，Deque接口裡定義了一些雙端隊列的方法，這些方法允許從兩端來操作隊列元素。

Ø void addFirst(Object obj)：将指定元素插入到該隊列的首部。

Ø void addlast(Object obj)：将指定元素插入到該隊列的尾部。

Ø Iterator desceningIterator()：傳回該雙端隊列對應的疊代器，該疊代器将以逆向順序來疊代隊列中的元素。

Ø Object getFirst()：擷取雙端隊列的第一個元素。

Ø Object getLast()：擷取雙端隊列的最後一個元素。

Ø Boolean offerFirst(Object obj)：将指定元素插入到雙端隊列的開頭。

Ø Boolean offerLast(Object obj)：将指定元素插入到雙端隊列的末尾。

Ø Object peekFrist()：擷取但不删除雙端隊列的第一個元素。

Ø Object peekLast()：擷取但不删除雙端隊列的最後一個元素。

Ø Object pollFrist()：擷取并删除雙端隊列的第一個元素。

Ø Object pollLast()：擷取并删除雙端隊列的最後一個元素。

Ø Object pop()：擷取并删除該雙端隊列的第一個元素。

Ø void push(Object obj)：将一個元素插入到該雙端隊列的隊首位置，相當于addFrist()

Ø Object removeFirst()：擷取并删除該雙端隊列的第一個元素。

Ø Object removeLast()：擷取并删除該雙端隊列的最後一個元素。

舉例1：

public static void main(String[] args) throws Exception{

deque = new();

;

;//相當于offerLast()

;

System.out.println(deque);

; //相當于offerFirst()

System.out.println(deque);

System.out.println(deque.size());

Object obj = deque.peek(); //相當于peekFirst()

System.out.println(obj);

System.out.println(deque.size());

obj = deque.poll();//相當于pollFist()

System.out.println(obj);

System.out.println(deque.size());

}

8.5.3 LinkedList實作類

LinkedList類是List接口的實作類，是以可根據索引來随機通路集合中元素。LinkedList還實作了Deque接口，是以可被當做雙端隊列來使用，同樣也可以被當做“棧”來使用。

舉例1：

public static void main(String[] args) throws Exception{

list = new();

; abc 789 123 456

;

//System.out.println(list);

;

//System.out.println(list);

;

System.out.println(list);

Object obj = list.pop();

System.out.println(obj);

System.out.println(list.size());

}

LinkedList與ArrayList、ArrayDeque的實作機制不同，ArrayList和ArrayDeque内部以數組的形式來儲存集合中元素，是以随機通路集合元素時有較好的性能。而LinkedList内部以連結清單的形式來儲存集合中的元素，是以随機通路集合元素時性能不如ArrayList和ArrayDeque。而插入、删除元素時性能非常出色，隻需要改變指針所指向的位址即可。

這裡有一個問題，請用LinkedList模拟棧資料結構的集合，并測試。

首先分析這個題目的意思，你自己定義一個集合類，在這個集合類内部可以使用LinkedList模拟。這個集合最終是個棧結構的集合。

public class MyStack{

private LinkedList link;

public MyStack(){

link = new LinkedList();

}

public void add(Object obj){

link.addFirst(obj);

}

public Object get(){

//(1)第一種做法。每次都拿到了，然而，再來拿的時候，還是拿的第一個。而棧記憶體提取資料的時候是拿到一個踢除一個，剩下的往上移一位。拿一個往上走一位。是以我們用下邊的那個方法，拿到第一個了并踢除了。是以你下次拿的時候才會拿到新的内容。要不然你拿到的永遠都是第一個。

//return link.getFirst();

return link.removeFirst();

}

//這裡要添加這麼一個方法，防止你拿資料的時候拿到了空的位置的時候該怎麼辦。有了這個方法，我們就可以用while()循環來寫代碼了。

public Boolean isEmpty(){

return link.isEmpty();

}

}