談談集合.Queue

Java中集合的主要作用就是裝盛其他數據和實現常見的數據結構。所以當我們要用到“棧”、“隊列”、“鏈表”和“數組”等常見的數據結構時就應該想到可以直接使用JDK給我們提供的集合框架。 比如說當我們想用到隊列時就應該想到使用LinkedList和ArrayDeque 。本篇博客將介紹Collection框架中的Queue。

Queue接口繼承了Collection接口，所以Collection的所有方法Queue的實現類中都包含，同時還有一個子接口Dqueue，表示雙端隊列。對於Queue我們主要掌握ArrayDeque和LinkedList，瞭解 PriorityQueue (優先級隊列)。

1. 接口介紹

Queue也是Java集合框架中定義的一種接口，直接繼承自 Collection 接口。除了基本的 Collection 接口規定測操作外，Queue 接口還定義一組針對隊列的特殊操作。通常來說，Queue是按照先進先出(FIFO)的方式來管理其中的元素的，但是優先隊列是一個例外。

Deque接口繼承自Queue接口，但Deque支持同時從兩端添加或移除元素，因此又被成為雙端隊列。鑑於此，Deque接口的實現可以被當作FIFO隊列使用，也可以當作LIFO隊列（棧）來使用。官方也是推薦使用 Deque的實現來替代Stack。Deque的主要實現類有ArrayDeque和LinkedList。

ArrayDeque是Deque接口的一種具體實現，是依賴於可變數組來實現的。ArrayDeque沒有容量限制，可根據需求自動進行擴容。ArrayDeque不支持值為null的元素。

LinkedList的具體特性已經在之前的博客中介紹過了，這邊不再重新介紹了。

1.1 Queue接口概覽

Queue可以被當做一個隊列來使用，實現FIFO操作，主要提供下面的操作

<code>public interface Queue extends Collection {
    //向隊列尾部插入一個元素，並返回true
    //如果隊列已滿，拋出IllegalStateException異常
    boolean add(E e);

    //向隊列尾部插入一個元素，並返回true
    //如果隊列已滿，返回false
    boolean offer(E e);

    //取出隊列頭部的元素，並從隊列中移除
    //隊列為空，拋出NoSuchElementException異常
    E remove();

    //取出隊列頭部的元素，並從隊列中移除
    //隊列為空，返回null
    E poll();

    //取出隊列頭部的元素，但並不移除
    //如果隊列為空，拋出NoSuchElementException異常
    E element();

    //取出隊列頭部的元素，但並不移除
    //隊列為空，返回null
    E peek();
}/<code>

1.2 Deque接口

Deque接口是一個雙端隊列，可以對隊列的頭尾進行操作，所以也可以當做棧來使用。

下面的表格列舉了Queue和Deque接口的相對應方法

Queue方法Deque方法add(e)addLast(e)offer(e)offerLast(e)remove()removeFirst()poll()pollFirst()element()getFirst()peek()peekFirst()

Deque還有一個重要的功能是可以當做棧來使用

Stack方法Deque方法push(e)addFirst(e)pop()removeFirst()peek()peekFirst()

2. ArrayDeque

ArrayDeque是Deque基於數組的實現。

2.1 ArrayDeque的成員變量

<code>//數組存儲元素
    transient Object[] elements;
    //頭部元素索引
    transient int head;
    //尾部元素索引
    transient int tail;
    //最小容量
    private static final int MIN_INITIAL_CAPACITY = 8;/<code>

ArrayDeque底層使用數組存儲元素，同時還使用head和tail來表示索引，但注意tail不是尾部元素的索引，而是尾部元素的下一位，即下一個將要被加入的元素的索引。

2.2 初始化

<code>public ArrayDeque() { 

    elements = new Object[16];
}

public ArrayDeque(int numElements) {
    allocateElements(numElements);
}

public ArrayDeque(Collection extends E> c) {
    allocateElements(c.size());
    addAll(c);
}

private void allocateElements(int numElements) {
    int initialCapacity = MIN_INITIAL_CAPACITY;
    // Find the best power of two to hold elements.
    // Tests "<=" because arrays aren't kept full.
    if (numElements >= initialCapacity) {
        initialCapacity = numElements;
        initialCapacity |= (initialCapacity >>>  1);
        initialCapacity |= (initialCapacity >>>  2);
        initialCapacity |= (initialCapacity >>>  4);
        initialCapacity |= (initialCapacity >>>  8);
        initialCapacity |= (initialCapacity >>> 16);
        initialCapacity++;

        if (initialCapacity < 0)   // Too many elements, must back off
            initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
    }
    elements = new Object[initialCapacity];
}/<code>

這邊講下private void allocateElements(int numElements)這個方法。ArrayDeque的初始化容量必須是2^n。所以你傳的初始化容量如果是10，那麼實際申請的數組容量是16，如果申請的容量是33，那麼實際的容量是62。如果申請的容量是62,那麼實際申請的容量是128。

2.3 add方法

<code>public void addFirst(E e) {
    if (e == null)
        throw new NullPointerException();
    elements[head = (head - 1) & (elements.length - 1)] = e;
    if (head == tail)
        doubleCapacity();
} 


public void addLast(E e) {
    if (e == null)
        throw new NullPointerException();
    //tail中保存的是即將加入末尾的元素的索引
    elements[tail] = e;
    //tail向後移動一位
    if ( (tail = (tail + 1) & (elements.length - 1)) == head)
        //tail和head相遇，空間用盡，需要擴容
        doubleCapacity();
}/<code>

在存儲的過程中，這裡有個有趣的算法，就是tail的計算公式(tail = (tail + 1) & (elements.length - 1))，注意這裡的存儲採用的是環形隊列的形式，也就是當tail到達容量最後一個的時候，tail就為等於0，否則tail的值tail+1。

head也採用了類似的方式，每次在頭部添加元素後，head都會指向最新被添加進去的那個元素所在的位置。當head小於0時也會採取環的形式存元素，比如head已經指向位置0，又向隊列中頭部添加一個元素後，head會變成length-1。

關於head和tail，需要主要的是head永遠指向第一個元素的索引位置，tail永遠指向尾部位置（這個位置上暫時還沒有元素，如果在尾部插入元素，則在這個位置上插入）

2.4 擴容機制

<code>private void doubleCapacity() {
    assert head == tail; //擴容時頭部索引和尾部索引肯定相等
    int p = head;
    int n = elements.length;
    //頭部索引到數組末端(length-1處)共有多少元素
    int r = n - p; // number of elements to the right of p
    //容量翻倍
    int newCapacity = n << 1;
    //容量過大，溢出了
    if (newCapacity < 0)
        throw new IllegalStateException("Sorry, deque too big");
    //分配新空間
    Object[] a = new Object[newCapacity];
    //複製頭部索引到數組末端的元素到新數組的頭部
    System.arraycopy(elements, p, a, 0, r);
    //複製其餘元素
    System.arraycopy(elements, 0, a, r, p);
    elements = a;
    //重置頭尾索引
    head = 0;
    tail = n;
}/<code>

下圖是擴容的示意圖

3. 總結

ArrayDeque是Deque 接口的一種具體實現，是依賴於可變數組來實現的。ArrayDeque 沒有容量限制，可根據需求自動進行擴容。ArrayDeque 可以作為棧來使用，效率要高於Stack；ArrayDeque 也可以作為隊列來使用，效率相較於基於雙向鏈表的LinkedList也要更好一些。

所以我們程序中如果要使用到“隊列”和“棧”這種數據結構，我們要首先想到LinkedList和ArrayDeque。個人認為作為隊列和棧來使用的話，兩者性能相差不大，但是ArrayDeque需要擴容，還需要申請連續的內存空間，所以個人更推薦使用LinkedList，不知道我的理解對不對。

閱讀更多 sandag 的文章

關鍵字: 數據結構 接口 談談