Java中的Deque接口及其示例

Deque (双端队列)接口存在于java.util包中，是队列接口的一个子类型，具有支持从数据结构的任意一端添加或删除元素的功能。它既可以用作队列（也就是先进先出/FIFO），也可以用作堆栈（也就是后进先出/LIFO）。Deque是双端队列的缩写。

Java中的Deque（双端队列）接口是Queue接口的子接口，扩展了Queue接口以提供双端队列，是一种允许从两端添加和删除元素的队列。Deque接口是Java集合框架的一部分，用于提供通用和灵活的数据结构，可用于实现各种算法和数据结构。

以下是在Java中使用Deque的示例：

import java.util.ArrayDeque;
import java.util.Deque;
 
public class Example {
  public static void main(String[] args) {
    Deque<Integer> deque = new ArrayDeque<>();
    deque.addFirst(1);
    deque.addLast(2);
    int first = deque.removeFirst();
    int last = deque.removeLast();
    System.out.println("First: " + first + ", Last: " + last);
  }
}

输出结果

First: 1, Last: 2

使用Deque的优点：

1. 双端性：Deque接口的主要优点是它提供双端队列，允许在队列的前端和末尾添加或删除元素。这使得它成为在需要在队列的前端和末尾插入或删除元素的场景下的不错选择。
2. 灵活性：Deque接口提供了许多在队列的前端和末尾添加、删除和检索元素的方法，使您在使用时有很高的灵活性。
3. 阻塞操作：Deque接口提供了阻塞方法，例如takeFirst和takeLast，允许您等待元素可用或队列中的空间可用。这使其成为并发和多线程应用程序的不错选择。

使用Deque的缺点：

1. 性能：与其他数据结构（例如链表或数组）相比，Deque的性能可能较慢，因为它提供了更多的功能。
2. 实现相关：Deque的行为取决于您使用的实现。例如，某些实现可能提供线程安全操作，而其他实现可能没有。在使用Deque之前，选择适当的实现并了解其行为非常重要。

参考书籍：

《Java Generics and Collections》由Maurice Naftalin和Philip Wadler编写，是Java集合框架和泛型的全面指南，包括Deque接口。本书介绍了集合框架的基础知识，解释了如何实际使用集合和泛型，并为编写正确和高效代码提供了提示和最佳实践。如果您想了解更多关于Deque接口和Java集合框架的知识，本书是一个优秀的资源。

语法： Deque接口声明如下：

public interface Deque extends Queue

创建Deque对象 由于Deque是一个接口，因此不能创建deque类型的对象。我们始终需要一个扩展该列表的类才能创建对象。并且，自从Java 1.5引入泛型之后，就可以限制可以存储在Deque中的对象类型。可以定义这种类型安全的队列:

// Obj是要存储在Deque中的对象类型
Deque<Obj> deque = new ArrayDeque<Obj>();

示例： Deque

//Java程序演示在Java中的Deque的工作：
 
import java.util.*;
 
public class DequeExample {
    public static void main(String[] args)
    {
        Deque<String> deque
            = new LinkedList<String>();
 
        //我们可以以各种方式向队列添加元素
 
        //在最后添加
        deque.add("元素1（尾部）");
 
        //在最前面添加
        deque.addFirst("元素2（头）");
 
        //在最后添加
        deque.addLast("元素3（尾部）");
 
        //在最前面添加
        deque.push("元素4（头）");
 
        //在最后添加
        deque.offer("元素5（尾部）");
 
        //在最前面添加
        deque.offerFirst("元素6（头）");
 
        System.out.println(deque + "");
 
        //我们可以删除第一个元素或最后一个元素。
        deque.removeFirst();
        deque.removeLast();
        System.out.println("删除第一个和最后一个元素后的队列："
                        + deque);
    }
}

输出

[元素6（头），元素4（头），元素2（头），元素1（尾部），元素3（尾部），元素5（尾部）]

删除第一个和最后一个元素后的队列：[元素4（头），元素2（头），元素1（尾部），元素3（尾部）]

使用Deque接口和ArrayDeque类的操作

让我们看看如何使用ArrayDeque类在deque上执行一些常用操作。

1. 添加元素: 为了在deque中添加元素，我们可以使用add()方法。队列和deque之间的区别在于，在deque中，可以从任何方向添加。因此，还有另外两个可用的方法addFirst()和addLast()，它们用于在任一端添加元素。

//Java程序演示在deque中添加元素：
 
import java.util.*;
public class ArrayDequeDemo {
    public static void main(String[] args)
    {
        //初始化deque
        Deque<String> dq
            = new ArrayDeque<String>();
 
        //添加元素的add()方法
        dq.add("为");
        dq.addFirst("Geeks");
        dq.addLast("Geeks");
 
        System.out.println(dq);
    }
}

输出

[Geeks，为，Geeks]

2. 删除元素： 为了从deque中删除元素，有各种方法可用。由于我们还可以从两端删除，deque接口为我们提供了 removeFirst()，removeLast()方法。除此之外，该接口还为我们提供了poll()，pop()，pollFirst()，pollLast()方法，其中pop()用于删除并返回deque的头。但是，使用poll()是因为它提供与pop()相同的功能，并且在deque为空时不返回异常。

// Java程序演示删除deque中的元素
 
import java.util.*;
public class ArrayDequeDemo {
    public static void main(String[] args)
    {
        // 初始化一个deque
        Deque<String> dq
            = new ArrayDeque<String>();
 
        // add()方法插入元素
        dq.add("For");
        dq.addFirst("Geeks");
        dq.addLast("Geeks");
 
        System.out.println(dq);
 
        System.out.println(dq.pop());
 
        System.out.println(dq.poll());
 
        System.out.println(dq.pollFirst());
 
        System.out.println(dq.pollLast());
    }
}

输出

[Geeks, For, Geeks]
Geeks
For
Geeks
null

3. 遍历Deque： 由于deque可以从两个方向遍历，deque接口的iterator方法提供了两种遍历方式。一种是从前往后，另一种是从后往前。

// Java程序演示deque中的元素遍历
 
import java.util.*;
public class ArrayDequeDemo {
    public static void main(String[] args)
    {
        // 初始化一个deque
        Deque<String> dq
            = new ArrayDeque<String>();
 
        // add()方法插入元素
        dq.add("For");
        dq.addFirst("Geeks");
        dq.addLast("Geeks");
        dq.add("is so good");
 
        for (Iterator itr = dq.iterator();
            itr.hasNext();) {
            System.out.print(itr.next() + " ");
        }
 
        System.out.println();
 
        for (Iterator itr = dq.descendingIterator();
            itr.hasNext();) {
            System.out.print(itr.next() + " ");
        }
    }
}

输出

Geeks For Geeks is so good 
is so good Geeks For Geeks 

实现Deque接口的类是ArrayDeque。

ArrayDeque: 在集合框架中实现的ArrayDeque类为我们提供了一种应用可调整大小数组的方法。这是一种特殊的数组，它可以扩展并允许用户从队列的两侧添加或删除元素。数组双向队列没有容量限制，并且它们会随着需要增长以支持使用。它们不是线程安全的，这意味着在没有外部同步的情况下，ArrayDeque不支持多线程并发访问。当作为堆栈使用时，ArrayDeque类可能比Stack类更快。当作为队列使用时，ArrayDeque类可能比LinkedList类更快。让我们看看如何使用这个类创建一个队列对象。

// Java程序演示使用ArrayDeque类创建deque对象
 
import java.util.*;
public class ArrayDequeDemo {
    public static void main(String[] args)
    {
        // 初始化一个deque
        Deque<Integer> de_que
            = new ArrayDeque<Integer>(10);
 
        // add()方法插入元素
        de_que.add(10);
        de_que.add(20);
        de_que.add(30);
        de_que.add(40);
        de_que.add(50);
 
        System.out.println(de_que);
 
        // clear()方法
        de_que.clear();
 
        // addFirst()方法插入元素到头部
        de_que.addFirst(564);
        de_que.addFirst(291);
 
        // addLast()方法插入元素到尾部
        de_que.addLast(24);
        de_que.addLast(14);
 
        System.out.println(de_que);
    }
}

输出

[10, 20, 30, 40, 50]
[291, 564, 24, 14]

Deque接口的方法

以下是双端队列接口中存在的方法: