摘要：除此之外，還有一個接口，代表一個雙端隊列，雙端隊列可以同時從兩端刪除添加元素，因此的實現(xiàn)類既可當成隊列使用，也可當成棧使用。相當于棧方法將一個元素進該雙端隊列所表示的棧的棧頂。

Queue用于模擬隊列這種數(shù)據(jù)結(jié)構(gòu)，隊列通常是指“先進先出”（FIFO）的容器。隊列的頭部保存在隊列中存放時間最長的元素，隊列的尾部保存在隊列中存放時間最短的元素。新元素插入（offer）到隊列的尾部，訪問元素（poll）操作會返回隊列頭部的元素。通常，隊列不允許隨機訪問隊列中的元素

Queue接口的方法

void add(Object e)：將指定元素加入此隊列的尾部

Object element()：獲取隊列頭部的元素，但是不刪除該元素

boolean offer(Object e)：將指定的元素插入此隊列的尾部。當使用容量有限的隊列時，此方法通常比add(Object e)有效

Object peek()：返回隊列頭部的元素，但是不刪除該元素。如果隊列為空，則返回null

Object poll()：返回隊列頭部的元素，并刪除該元素。如果隊列為空，則返回null

Object remove()：獲取隊列頭部的元素，并刪除該元素

Queue接口有一個PriorityQueue實現(xiàn)類。除此之外，Queue還有一個Deque接口，Deque代表一個“雙端隊列”，雙端隊列可以同時從兩端刪除、添加元素，因此Deque的實現(xiàn)類既可當成隊列使用，也可當成棧使用。Java為Deque提供了ArrayDeque實現(xiàn)類和LinkedList兩個實現(xiàn)類

PriorityQueue保存隊列元素的順序不是按加入隊列的順序，而是按隊列元素的大小進行重新排序。因此當調(diào)用peek()或pool()方法取出隊列中頭部的元素時，并不是取出最先進入隊列的元素，而是取出隊列中的最小的元素

public class PriorityQueueTest 
{
    public static void main(String[] args)
    {
        PriorityQueue pq = new PriorityQueue();
        pq.offer(6);
        pq.add(-3);
        pq.add(20);
        pq.offer(18);
        //輸出：[-3, 6, 20, 18]
        System.out.println(pq);
    }
}

實際上，程序多次調(diào)用poll()方法，既可看到元素按從小到大的順序“移出隊列”，PriorityQueue隊列對元素的要求與TreeSet對元素的要求基本一致

PriorityQueue不允許插入null元素，它還需要對隊列元素進行排序，PriorityQueue有兩種排序方式

自然排序：采用自然排序的PriorityQueue集合中的元素必須實現(xiàn)Comparator接口，而且應該是一個類的多個實例，否則可能導致ClassCastException異常

定制排序：創(chuàng)建PriorityQueue隊列時，傳入一個Comparable對象，該對象負責對所有隊列中的所有元素進行排序。采用定制排序不要求必須實現(xiàn)Comparator接口

Deque接口是Queue接口的子接口，它代表一個雙端隊列

void addFirst(Object e)：將指定元素插入到雙端隊列的頭部

void addLast(Object e)：將指定元素插入到雙端隊列的尾部

Iteratord descendingItrator()：返回該雙端隊列對應的迭代器，該迭代器以逆向順序來迭代隊列中的元素

Object getFirst()：獲取但不刪除雙端隊列的第一個元素

Object getLast()：獲取但不刪除雙端隊列的最后一個元素

boolean offerFirst(Object e)：將指定元素插入到雙端隊列的頭部

boolean offerLast(OBject e)：將指定元素插入到雙端隊列的尾部

Object peekFirst()：獲取但不刪除雙端隊列的第一個元素；如果雙端隊列為空，則返回null

Object peekLast()：獲取但不刪除雙端隊列的最后一個元素；如果雙端隊列為空，則返回null

Object pollFirst()：獲取并刪除雙端隊列的第一個元素；如果雙端隊列為空，則返回null

Object pollLast()：獲取并刪除雙端隊列的最后一個元素；如果雙端隊列為空，則返回null

Object pop()（棧方法）：pop出該雙端隊列所表示的棧的棧頂元素。相當于removeFirst()

void push(Object e)(棧方法)：將一個元素push進該雙端隊列所表示的棧的棧頂。相當于addFirst(e)

Object removeFirst()：獲取并刪除該雙端隊列的第一個元素

Object removeFirstOccurence(Object o)：獲取并刪除該雙端隊列的第一次出現(xiàn)的元素o

Object removeLast()：獲取并刪除該雙端隊列的最后一個元素o

Object removeLastOccurence(Object o)：獲取并刪除該雙端隊列的最后一次出現(xiàn)的元素o

Deque與Queue的方法對照圖

Deque與Stack的方法對照圖

ArrayDeque是一個基于數(shù)組實現(xiàn)的雙端隊列，創(chuàng)建Deque時同樣可指定一個numElements參數(shù)，該參數(shù)用于指定Object[]數(shù)組的長度；如果不指定numElements參數(shù)，Deque底層數(shù)組的長度為16

當程序中需要使用“棧”這種數(shù)據(jù)結(jié)構(gòu)時，推薦使用ArrayDeque，盡量避免使用Stack——因為Stack是古老的集合，性能較差

//把ArrayDeque當成棧使用

import java.util.*;

public class ArrayDequeStack
{
    public static void main(String[] args)
    {
        ArrayDeque stack = new ArrayDeque();
        // 依次將三個元素push入"棧"
        stack.push("金州勇士");
        stack.push("俄克拉荷馬雷霆");
        stack.push("克利夫蘭騎士");
        // 輸出：[克利夫蘭騎士, 俄克拉荷馬雷霆, 金州勇士]
        System.out.println(stack);
        // 訪問第一個元素，但并不將其pop出"棧"，輸出：克利夫蘭騎士
        System.out.println(stack.peek());
        // 依然輸出：[克利夫蘭騎士, 俄克拉荷馬雷霆, 金州勇士]
        System.out.println(stack);
        // pop出第一個元素，輸出：克利夫蘭騎士
        System.out.println(stack.pop());
        // 輸出：[俄克拉荷馬雷霆, 金州勇士]
        System.out.println(stack);
    }
}

ArrayDeque作為隊列使用，按“先進先出”的方式操作集合元素

import java.util.*;

public class ArrayDequeQueue
{
    public static void main(String[] args)
    {
        ArrayDeque queue = new ArrayDeque();
        // 依次將三個元素加入隊列
        queue.offer("克利夫蘭騎士");
        queue.offer("俄克拉荷馬雷霆");
        queue.offer("金州勇士");
        // 輸出：[克利夫蘭騎士, 俄克拉荷馬雷霆, 金州勇士]
        System.out.println(queue);
        // 訪問隊列頭部的元素，但并不將其poll出隊列"棧"，輸出：克利夫蘭騎士
        System.out.println(queue.peek());
        // 依然輸出：[克利夫蘭騎士, 俄克拉荷馬雷霆, 金州勇士]
        System.out.println(queue);
        // poll出第一個元素，輸出：克利夫蘭騎士
        System.out.println(queue.poll());
        // 輸出：[俄克拉荷馬雷霆, 金州勇士]
        System.out.println(queue);
    }
}

LinkedList是List接口的實現(xiàn)類——這意味著它是一個List集合，可以根據(jù)索引來隨機訪問集合中的元素。此外，LinkedList還實現(xiàn)了Duque接口，可以被當成雙端隊列來使用，因此既可以被當成“棧”來使用，也可以當成隊列使用。

import java.util.*;

public class LinkedListTest
{
    public static void main(String[] args)
    {
        LinkedList teams = new LinkedList();
        // 將字符串元素加入隊列的尾部
        teams.offer("克利夫蘭騎士");
        // 將一個字符串元素加入棧的頂部
        teams.push("金州勇士");
        // 將字符串元素添加到隊列的頭部（相當于棧的頂部）
        teams.offerFirst("俄克拉荷馬雷霆");
        // 以List的方式（按索引訪問的方式）來遍歷集合元素
        for (int i = 0; i < teams.size() ; i++ )
        {
            System.out.println("遍歷中：" + teams.get(i));
        }
        // 訪問、并不刪除棧頂?shù)脑?        System.out.println(teams.peekFirst());
        // 訪問、并不刪除隊列的最后一個元素
        System.out.println(teams.peekLast());
        // 將棧頂?shù)脑貜棾觥皸！?        System.out.println(teams.pop());
        // 下面輸出將看到隊列中第一個元素被刪除
        System.out.println(teams);
        // 訪問、并刪除隊列的最后一個元素
        System.out.println(teams.pollLast());
        // 下面輸出：[金州勇士]
        System.out.println(teams);
    }
}

ArrayList與ArrayDeque內(nèi)部以數(shù)組的形式來保存集合中的元素，因此隨機訪問集合元素時有較好的性能；LinkedList內(nèi)部以鏈表的形式來保存集合中的元素，因此隨機訪問集合元素時性能較差，但在插入、刪除元素時性能比較出色（只需改變指針所指的地址即可）。Vector也是以數(shù)組的形式來存儲集合元素的，但因為它實現(xiàn)了線程同步功能（而且實現(xiàn)機制也不好），所以各方面性能都比較差

對于所有的內(nèi)部基于數(shù)組的集合實現(xiàn)，例如ArrayList與ArrayDeque等，使用隨機訪問的性能比使用Iterator迭代訪問的性能要好，因為隨機訪問會被映射成對數(shù)組元素的訪問

ArrayList：基于數(shù)組的線性表
LinkedList：基于鏈的線性表
Queue：隊列
Deque：雙端隊列

數(shù)組以一塊連續(xù)內(nèi)存區(qū)來保存所有的數(shù)組元素，所以數(shù)組在隨機訪問時性能最好，所有的內(nèi)部以數(shù)組為底層實現(xiàn)的集合在隨機訪問時性能都比較好；而內(nèi)部以鏈表作為底層實現(xiàn)的集合在執(zhí)行插入、刪除操作時有較好的性能。總體來說，ArrayList的性能比LinkedList的性能要好，因此大部分時候都應該考慮使用ArrayList

使用List集合的建議：

如果需要遍歷List集合元素，對于ArrayList、Vector集合，應該使用隨機訪問方法（get）來遍歷集合元素，這樣性能更好；對于LinkedList集合，則應該采用迭代器（Iterator）來遍歷集合

如果需要經(jīng)常執(zhí)行插入、刪除操作來改變包含大量數(shù)據(jù)的List集合的大小，可考慮使用LinkedList集合。使用ArrayList、Vector集合可能需要經(jīng)常重新分配內(nèi)部數(shù)組的大小，效果可能較差

如果有多個線程需要訪問List集合中的元素，開發(fā)者可考慮使用Collections將集合包裝成線程安全的集合