跳到主要内容

Java ArrayDeque

提示
  1. ArrayDeque 简介：ArrayDeque 是 Java 中的数组实现的队列和双端队列数据结构，实现了 Queue 和 Deque 接口。
  2. 创建和使用 ArrayDeque：通过 ArrayDeque<Type> name = new ArrayDeque<>(); 创建，支持在队列首部和尾部添加（addFirst(), addLast()）和移除（removeFirst(), removeLast()）元素。
  3. 特性和应用：ArrayDeque 不支持 null 元素，适用于实现栈（LIFO）结构，比 LinkedList 更高效，提供了方法如 peek(), poll(), clear() 来访问、修改和遍历队列。

在 Java 中，我们可以使用 ArrayDeque 类使用数组实现队列和双端队列数据结构。

ArrayDeque 实现的接口​

ArrayDeque 类实现了这两个接口：

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

创建 ArrayDeque​

为了创建一个数组双端队列，我们必须导入 java.util.ArrayDeque 包。

下面是我们如何在 Java 中创建一个数组双端队列的方法：

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

这里的 Type 表示数组双端队列的类型。例如，

// 创建 String 类型的 ArrayDeque
ArrayDeque<String> animals = new ArrayDeque<>();

// 创建 Integer 类型的 ArrayDeque
ArrayDeque<Integer> age = new ArrayDeque<>();

ArrayDeque 的方法​

ArrayDeque 类为 Queue 和 Deque 接口中的所有方法提供了实现。

向双端队列插入元素​

1. 使用 add(), addFirst() 和 addLast() 添加元素

  • add() - 在数组双端队列的末尾插入指定元素
  • addFirst() - 在数组双端队列的开头插入指定元素
  • addLast() - 在数组双端队列的末尾插入指定元素（等同于 add()）

注意： 如果数组双端队列已满，这些方法 add(), addFirst() 和 addLast() 会抛出 IllegalStateException。

例如，

import java.util.ArrayDeque;

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

        // 使用 add()
        animals.add("Dog");

        // 使用 addFirst()
        animals.addFirst("Cat");

        // 使用 addLast()
        animals.addLast("Horse");
        System.out.println("ArrayDeque: " + animals);
    }
}

输出

ArrayDeque: [Cat, Dog, Horse]

2. 使用 offer(), offerFirst() 和 offerLast() 插入元素

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

注意： offer(), offerFirst() 和 offerLast() 如果元素成功插入，则返回 true；如果数组双端队列已满，这些方法返回 false。

例如，

import java.util.ArrayDeque;

class Main {
    public static void main(String[] args) {
        ArrayDeque<String> animals= new ArrayDeque<>();
        // 使用 offer()
        animals.offer("Dog");

        // 使用 offerFirst()
        animals.offerFirst("Cat");

        // 使用 offerLast()
        animals.offerLast("Horse");
        System.out.println("ArrayDeque: " + animals);
    }
}

输出

ArrayDeque: [Cat, Dog, Horse]

注意： 如果数组双端队列已满

  • add() 方法将抛出异常
  • offer() 方法返回 false

访问 ArrayDeque 元素​

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

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

注意： 如果数组双端队列为空，getFirst() 和 getLast() 抛出 NoSuchElementException。

例如，

import java.util.ArrayDeque;

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("第一个元素: " + firstElement);

        // 获取最后一个元素
        String lastElement = animals.getLast();
        System.out.println("最后一个元素: " + lastElement);
    }
}

输出

ArrayDeque: [Dog, Cat, Horse]
第一个元素: Dog
最后一个元素: Horse

2. 使用 peek(), peekFirst() 和 peekLast() 方法访问元素

  • peek() - 返回数组双端队列的第一个元素
  • peekFirst() - 返回数组双端队列的第一个元素（等同于 peek()）
  • peekLast() - 返回数组双端队列的最后一个元素

例如，

import java.util.ArrayDeque;

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("头部元素: " + element);

        // 使用 peekFirst()
        String firstElement = animals.peekFirst();
        System.out.println("第一个元素: " + firstElement);

        // 使用 peekLast
        String lastElement = animals.peekLast();
        System.out.println("最后一个元素: " + lastElement);
    }
}

输出

ArrayDeque: [Dog, Cat, Horse]
头部元素: Dog
第一个元素: Dog
最后一个元素: Horse

注意： 如果数组双端队列为空，peek(), peekFirst() 和 getLast() 抛出 NoSuchElementException。

移除 ArrayDeque 元素​

1. 使用 remove(), removeFirst(), removeLast() 方法移除元素

  • remove() - 返回并移除数组双端队列的第一个元素
  • remove(element) - 返回并移除数组双端队列头部的指定元素
  • removeFirst() - 返回并移除数组双端队列的第一个元素（等同于 remove()）
  • removeLast() - 返回并移除数组双端队列的最后一个元素

注意： 如果数组双端队列为空，remove(), removeFirst() 和 removeLast() 方法抛出异常。另外，如果找不到元素，remove(element) 也会抛出异常。

例如，

import java.util.ArrayDeque;

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);

        // 使用 remove()
        String element = animals.remove();
        System.out.println("移除的元素: " + element);

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

        // 使用 removeFirst()
        String firstElement = animals.removeFirst();
        System.out.println("移除的第一个元素: " + firstElement);

        // 使用 removeLast()
        String lastElement = animals.removeLast();
        System.out.println("移除的最后一个元素: " + lastElement);
    }
}

输出

ArrayDeque: [Dog, Cat, Cow, Horse]
移除的元素: Dog
新的 ArrayDeque: [Cat, Cow, Horse]
移除的第一个元

素: Cat
移除的最后一个元素: Horse

2. 使用 poll(), pollFirst() 和 pollLast() 方法移除元素

  • poll() - 返回并移除数组双端队列的第一个元素
  • pollFirst() - 返回并移除数组双端队列的第一个元素（等同于 poll()）
  • pollLast() - 返回并移除数组双端队列的最后一个元素

注意： 如果数组双端队列为空，poll(), pollFirst() 和 pollLast() 会返回 null。

例如，

import java.util.ArrayDeque;

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);

        // 使用 poll()
        String element = animals.poll();
        System.out.println("移除的元素: " + element);
        System.out.println("新的 ArrayDeque: " + animals);

        // 使用 pollFirst()
        String firstElement = animals.pollFirst();
        System.out.println("移除的第一个元素: " + firstElement);

        // 使用 pollLast()
        String lastElement = animals.pollLast();
        System.out.println("移除的最后一个元素: " + lastElement);
    }
}

输出

ArrayDeque: [Dog, Cat, Cow, Horse]
移除的元素: Dog
新的 ArrayDeque: [Cat, Cow, Horse]
移除的第一个元素: Cat
移除的最后一个元素: Horse

3. 移除所有元素：使用 clear() 方法

要从数组双端队列中移除所有元素，我们使用 clear() 方法。例如，

import java.util.ArrayDeque;

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);

        // 使用 clear()
        animals.clear();

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

输出

ArrayDeque: [Dog, Cat, Horse]
新的 ArrayDeque: []

遍历 ArrayDeque​

  • iterator() - 返回一个迭代器，可用于遍历数组双端队列
  • descendingIterator() - 返回一个迭代器，可用于逆序遍历数组双端队列

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

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

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()
        Iterator<String> iterate = animals.iterator();
        while(iterate.hasNext()) {
            System.out.print(iterate.next());
            System.out.print(", ");
        }

        System.out.print("\nArrayDeque 逆序: ");
        // 使用 descendingIterator()
        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 中实现 后进先出（LIFO） 栈，建议使用双端队列而不是 栈类。ArrayDeque 类可能比 Stack 类更快。

ArrayDeque 提供了以下方法，可用于实现栈。

  • push() - 将一个元素添加到栈顶
  • peek() - 返回栈顶的一个元素
  • pop() - 返回并移除栈顶的一个元素

例如，

import java.util.ArrayDeque;

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);

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

        // 从栈顶移除元素
        String remElement = stack.pop();
        System.out.println("移除的元素: " + remElement);
    }
}

输出

栈: [Horse, Cat, Dog]
访问的元素: Horse
移除的元素: Horse

ArrayDeque 与 LinkedList 类比较​

ArrayDeque 和 Java LinkedList 都实现了 Deque 接口。然而，它们之间存在一些差异。

  • LinkedList 支持 null 元素，而 ArrayDeque 不支持。
  • 链表中的每个节点都包含指向其他节点的链接。因此，LinkedList 比 ArrayDeque 需要更多的存储空间。
  • 如果您正在实现队列或双端队列数据结构，ArrayDeque 可能比 LinkedList 更快。
最后于 更新