Introduction to the Java ArrayDeque – Java ArrayDeque的介绍

1. Overview

1.概述

In this tutorial, we’ll show how to use the Java’s ArrayDeque class – which is an implementation of Deque interface.

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

An ArrayDeque (also known as an “Array Double Ended Queue”, pronounced as “ArrayDeck”) is a special kind of a growable array that allows us to add or remove an element from both sides.

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

An ArrayDeque implementation can be used as a Stack (Last-In-First-Out) or a Queue(First-In-First-Out).

一个ArrayDeque实现可以作为Stack（后进先出）或Queue（先进先出）使用。

2. The API at a Glance

2.API一瞥

For each operation, we basically have two options.

对于每个操作，我们基本上有两个选择。

The first group consists of methods that throw exception if the operation fails. The other group returns a status or a value:

第一组包括在操作失败时抛出异常的方法。另一组则返回一个状态或一个值。

3. Using Methods

3.使用方法

Let’s look at a few simple example of how we can make use of the ArrayDeque.

让我们看看几个简单的例子，看看我们如何利用ArrayDeque。

3.1. Using ArrayDeque as a Stack

3.1.将ArrayDeque作为Stack

We’ll start with an example of how we can treat the class as a Stack – and push an element:

我们将从一个例子开始，说明我们如何把类当作一个Stack – 并推送一个元素。

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

Let’s also see how we can pop an element from the ArrayDeque – when used as a Stack:

让我们也看看我们如何从ArrayDeque中弹出一个元素–当作为一个堆栈使用时。

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

The pop method throws NoSuchElementException when a stack is empty.

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

3.2. Using ArrayDeque as a Queue

3.2.将ArrayDeque作为Queue

Let’s now start with a simple example showing how we can offer an element in an ArrayDeque – when used as a simple Queue:

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

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

And let’s see how we can poll an element from an ArrayDeque, also when used as a Queue:

让我们看看我们如何从ArrayDeque中轮询一个元素，当作为Queue使用时也是如此。

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

The poll method returns a null value if a queue is empty.

如果队列是空的，poll方法返回null值。

4. How’s ArrayDeque Implemented

4.如何实现ArrayDeque？

Under the hood, the ArrayDeque is backed by an array which doubles its size when it gets filled.

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

Initially, the array is initialized with a size of 16. It’s implemented as a double-ended queue where it maintains two pointers namely a head and a tail.

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

Let’s see this logic in action – at a high level.

让我们来看看这个逻辑的作用–在一个高层次上。

4.1. ArrayDeque as Stack

4.1.ArrayDeque作为堆栈

As can be seen, when a user adds in an element using the push method, it moves the head pointer by one.

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

When we pop an element, it sets the element at the head position as null so the element could be garbage collected, and then moves back the head pointer by one.

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

4.2. ArrayDeque as a Queue

4.2.ArrayDeque作为一个Queue

When we add in an element using the offer method, it moves the tail pointer by one.

当我们使用offer方法加入一个元素时，它的尾部指针会移动一个。

While when user polls an element, it sets the element at the head position to null so the element could be garbage collected, and then moves the head pointer.

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

4.3. Notes on ArrayDeque

4.3.关于ArrayDeque的说明

Finally, a few more notes worth understanding and remembering about this particular implementation:

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

• It’s not thread-safe
• Null elements are not accepted
• Works significantly faster than the synchronized Stack
• Is a faster queue than LinkedList due to the better locality of reference
• Most operations have amortized constant time complexity
• An Iterator returned by an ArrayDeque is fail-fast
• ArrayDeque automatically doubles the size of an array when head and tail pointer meets each other while adding an element

5. Conclusion

5.结论

In this short article, we illustrated the usage of methods in ArrayDeque.

在这篇短文中，我们说明了ArrayDeque中方法的用法。

The implementation of all these examples can be found in the GitHub project; this is a Maven-based project, so it should be easy to import and run as is.

所有这些例子的实现都可以在GitHub项目中找到；这是一个基于Maven的项目，所以应该很容易导入并按原样运行。