1兜看、概覽

本篇踏揣，我們將介紹ArrayDeque的使用方法-ArrayDeque是Deque的一個實現(xiàn)靶溜。ArrayDeque俗稱數(shù)組雙端隊列，是一種允許我們從倆端進行存取操作的可擴容數(shù)組夜焦。

ArrayDeque既可以作為Stack使用(Last-In-First-Out) 又可以作為Queue使用(First-In-First-Out)壳澳。

2、API

針對于每個操作茫经，我們基本上都有倆個可選擇的API巷波，第一組API方法在操作失敗時，會拋出異常卸伞。另一組則會返回一個狀態(tài)或一個值抹镊。

3、使用方法

下面荤傲，我們將通過幾個示例來看一下ArrayDeque的用法垮耳。

3.1 ArrayDeque作為棧使用

接下來，我們把ArrayDeque當做Stack用-并向其中push一個元素

public static void whenPush_addsAtFirst(){

        Deque<String> stack = new ArrayDeque<>();
        stack.push("first");
        stack.push("second");

        System.out.println(stack.getFirst());

}

當用作Stack時遂黍，我們?nèi)绾螐闹衟op出一個元素：

public static void whenPop_removesLast(){

       Deque<String> stack = new ArrayDeque<>();

       stack.push("first");
       stack.push("second");

       System.out.println(stack.pop());
}

當stack為空時终佛，pop方法會拋出NoSuchElementException異常。

3.2 ArrayDeque作為隊列使用

接下來妓湘，我們看把ArrayDeque當做Queue使用時查蓉，如何向其中添加一個元素:

public static void whenOffer_addsAtLast(){

        Deque<String>  queue = new ArrayDeque<>();
        queue.offer("first");
        queue.offer("second");

        System.out.println(queue.getLast());
    }

當把ArrayDeque作為Queue使用時，如何從隊列中獲取元素：

public static void whenPoll_removesFirst(){

        Deque<String>  queue = new ArrayDeque<>();
        queue.offer("first");
        queue.offer("second");

        System.out.println(queue.poll());
    }

若隊列為空的話榜贴，poll方法將返回null值。

4、ArrayDeque的實現(xiàn)原理

原理

ArrayDeque的底層是由一個數(shù)組來實現(xiàn)的唬党，這個數(shù)組會在其塞滿的時候鹃共，把容量擴大一倍。該數(shù)組初始化大小為16驶拱，它通過維護倆個指針：head霜浴、tail實現(xiàn)了雙端隊列。

4.1 ArrayDeque作為棧的實現(xiàn)原理

作為棧

正如圖上所示蓝纲，當用戶使用push方法向其中添加元素時阴孟，它會把head頭指針向前移動一位。
當我們從棧中彈出一個元素時税迷，它會把head位置處的元素設置為null(這樣的話永丝，此元素就可以被垃圾回收)，并且把head指針向后移動一位箭养。

4.2 ArrayDeque作為隊列的實現(xiàn)原理

作為隊列

如上圖所示慕嚷，使用offer向隊列中添加元素，tail尾指針會向后移動一位毕泌。而當用戶從隊列中拉取一個元素時喝检，它會把head位置處的元素設置為null，并且把head指針向后移動一位撼泛。

4.3 ArrayDeque的注意點

最后挠说，有幾個注意點我們需要記住：

. ArrayDeque不是線程安全的

. ArrayDeque不能存儲Null值

. 相較于同步棧來說愿题，ArrayDeque的速度相當快

. ArrayDeque比LinkedList速度更快

. 大多數(shù)操作的時間復雜度都是常數(shù)

. ArrayDeque的Iterator是fail-fast的

. 當添加元素時损俭，如果head指針和tail指針指向同一位置，ArrayDeque會自動把容量擴大一倍

5抠忘、總結(jié)

全部代碼如下：

public class ArrayDequeTests {


    public static void main(String[] args) throws Exception{

        //whenPush_addsAtFirst();
        //whenPop_removesLast();
        //whenOffer_addsAtLast();
        whenPoll_removesFirst();
    }

    public static void whenPush_addsAtFirst(){

        Deque<String> stack = new ArrayDeque<>();
        stack.push("first");
        stack.push("second");

        System.out.println(stack.getFirst());

    }


    public static void whenPop_removesLast(){

        Deque<String> stack = new ArrayDeque<>();

        stack.push("first");
        stack.push("second");

        System.out.println(stack.pop());
    }


    public static void whenOffer_addsAtLast(){

        Deque<String>  queue = new ArrayDeque<>();
        queue.offer("first");
        queue.offer("second");

        System.out.println(queue.getLast());
    }


    public static void whenPoll_removesFirst(){

        Deque<String>  queue = new ArrayDeque<>();
        queue.offer("first");
        queue.offer("second");

        System.out.println(queue.poll());
    }


}

以上就是關(guān)于ArrayDeque的簡單介紹撩炊。

6、參考文獻

1. oracle-javase7-apidoc

2. baeldung-java-ArrayDeque

3. stackoverflow-why-is-arraydeque-better-than-linkedlist

4. java-collections-overview