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

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

Queue接口的方法

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

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

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

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

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

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

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

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

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

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

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

自然排序：采用自然排序的PriorityQueue集合中的元素必須實(shí)現(xiàn)Comparator接口，而且應(yīng)該是一個(gè)類(lèi)的多個(gè)實(shí)例，否則可能導(dǎo)致ClassCastException異常

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

Deque接口是Queue接口的子接口，它代表一個(gè)雙端隊(duì)列

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

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

Iteratord descendingItrator()：返回該雙端隊(duì)列對(duì)應(yīng)的迭代器，該迭代器以逆向順序來(lái)迭代隊(duì)列中的元素

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

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

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

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

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

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

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

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

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

void push(Object e)(棧方法)：將一個(gè)元素push進(jìn)該雙端隊(duì)列所表示的棧的棧頂。相當(dāng)于addFirst(e)

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

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

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

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

Deque與Queue的方法對(duì)照?qǐng)D

Deque與Stack的方法對(duì)照?qǐng)D

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

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

//把ArrayDeque當(dāng)成棧使用

import java.util.*;

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

ArrayDeque作為隊(duì)列使用，按“先進(jìn)先出”的方式操作集合元素

import java.util.*;

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

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

import java.util.*;

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

ArrayList與ArrayDeque內(nèi)部以數(shù)組的形式來(lái)保存集合中的元素，因此隨機(jī)訪問(wèn)集合元素時(shí)有較好的性能；LinkedList內(nèi)部以鏈表的形式來(lái)保存集合中的元素，因此隨機(jī)訪問(wèn)集合元素時(shí)性能較差，但在插入、刪除元素時(shí)性能比較出色（只需改變指針?biāo)傅牡刂芳纯桑ector也是以數(shù)組的形式來(lái)存儲(chǔ)集合元素的，但因?yàn)樗鼘?shí)現(xiàn)了線程同步功能（而且實(shí)現(xiàn)機(jī)制也不好），所以各方面性能都比較差

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

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

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

使用List集合的建議：

如果需要遍歷List集合元素，對(duì)于ArrayList、Vector集合，應(yīng)該使用隨機(jī)訪問(wèn)方法（get）來(lái)遍歷集合元素，這樣性能更好；對(duì)于LinkedList集合，則應(yīng)該采用迭代器（Iterator）來(lái)遍歷集合

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

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