双端列表 —— Deque 接口概述，使用ArrayDeque实现队列和双端队列数据结构

淩亂°似流年 2024-03-23 20:58 36阅读 0赞

![fe56b8b009754d0ba5037cb89fe70ef7.jpeg][]

### **Deque接口简介** ###

Deque译为双端队列，在双向都能作为队列来使用，同时可用作栈。Deque接口的方法是对称成比例的。  
Deque接口继承Queue接口，因此具有Queue，[Collection][]，Iterable的方法属性。

### 双端队列的工作原理 ###

在常规队列中，元素是从后面添加的，而从前面删除的。但是，在双端队列中，我们可以**从前后插入和删除元素**。

![双端队列数据结构的工作][working-of-deque.png]![66143d4a562b4c45afd6e4cca4c74158.png][]

### 实现Deque的类 ###

为了使用Deque接口的功能，我们需要使用实现接口的类：

*  [ArrayDeque][]
 *  [LinkedList][]

![ArrayDeque和Linkedlist实现Deque][ArrayDeque_Linkedlist_Deque]![ca11aacf87b24adea274881049c287db.png][]

### 如何使用Deque？ ###

在Java中，我们必须导入要使用Deque的包 java.util.Deque 。

Deque<String> animal1 = new ArrayDeque<>();
    
    Deque<String> animal2 = new LinkedList<>();

在这里，我们分别创建了类ArrayDeque和LinkedList的对象animal1和animal2。 这些对象可以使用Deque接口的功能。

### Deque的方法 ###

Deque接口定义了以下方法：

<table> 
 <thead> 
  <tr> 
   <th style="text-align:center;">方法</th> 
   <th style="text-align:center;">描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td><code>void addFirst(E e)</code></td> 
   <td>将元素插入此deque的开头</td> 
  </tr> 
  <tr> 
   <td><code>void addLast(E e)</code></td> 
   <td>将元素插入此deque的末尾</td> 
  </tr> 
  <tr> 
   <td><code>boolean offerFirst(E e)</code></td> 
   <td>在此deque的开头插入指定元素。</td> 
  </tr> 
  <tr> 
   <td><code>boolean offerLast(E e)</code></td> 
   <td>在此deque的末尾插入指定元素。</td> 
  </tr> 
  <tr> 
   <td><code>E removeFirst()</code></td> 
   <td>检索并删除此deque的第一个元素</td> 
  </tr> 
  <tr> 
   <td><code>E removeLast()</code></td> 
   <td>检索并删除此deque的最后一个元素</td> 
  </tr> 
  <tr> 
   <td><code>E pollFirst()</code></td> 
   <td>检索并删除此deque的第一个元素；如果deque为空，则返回null</td> 
  </tr> 
  <tr> 
   <td><code>E pollLast()</code></td> 
   <td>检索并删除此deque的最后一个元素；如果deque为空，则返回null</td> 
  </tr> 
  <tr> 
   <td><code>E getFirst()</code></td> 
   <td>检索但不删除此deque的第一个元素。</td> 
  </tr> 
  <tr> 
   <td><code>E getLast()</code></td> 
   <td>检索但不删除此deque的最后一个元素。</td> 
  </tr> 
  <tr> 
   <td><code>E peekFirst()</code></td> 
   <td>检索但不删除此deque的第一个元素；如果deque为空，则返回null</td> 
  </tr> 
  <tr> 
   <td><code>E peekLast()</code></td> 
   <td>检索但不删除此deque的最后一个元素；如果deque为空，则返回null</td> 
  </tr> 
  <tr> 
   <td><code>boolean removeFirstOccurrence(Object o)</code></td> 
   <td>从deque中删除第一次出现的指定元素（从头部到尾部遍历deque时）。</td> 
  </tr> 
  <tr> 
   <td><code>boolean removeLastOccurrence(Object o)</code></td> 
   <td>从deque中删除最后一次出现的指定元素（从头部到尾部遍历deque时）。</td> 
  </tr> 
  <tr> 
   <td><code>boolean add(E e)</code></td> 
   <td>将指定元素添加到此deque的末尾。</td> 
  </tr> 
  <tr> 
   <td><code>boolean offer(E e)</code></td> 
   <td>将指定元素添加到此deque的末尾。</td> 
  </tr> 
  <tr> 
   <td><code>E remove()</code></td> 
   <td>检索并删除此deque的头部。</td> 
  </tr> 
  <tr> 
   <td><code>E poll()</code></td> 
   <td>检索并删除此deque的头部；如果deque为空，则返回null。</td> 
  </tr> 
  <tr> 
   <td><code>E element()</code></td> 
   <td>检索但不删除此deque的头部。</td> 
  </tr> 
  <tr> 
   <td><code>E peek()</code></td> 
   <td>检索但不删除此deque的头部；如果deque为空，则返回null。</td> 
  </tr> 
  <tr> 
   <td><code>void push(E e)</code></td> 
   <td>将元素推入此deque的堆栈层次结构中，也就是在deque的头部插入一个元素。</td> 
  </tr> 
  <tr> 
   <td><code>E pop()</code></td> 
   <td>从此deque表示的堆栈处弹出一个元素，也就是把deque的头部元素移除掉。</td> 
  </tr> 
  <tr> 
   <td><code>boolean contains(Object o)</code></td> 
   <td>如果此deque包含指定元素，则返回true。</td> 
  </tr> 
  <tr> 
   <td><code>int size()</code></td> 
   <td>返回deque中的元素数。</td> 
  </tr> 
  <tr> 
   <td><code>Iterator&lt;E&gt; iterator()</code></td> 
   <td>返回一个按元素插入顺序遍历此deque中元素的迭代器。</td> 
  </tr> 
  <tr> 
   <td><code>Iterator&lt;E&gt; descendingIterator()</code></td> 
   <td>返回一个按元素逆序遍历此deque中元素的迭代器。</td> 
  </tr> 
 </tbody> 
</table>

### 双端队列作为堆栈数据结构 ###

Java Collections框架的Stack类提供了堆栈的实现。

但是，建议Deque用作堆栈而不是[Stack类][Stack]。这是因为Stack的方法是同步的。

以下是Deque接口提供的用于实现堆栈的方法：

*  push() - 在双端队列的开头添加元素
 *  pop() - 从双端队列的开头删除元素
 *  peek() - 从双端队列的开头返回一个元素

Deque是可以用作栈或队列的，具体是哪个取决于使用哪些方法。下面是一些示例代码，演示了如何使用Deque接口。

#### 1. 使用Deque作为队列 ####

import java.util.Deque;
    import java.util.LinkedList;
    
    public class Deque{
    
        public static void main(String[] args) {
            Deque<String> queue = new LinkedList<>();
    
            // 添加元素到队列
            queue.add("Java");
            queue.add("C++");
            queue.add("Python");
    
            // 获取队列的第一个元素，不删除
            System.out.println("First element of queue: " + queue.peek());
    
            // 获取并删除队首元素
            String firstElement = queue.poll();
            System.out.println("Removed first element of queue: " + firstElement);
    
            // 队列中添加一个新元素
            queue.offer("JavaScript");
    
            // 遍历队列中的元素
            System.out.println("All elements of queue:");
            for (String element : queue) {
                System.out.println(element);
            }
        }
    }

此代码将Deque用作队列，使用add方法添加元素，并使用peek获取第一个元素。然后，使用poll方法删除并获取队列中的第一个元素，并使用offer方法将新元素添加到队列末尾。最后，使用for-each循环遍历队列中的所有元素。

#### 2. 使用Deque作为栈 ####

import java.util.Deque;
    import java.util.LinkedList;
    
    public class Deque{
    
        public static void main(String[] args) {
            Deque<String> stack = new LinkedList<>();
    
            // 将元素推入栈中
            stack.push("Java");
            stack.push("C++");
            stack.push("Python");
    
            // 获取栈顶元素，不删除
            System.out.println("Top element of stack: " + stack.peek());
    
            // 获取并删除栈顶元素
            String topElement = stack.pop();
            System.out.println("Removed top element of stack: " + topElement);
    
            // 将新元素推入栈中
            stack.push("JavaScript");
    
            // 遍历栈中的所有元素
            System.out.println("All elements of stack:");
            for (String element : stack) {
                System.out.println(element);
            }
        }
    }

此代码演示了如何将Deque用作栈。它使用push方法将元素推入栈中，并使用peek获取栈顶元素。然后，使用pop方法获取并删除栈顶元素，并使用push方法将新元素推入栈顶。最后，使用for-each循环遍历栈中的所有元素。

### 创建ArrayDeque ###

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

这是我们可以用Java创建ArrayDeque双端队列的方法：

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

在此，Type表示ArrayDeque双端队列的类型。例如，

//创建字符串类型ArrayDeque
    ArrayDeque<String> animals = new ArrayDeque<>();
    
    //创建整数类型ArrayDeque
    ArrayDeque<Integer> age = new ArrayDeque<>();

### ArrayDeque方法 ###

ArrayDeque类提供了所有的存在于方法Queue和Deque接口。

#### 将元素插入双端队列 ####

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

>  *  add() - 将指定的元素插入ArrayDeque双端队列的末尾
>  *  addFirst() -在ArrayDeque双端队列的开头，插入指定的元素
>  *  addLast() - 在ArrayDeque双端队列的末尾插入指定的内容（等效于add()）

**注意：**如果ArrayDeque双端队列已满，则所有这些方法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() - 将指定的元素插入ArrayDeque双端队列的末尾
>  *  offerFirst() - 在ArrayDeque双端队列的开始处插入指定的元素
>  *  offerLast() - 将指定的元素插入ArrayDeque双端队列的末尾

**注意：** offer()，offerFirst()并offerLast()返回true是否成功插入元素；否则，返回。如果ArrayDeque双端队列已满，则这些方法返回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]

#### 访问ArrayDeque元素 ####

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

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

**注：**如果ArrayDeque双端队列为空，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() - 返回ArrayDeque双端队列的第一个元素
>  *  peekFirst() - 返回ArrayDeque双端队列的第一个元素（等效于peek()）
>  *  peekLast() - 返回ArrayDeque双端队列的最后一个元素

例如：

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]
    Head Element: Dog
    第一个元素： Dog
    最后一个元素： Horse

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

#### 删除 ArrayDeque 元素 ####

**1.使用remove()，removeFirst()，removeLast()方法删除元素**

>  *  remove() - 返回并从ArrayDeque双端队列的第一个元素中删除一个元素
>  *  remove(element) - 返回并从ArrayDeque双端队列的头部删除指定的元素
>  *  removeFirst() - 返回并从ArrayDeque双端队列中删除第一个元素（等效于remove()）
>  *  removeLast() - 返回并从ArrayDeque双端队列中删除最后一个元素

**注意：**如果数组双端队列为空，则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: " + 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]
    删除Element: Dog
    新的ArrayDeque： [Cat, Cow, Horse]
    删除第一个元素： Cat
    删除最后一个元素： Horse

**2.使用poll()，pollFirst()和pollLast()方法删除元素**

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

**注意：**如果ArrayDeque双端队列为空，则如果找不到该元素，则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: " + 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]
    删除Element: Dog
    新的ArrayDeque： [Cat, Cow, Horse]
    删除第一个元素： Cat
    删除最后一个元素： Horse

**3.删除元素：使用clear()方法**

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

**输出结果**

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

#### 迭代遍历ArrayDeque ####

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

为了使用这些方法，我们必须导入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("\n反向ArrayDeque: ");
            //使用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]

### 其他方法 ###

<table> 
 <tbody> 
  <tr> 
   <th>方法</th> 
   <th>内容描述</th> 
  </tr> 
  <tr> 
   <td>element()</td> 
   <td>从ArrayDeque双端队列的头部返回一个元素。</td> 
  </tr> 
  <tr> 
   <td>contains(element)</td> 
   <td>在ArrayDeque双端队列中搜索指定的元素。<br> 如果找到该元素，则返回true，否则返回false。</td> 
  </tr> 
  <tr> 
   <td>size()</td> 
   <td>返回ArrayDeque双端队列的长度。</td> 
  </tr> 
  <tr> 
   <td>toArray()</td> 
   <td>将ArrayDeque双端队列转换为数组并返回。</td> 
  </tr> 
  <tr> 
   <td>clone()</td> 
   <td>创建ArrayDeque双端队列的副本并返回它。</td> 
  </tr> 
 </tbody> 
</table>

### ArrayDeque作为堆栈 ###

要在Java中实现**LIFO（后进先出）**堆栈，建议在Stack类上使用双端队列。该ArrayDeque类比Stack类快。

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

>  *  push() - 在堆栈顶部添加一个元素
>  *  peek() - 从堆栈顶部返回一个元素
>  *  pop() - 返回并从堆栈顶部删除元素

例如：

import java.util.ArrayDeque;
    
    class Main {
        public static void main(String[] args) {
            ArrayDeque<String> stack = new ArrayDeque<>();
    
            //将元素添加到stack
            stack.push("Dog");
            stack.push("Cat");
            stack.push("Horse");
            System.out.println("Stack: " + stack);
    
            //从堆栈顶部访问元素
            String element = stack.peek();
            System.out.println("访问元素： " + element);
    
            //从堆栈顶部删除元素
            String remElement = stack.pop();
            System.out.println("删除element: " + remElement);
        }
    }

**输出结果**

Stack: [Horse, Cat, Dog]
    访问元素： Horse
    删除Element: Horse

### ArrayDeque与 LinkedList类 ###

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

>  *  LinkedList支持空元素，而ArrayDeque不支持。
>  *  链表中的每个节点都包含到其他节点的链接。这就是LinkedList比ArrayDeque需要更多存储空间的原因。
>  *  如果要实现队列或双端队列数据结构，则ArrayDeque可能比LinkedList快。

[fe56b8b009754d0ba5037cb89fe70ef7.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/59f88f89ddb9479ba6404d50484d87d6.png
[Collection]: https://so.csdn.net/so/search?q=Collection&spm=1001.2101.3001.7020
[working-of-deque.png]: https://www.nhooo.com/run/images/working-of-deque.png
[66143d4a562b4c45afd6e4cca4c74158.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/a3c40adbf6cb4a0f9b0fd019f6be4678.png
[ArrayDeque]: https://so.csdn.net/so/search?spm=1001.2014.3001.4498&q=ArrayDeque&t=&u=
[LinkedList]: https://so.csdn.net/so/search?q=LinkedList&t=&u=&urw=
[ArrayDeque_Linkedlist_Deque]: https://www.nhooo.com/run/images/deque-implemention-classes.png
[ca11aacf87b24adea274881049c287db.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/8d58720ad6644ca7bef5c502bd8550dc.png
[Stack]: https://so.csdn.net/so/search?spm=1001.2101.3001.4498&q=Stack%E7%B1%BB&t=&u=