1 如何理解“雙端隊列”

Deque 全稱為double ended queue，即雙向隊列，相對于隊列它提供了更強(qiáng)大的功能.它允許在隊列兩側(cè)插入或刪除元素。因此deque實(shí)現(xiàn)不僅僅能能作為隊列【先進(jìn)先出FIFO(first in first out)】使用，還能作為棧【后入先出LIFO(last in first out)使用】。

2 Java中雙端隊列“接口”

Deque中定義的方法主要分為四部分，第一部分就如Deque定義所言，提供兩側(cè)插入或刪除的方法。第二部分是繼承自Queue的實(shí)現(xiàn)。第三部分表示如果要基于此實(shí)現(xiàn)一個Stack，需要實(shí)現(xiàn)的方法。最后一部分是繼承自Collection的方法

提供兩側(cè)插入或刪除的方法

//在隊首添加元素
void addFirst(E e);
//在隊首添加元素
boolean offerFirst(E e);

//在隊尾添加元素
void addLast(E e);
boolean offerLast(E e);

//刪除隊首元素
E removeFirst();
E pollFirst();

//刪除隊尾元素
E removeLast();
E pollLast();

//獲取隊首元素
E getFirst();
E peekFirst();

//獲取隊尾元素
E getLast();
E peekLast();

//刪除隊列中第一個發(fā)現(xiàn)o元素
boolean removeFirstOccurrence(Object o);
//刪除隊列中最后一個發(fā)現(xiàn)o元素
boolean removeLastOccurrence(Object o);

和隊列一樣這里添加、刪除、查詢這些個操作都提供了兩種形式。在操作失敗時直接拋出異常，而另一種則返回一個特殊的值

image

繼承自Queue的方法

Deque 繼承了父接口Queue所有方法，并對所有接口方法都可以通過自身定義兩側(cè)插入或刪除的方法來實(shí)現(xiàn).其對應(yīng)關(guān)系如下：

image

對應(yīng)源碼

    public boolean add(E e) {
        addLast(e);
        return true;
    }

實(shí)現(xiàn)Stack接口

雖然Deque提供的addFirst()，removeFirst()方法足以實(shí)現(xiàn)Stack功能，但Deque還是提供了針對Stack方法操作名稱相關(guān)的方法：

//與addFirst()等價
void push(E e);

//與removeFirst()等價
E pop();

繼承于Collection的方法

//順序是從隊首到隊尾
Iterator<E> iterator();

//順序是從隊尾到隊首
Iterator<E> descendingIterator();