為什麼不推薦使用Stack

Java已不推薦使用Stack，而是推薦使用更高效的ArrayDeque

為什麼不推薦使用

• 性能低：是因為 Stack 繼承自 Vector， 而 Vector 在每個方法中都加了鎖。由於需要兼容老的項目，很難在原有的基礎上進行優化，因此 Vector 就被淘汰掉了，使用 ArrayList 和 CopyOnWriteArrayList 來代替，如果在非線程安全的情況下可以使用 ArrayList，線程安全的情況下可以使用 CopyOnWriteArrayList 。

• 破壞了原有的數據結構：棧的定義是在一端進行 push 和 pop 操作，除此之外不應該包含其他 入棧和出棧 的方法，但是 Stack 繼承自 Vector，使得 Stack 可以使用父類 Vector 公有的方法。

為什麼現在還在用

但是為什麼還有很多人在使用 Stack。總結了一下主要有兩個原因。

• JDK 官方是不推薦使用 Stack，之所以還有很多人在使用，是因為 JDK 並沒有加 deprecation 註解，只是在文檔和註釋中聲明不建議使用，但是很少有人會去關注其實現細節

• 在筆試面試需要做算法題的時候，更多關注點是在解決問題的算法邏輯思路上，並不會關注在不同語言下 Stack 實現細節，但是對於使用 Java 語言的業務開發者，不僅需要關注算法邏輯本身，也需要關注它的實現細節

為什麼推薦使用 Deque 接口替換棧

如果 JDK 不推薦使用 Stack，那應該使用什麼集合類來替換棧，一起看看官方的文檔。

正如圖中標註部分所示，棧的相關操作應該由 Deque 接口來提供，推薦使用 Deque 這種數據結構， 以及它的子類，例如 ArrayDeque。

val stack: Deque<Int> = ArrayDeque()

使用 Deque 接口來實現棧的功能有什麼好處：

• 速度比 Stack 快

這個類作為棧使用時可能比 Stack 快，作為隊列使用時可能比 LinkedList 快。因為原來的 Java 的 Stack 繼承自 Vector，而 Vector 在每個方法中都加了鎖，而 Deque 的子類 ArrayDeque 並沒有鎖的開銷。

• 屏蔽掉無關的方法

原來的 Java 的 Stack，包含了在任何位置添加或者刪除元素的方法，這些不是棧應該有的方法，所以需要屏蔽掉這些無關的方法。聲明為 Deque 接口可以解決這個問題，在接口中聲明棧需要用到的方法，無需管子類是如何是實現的，對於上層使用者來説，只可以調用和棧相關的方法。

Stack 和 ArrayDeque的 區別

Stack 常用的方法如下所示：

ArrayDeque 常用的方法如下所示：

Queue介紹

Java裏有一個叫做Stack的類，卻沒有叫做Queue的類(它是個接口名字)。當需要使用棧時，Java已不推薦使用Stack，而是推薦使用更高效的ArrayDeque；既然Queue只是一個接口，當需要使用隊列時也就首選ArrayDeque了(次選是LinkedList)。

Queue

Queue接口繼承自Collection接口，除了最基本的Collection的方法之外，它還支持額外的insertion, extraction和inspection操作。這裏有兩組格式，共6個方法，一組是拋出異常的實現；另外一組是返回值的實現(沒有則返回null)。

Deque

Deque 是"double ended queue", 表示雙向的隊列，英文讀作"deck". Deque 繼承自 Queue接口，除了支持Queue的方法之外，還支持 insert , remove 和 examine操作，由於Deque是雙向的，所以可以對隊列的頭和尾都進行操作，它同時也支持兩組格式，一組是拋出異常的實現；另外一組是返回值的實現(沒有則返回null)。共12個方法如下:

當把 Deque 當做FIFO的 queue 來使用時，元素是從 deque 的尾部添加，從頭部進行刪除的； 所以 deque 的部分方法是和 queue 是等同的。具體如下:

Deque的含義是“double ended queue”，即雙端隊列，它既可以當作棧使用，也可以當作隊列使用。下表列出了Deque與Queue相對應的接口:

下表列出了Deque與Stack對應的接口:

上面兩個表共定義了Deque的12個接口。添加，刪除，取值都有兩套接口，它們功能相同，區別是對失敗情況的處理不同。一套接口遇到失敗就會拋出異常，另一套遇到失敗會返回特殊值( false 或 null )。除非某種實現對容量有限制，大多數情況下，添加操作是不會失敗的。雖然Deque的接口有12個之多，但無非就是對容器的兩端進行操作，或添加，或刪除，或查看。

ArrayDeque和LinkedList是Deque的兩個通用實現，由於官方更推薦使用AarryDeque用作棧和隊列，加之上一篇已經講解過LinkedList，本文將着重講解ArrayDeque的具體實現

從名字可以看出ArrayDeque底層通過數組實現，為了滿足可以同時在數組兩端插入或刪除元素的需求，該數組還必須是循環的，即循環數組(circular array)，也就是説數組的任何一點都可能被看作起點或者終點。ArrayDeque是非線程安全的(not thread-safe)，當多個線程同時使用的時候，需要程序員手動同步；另外，該容器不允許放入 null 元素。

上圖中我們看到， head 指向首端第一個有效元素， tail 指向尾端第一個可以插入元素的空位。因為是循環數組，所以 head 不一定總等於0， tail 也不一定總是比 head 大。

方法剖析

addFirst()

addFirst(E e)的作用是在Deque的首端插入元素，也就是在head的前面插入元素，在空間足夠且下標沒有越界的情況下，只需要將elements[--head] = e即可。

實際需要考慮:

1. 空間是否夠用
2. 下標是否越界的問題

上圖中，如果head為0之後接着調用addFirst()，雖然空餘空間還夠用，但head為-1，下標越界了。

//addFirst(E e)
public void addFirst(E e) {
    if (e == null)//不允許放入null
        throw new NullPointerException();
    elements[head = (head - 1) & (elements.length - 1)] = e;//2.下標是否越界
    if (head == tail)//1.空間是否夠用
        doubleCapacity();//擴容
}

上述代碼可以看到， 空間問題是在插入之後解決的；首先，因為tail總是指向下一個可插入的空位，也就意味着elements數組至少有一個空位，所以插入元素的時候不用考慮空間問題。

下標越界的處理解決起來非常簡單，head = (head - 1) & (elements.length - 1)就可以了，這段代碼相當於取餘，同時解決了head為負值的情況。因為elements.length必需是2的指數倍，elements - 1就是二進制低位全1，跟head - 1相與之後就起到了取模的作用，如果head - 1為負數(其實只可能是-1)，則相當於對其取相對於elements.length的補碼。

計算機裏數值都是用補碼錶示的，如果是8位的，-1就是1111 1111，而 (elements.length - 1) 也是 1111 1111，因此兩者相與也就是(elements.length - 1)；

head = (head - 1) & (elements.length - 1) 最後再讓算出的位置賦值給head，因此其實這段代碼就是讓head再從後往前賦值

擴容函數doubleCapacity()，其邏輯是申請一個更大的數組(原數組的兩倍)，然後將原數組複製過去。過程如下圖所示:

圖中可以看到，複製分兩次進行，第一次複製head右邊的元素，第二次複製head左邊的元素。

//doubleCapacity()
private void doubleCapacity() {
    assert head == tail;
    int p = head;
    int n = elements.length;
    int r = n - p; // head右邊元素的個數
    int newCapacity = n << 1;//原空間的2倍
    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 = (E[])a;
    head = 0;
    tail = n;
}

addLast()

addLast(E e)的作用是在Deque的尾端插入元素，也就是在tail的位置插入元素，由於tail總是指向下一個可以插入的空位，因此只需要elements[tail] = e;即可。插入完成後再檢查空間，如果空間已經用光，則調用doubleCapacity()進行擴容。

public void addLast(E e) {
    if (e == null)//不允許放入null
        throw new NullPointerException();
    elements[tail] = e;//賦值
    if ( (tail = (tail + 1) & (elements.length - 1)) == head)//下標越界處理
        doubleCapacity();//擴容
}

pollFirst()

pollFirst()的作用是刪除並返回Deque首端元素，也即是head位置處的元素。如果容器不空，只需要直接返回elements[head]即可，當然還需要處理下標的問題。由於ArrayDeque中不允許放入null，當elements[head] == null時，意味着容器為空。

public E pollFirst() {
    int h = head;
    E result = elements[head];
    if (result == null)//null值意味着deque為空
        return null;
    elements[h] = null;//let GC work
    head = (head + 1) & (elements.length - 1);//下標越界處理
    return result;
}

pollLast()

pollLast()的作用是刪除並返回Deque尾端元素，也即是tail位置前面的那個元素。

public E pollLast() {
    int t = (tail - 1) & (elements.length - 1);//tail的上一個位置是最後一個元素
    E result = elements[t];
    if (result == null)//null值意味着deque為空
        return null;
    elements[t] = null;//let GC work
    tail = t;
    return result;
}

peekFirst()

peekFirst()的作用是返回但不刪除Deque首端元素，也即是head位置處的元素，直接返回elements[head]即可。

public E peekFirst() {
    return elements[head]; // elements[head] is null if deque empty
}

peekLast()

peekLast()的作用是返回但不刪除Deque尾端元素，也即是tail位置前面的那個元素。

public E peekLast() {
    return elements[(tail - 1) & (elements.length - 1)];
}