Java中ArrayDeque简介

1. 概述

在本教程中，我们将展示如何使用 Java 的ArrayDeque类——它是Deque接口的一个实现。

ArrayDeque（也称为“Array Double Ended Queue”，发音为“ArrayDeck”）是一种特殊的可增长数组，它允许我们从两侧添加或删除元素。

ArrayDeque实现可以用作stack（后进先出）或Queue（先进先出）。

2. API 概览

对于每个操作，我们基本上有两种选择。 第一组由在操作失败时抛出异常的方法组成。另一组返回状态或值：

3. 使用方法

让我们看一些如何使用ArrayDeque的简单示例。

3.1.使用ArrayDeque作为stack

我们将从一个如何将类视为stack的示例开始- 并推送一个元素：

@Test
public void whenPush_addsAtFirst() {
    Deque<String> stack = new ArrayDeque<>();
    stack.push("first");
    stack.push("second");
 
    assertEquals("second", stack.getFirst());
}

让我们也看看我们如何从ArrayDeque中弹出一个元素——当用作堆栈时：

@Test
public void whenPop_removesLast() {
    Deque<String> stack = new ArrayDeque<>();
    stack.push("first");
    stack.push("second");
 
    assertEquals("second", stack.pop());
}

当堆栈为空时， pop方法会抛出NoSuchElementException。

3.2. 使用ArrayDeque作为Queue

现在让我们从一个简单的例子开始，展示我们如何在ArrayDeque中提供一个元素——当用作一个简单的Queue时：

@Test
public void whenOffer_addsAtLast() {
    Deque<String> queue = new ArrayDeque<>();
    queue.offer("first");
    queue.offer("second");
 
    assertEquals("second", queue.getLast());
}

让我们看看我们如何从ArrayDeque中轮询一个元素，也可以在用作Queue时：

@Test
public void whenPoll_removesFirst() {
    Deque<String> queue = new ArrayDeque<>();
    queue.offer("first");
    queue.offer("second");
 
    assertEquals("first", queue.poll());
}

如果队列为空，则poll方法返回null。

4. ArrayDeque是如何实现的

在引擎盖下，ArrayDeque由一个数组支持，当它被填充时，它的大小会翻倍。

最初，数组初始化为 16 的大小。它被实现为一个双端队列，其中维护两个指针，即头和尾。

让我们在高层次上看看这个逻辑。

4.1. ArrayDeque作为堆栈

可以看出，当用户使用push方法添加元素时，它会将头指针移动一个。

当我们弹出一个元素时，它会将头部位置的元素设置为null，这样该元素就可以被垃圾回收，然后将头部指针向后移动一个。

4.2. ArrayDeque作为队列

当我们使用offer方法

添加一个元素时，它会将尾指针移动一位。

而当用户轮询一个元素时，它将位于头位置的元素设置为空，以便该元素可以被垃圾收集，然后移动头指针。

4.3. ArrayDeque的注意事项

最后，关于这个特定的实现，还有一些值得理解和记住的注意事项：

• 它不是线程安全的
• 不接受空元素
• 工作速度明显快于同步Stack
• 由于引用的局部性更好，是比LinkedList更快的队列
• 大多数操作都摊销了常数时间复杂度
• ArrayDeque返回的Iterator是快速失败的
• ArrayDeque在添加元素时头尾指针相遇时自动将数组大小加倍