Java ArrayDeque

在本教程中，我们通过示例学习 ArrayDeque 类及其用法。此外，我们将 ArrayDeque 作为堆栈使用。

ArrayDeque 类使用数组实现了队列、双端队列、和栈的数据结构。当 ArrayDeque 作为队列使用的时候，比 LinkedList 性能好；当作为栈使用的时候，比 Stack 性能好。

ArrayDeque 类实现 Deque 接口，而 Deque 接口继承了 Queue 接口。

Java 中的 ArrayDeque 实现了两个接口：Queue 和 Deque

创建 ArrayDeque

我们首先导入 java.util.ArrayDeque 类，然后按照如下的方式构造 ArrayDeque 对象：

ArrayDeque<Type> animal = new ArrayDeque<>();

这里， Type 表示元素的数据类型。例如，

ArrayDeque<String> animals = new ArrayDeque<>();
ArrayDeque<Integer> age = new ArrayDeque<>();

ArrayDeque 的方法

ArrayDeque 类完全实现了 Queue 接口和 Deque 接口的所有方法。

插入元素到双端队列

使用 add()、addFirst() 和 addLast() 添加元素
- add() - 在队列的末尾插入指定的元素
- addFirst() - 在双端队列的开头插入指定的元素
- addLast() - 在双端队列的末尾插入指定的（等价于 add() ）
注： add()，addFirst() 和 addLast() 这 3 个方法，如果插入成功返回 true, 如果队列已满，都会抛出 IllegalStateException 异常。

例如，
```
import java.util.ArrayDeque;

public class Main {
  public static void main(String[] args) {
    ArrayDeque<String> animals = new ArrayDeque<>();

    animals.add("Dog");
    animals.addFirst("Cat");
    animals.addLast("Horse");

    System.out.println("ArrayDeque: " + animals);
  }
}
```
输出
```
ArrayDeque: [Cat, Dog, Horse]
```

使用 offer()、offerFirst() 和 offerLast() 插入元素

offer() - 在队列的末尾插入指定的元素
offerFirst() - 在双端队列的开头插入指定的元素
offerLast() - 在双端队列的末尾插入指定的元素

注： offer()，offerFirst() 和 offerLast() 如果插入成功返回 true，如果队列已满返回 false 。

例如，

import java.util.ArrayDeque;

public class Main {
  public static void main(String[] args) {
    ArrayDeque<String> animals = new ArrayDeque<>();

    animals.offer("Dog");
    animals.offerFirst("Cat");
    animals.offerLast("Horse");

    System.out.println("ArrayDeque: " + animals);
  }
}

输出

ArrayDeque: [Cat, Dog, Horse]

注意： 如果双端队列已满, add() 方法将抛出异常, offer() 方法返回 false。

访问 ArrayDeque 元素

使用 getFirst() 和 getLast() 访问元素

getFirst() - 返回双端队列的第一个元素
getLast() - 返回双端队列的最后一个元素

**注：**如果双端队列为空， getFirst() 并 getLast() 抛出 NoSuchElementException 。

例如，

import java.util.ArrayDeque;

public class Main {
  public static void main(String[] args) {
    ArrayDeque<String> animals = new ArrayDeque<>();
    animals.add("Dog");
    animals.add("Cat");
    animals.add("Horse");
    System.out.println("ArrayDeque: " + animals);

    // 队头元素
    String firstElement = animals.getFirst();
    System.out.println("First Element: " + firstElement);

    // 队尾元素
    String lastElement = animals.getLast();
    System.out.println("Last Element: " + lastElement);
  }
}

输出

ArrayDeque: [Dog, Cat, Horse]
First Element: Dog
Last Element: Horse

使用 peek()、peekFirst() 和 peekLast() 方法访问元素

peek() - 返回队列的第一个元素，如果队列为空返回 null。
peekFirst() - 返回双端队列的第一个元素，如果队列为空返回 null。（等价于 peek() ）
peekLast() - 返回双端队列的最后一个元素，如果队列为空返回 null。

例如，

import java.util.ArrayDeque;

public class Main {
  public static void main(String[] args) {
    ArrayDeque<String> animals = new ArrayDeque<>();
    animals.add("Dog");
    animals.add("Cat");
    animals.add("Horse");
    System.out.println("ArrayDeque: " + animals);

    // peek() 返回队头元素
    String element = animals.peek();
    System.out.println("Head Element: " + element);

    // peekFirst() 返回队头元素
    String firstElement = animals.peekFirst();
    System.out.println("First Element: " + firstElement);

    // peekLast() 返回队尾元素
    String lastElement = animals.peekLast();
    System.out.println("Last Element: " + lastElement);
  }
}

输出

ArrayDeque: [Dog, Cat, Horse]
Head Element: Dog
First Element: Dog
Last Element: Horse

删除 ArrayDeque 元素

使用 remove()、removeFirst()、removeLast() 方法删除元素

remove() - 删除并返回双端队列的第一个元素
remove(element) - 删除队列中第一个匹配的指定的元素，成功返回 true；找不到元素抛出异常。
removeFirst() - 删除并返回双端队列的第一个元素（等价于 remove() ）
removeLast() - 删除并返回双端队列的最后一个元素

**注意：**如果队列为空 remove() ， removeFirst() 和 removeLast() 方法会抛出异常。

例如，

import java.util.ArrayDeque;

public class Main {
  public static void main(String[] args) {
    ArrayDeque<String> animals = new ArrayDeque<>();
    animals.add("Dog");
    animals.add("Cat");
    animals.add("Cow");
    animals.add("Horse");
    System.out.println("ArrayDeque: " + animals);

    String element = animals.remove();
    System.out.println("Removed Element: " + element);

    System.out.println("Now ArrayDeque: " + animals);

    String firstElement = animals.removeFirst();
    System.out.println("Removed First Element: " + firstElement);

    String lastElement = animals.removeLast();
    System.out.println("Removed Last Element: " + lastElement);

    System.out.println("Now ArrayDeque: " + animals);
  }
}

输出

ArrayDeque: [Dog, Cat, Cow, Horse]
Removed Element: Dog
Now ArrayDeque: [Cat, Cow, Horse]
Removed First Element: Cat
Removed Last Element: Horse
Now ArrayDeque: [Cow]

使用 poll()、pollFirst() 和 pollLast() 方法删除元素

poll() - 返回并删除双端队列的第一个元素
pollFirst() - 返回并删除双端队列的第一个元素（等价于 poll() ）
pollLast() - 返回并删除双端队列的最后一个元素

**注：**如果双端队列为空， poll() ， pollFirst() 和 pollLast() 方法返回 null。

例如，

import java.util.ArrayDeque;

public class Main {
  public static void main(String[] args) {
    ArrayDeque<String> animals = new ArrayDeque<>();
    animals.add("Dog");
    animals.add("Cat");
    animals.add("Cow");
    animals.add("Horse");
    System.out.println("ArrayDeque: " + animals);

    String element = animals.poll();
    System.out.println("Removed Element: " + element);
    System.out.println("ArrayDeque: " + animals);

    String firstElement = animals.pollFirst();
    System.out.println("Removed First Element: " + firstElement);

    String lastElement = animals.pollLast();
    System.out.println("Removed Last Element: " + lastElement);

    System.out.println("ArrayDeque: " + animals);
  }
}

输出

ArrayDeque: [Dog, Cat, Cow, Horse]
Removed Element: Dog
ArrayDeque: [Cat, Cow, Horse]
Removed First Element: Cat
Removed Last Element: Horse
ArrayDeque: [Cow]

使用 clear() 方法清空队列

clear() 方法从双端队列中删除所有元素。例如，

import java.util.ArrayDeque;

public class Main {
  public static void main(String[] args) {
    ArrayDeque<String> animals = new ArrayDeque<>();
    animals.add("Dog");
    animals.add("Cat");
    animals.add("Horse");
    System.out.println("ArrayDeque: " + animals);

    animals.clear();
    System.out.println("New ArrayDeque: " + animals);
  }
}

输出

ArrayDeque: [Dog, Cat, Horse]
New ArrayDeque: []

迭代 ArrayDeque

iterator() - 返回可用于迭代双端队列的迭代器
descendingIterator() - 返回一个迭代器，可用于以相反的顺序迭代双端队列

为了使用这些方法，我们必须导入 java.util.Iterator 包。例如，

import java.util.ArrayDeque;
import java.util.Iterator;

public class Main {
  public static void main(String[] args) {
    ArrayDeque<String> animals = new ArrayDeque<>();
    animals.add("Dog");
    animals.add("Cat");
    animals.add("Horse");

    System.out.print("ArrayDeque 正向: ");

    // 正向迭代
    Iterator<String> iterate = animals.iterator();
    while (iterate.hasNext()) {
      System.out.print(iterate.next());
      System.out.print(", ");
    }

    System.out.print("\nArrayDeque 反向: ");
    // 反向迭代
    Iterator<String> desIterate = animals.descendingIterator();
    while (desIterate.hasNext()) {
      System.out.print(desIterate.next());
      System.out.print(", ");
    }
  }
}

输出

ArrayDeque 正向: Dog, Cat, Horse,
ArrayDeque 反向: Horse, Cat, Dog,

其他方法

方法	说明
`element()`	从双端队列的头部返回一个元素。
`contains(element)`	在双端队列中搜索指定元素。如果找到该元素，则返回 `true` ，否则返回 `false` 。
`size()`	返回双端队列的长度。
`toArray()`	将双端队列转换为数组并返回它。
`clone()`	创建双端队列的副本并返回它。

使用 ArrayDeque 作为堆栈

Java 集合框架中已有 Stack 类作为堆栈的实现，但是现在已经不建议使用。而 ArrayDeque 也实现了堆栈的操作，并且比 Stack 效率更高。

ArrayDeque 提供了以下方法用于堆栈操作：

push() - 向栈顶添加一个元素
peek() - 从栈顶返回一个元素
pop() - 从栈顶返回并删除一个元素

例如，

import java.util.ArrayDeque;

public class Main {
  public static void main(String[] args) {
    ArrayDeque<String> stack = new ArrayDeque<>();

    // 添加元素到堆栈
    stack.push("Dog");
    stack.push("Cat");
    stack.push("Horse");
    System.out.println("Stack: " + stack);

    // 访问栈顶元素
    String element = stack.peek();
    System.out.println("Accessed Element: " + element);

    // 删除栈顶元素
    String remElement = stack.pop();
    System.out.println("Removed element: " + remElement);
  }
}

输出

Stack: [Horse, Cat, Dog]
Accessed Element: Horse
Removed element: Horse

ArrayDeque 与 LinkedList

在 Java 集合框架中， ArrayDeque 和 LinkedList 都实现了 Deque 接口。但是，它们之间存在一些差异。

LinkedList 底层使用双向链表作为数据结构， ArrayDeque 底层使用数组作为数据结构。
LinkedList 支持 null 元素， ArrayDeque 不支持 null 元素。
LinkedList 中的每个节点都包含指向其他节点的链接，这导致了 LinkedList 比 ArrayDeque 占用更多的空间。
作为队列或双端队列数据结构， ArrayDeque 比 LinkedList 更快。