【Java】10 Deque 接口

Love The Way You Lie 2023-07-25 14:09 29阅读 0赞

> java.util.Deque 是支持两端元素插入和移除的线性集合。 名称 deque 是 “双端队列” 的缩写，通常发音为“deck”。 大多数 Deque 实现对它们可能包含的元素的数量没有固定的限制，但是该接口支持容量限制的 deques 以及没有固定大小限制的 deques。

## 一、Deque 接口 ##

Queue 用于模拟队列这种数据结构，队列通常是指 “先进先出”（FIFO）的容器。队列的头部保存在队列中存放时间最长的元素，队列的尾部保存在队列中存放时间最短的元素。新元素插入（offer）到队列的尾部，访问元素（poll）操作会返回队列头部的元素。通常，队列不允许随机访问队列中的元素。

### 1.1 常用方法 ###

<table> 
 <thead> 
  <tr> 
   <th align="left">方法名</th> 
   <th align="left">说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="left">boolean add(E e)</td> 
   <td align="left">将指定的元素插入此双端队列表示的队列中（在此双端队列的尾部），在成功时返回 true</td> 
  </tr> 
  <tr> 
   <td align="left">void addFirst(E e)</td> 
   <td align="left">将指定的元素插入此双端队列的前面</td> 
  </tr> 
  <tr> 
   <td align="left">void addLast(E e)</td> 
   <td align="left">将指定的元素插入此双端队列的末尾</td> 
  </tr> 
  <tr> 
   <td align="left">boolean contains(Object o)</td> 
   <td align="left">如果此双端队列包含指定的元素，则返回 true</td> 
  </tr> 
  <tr> 
   <td align="left">E element( )</td> 
   <td align="left">返回此双端队列的头部</td> 
  </tr> 
  <tr> 
   <td align="left">E getFirst( )</td> 
   <td align="left">返回此双端队列的第一个元素</td> 
  </tr> 
  <tr> 
   <td align="left">E getLast()</td> 
   <td align="left">返回此双端队列的最后一个元素</td> 
  </tr> 
  <tr> 
   <td align="left">boolean offer(E e)</td> 
   <td align="left">将指定的元素插入由此双端队列的尾部）</td> 
  </tr> 
  <tr> 
   <td align="left">boolean offerFirst(E e)</td> 
   <td align="left">在此双端队列前面插入指定的元素</td> 
  </tr> 
  <tr> 
   <td align="left">boolean offerLast(E e)</td> 
   <td align="left">在此双端队列末尾插入指定的元素</td> 
  </tr> 
  <tr> 
   <td align="left">E peek( )</td> 
   <td align="left">返回此双端队列的头部，如果此双端队列为空，则返回 null</td> 
  </tr> 
  <tr> 
   <td align="left">E peekFirst( )</td> 
   <td align="left">返回此双端队列的第一个元素，如果此双端队列为空，则返回 null</td> 
  </tr> 
  <tr> 
   <td align="left">E peekLast( )</td> 
   <td align="left">返回此双端队列的最后一个元素，如果此双端队列为空，则返回 null</td> 
  </tr> 
  <tr> 
   <td align="left">E poll( )</td> 
   <td align="left">返回并删除此双端队列的头部，如果此双端队列为空，则返回 null</td> 
  </tr> 
  <tr> 
   <td align="left">E pollFirst( )</td> 
   <td align="left">返回并删除此双端队列的第一个元素，如果此双端队列为空，则返回 null</td> 
  </tr> 
  <tr> 
   <td align="left">E pollLast( )</td> 
   <td align="left">返回并删除此双端队列的最后一个元素，如果此双端队列为空，则返回 null</td> 
  </tr> 
  <tr> 
   <td align="left">E pop( )</td> 
   <td align="left">从此双端队列表示的堆栈中弹出一个元素</td> 
  </tr> 
  <tr> 
   <td align="left">void push(E e)</td> 
   <td align="left">将元素推送到此双端队列表示的堆栈</td> 
  </tr> 
  <tr> 
   <td align="left">E remove( )</td> 
   <td align="left">返回并删除由此双端队列的头部</td> 
  </tr> 
  <tr> 
   <td align="left">boolean remove(Object o)</td> 
   <td align="left">从此双端队列中删除第一个出现的元素 o</td> 
  </tr> 
  <tr> 
   <td align="left">E removeFirst( )</td> 
   <td align="left">返回并删除此双端队列的第一个元素</td> 
  </tr> 
  <tr> 
   <td align="left">boolean removeFirstOccurrence(Object o)</td> 
   <td align="left">从此双端队列中删除第一个出现的元素 o</td> 
  </tr> 
  <tr> 
   <td align="left">E removeLast( )</td> 
   <td align="left">返回并删除此双端队列的最后一个元素</td> 
  </tr> 
  <tr> 
   <td align="left">boolean removeLastOccurrence(Object o)</td> 
   <td align="left">从此双端队列中删除最后出现的元素 o</td> 
  </tr> 
  <tr> 
   <td align="left">int size( )</td> 
   <td align="left">返回此双端队列中的元素个数</td> 
  </tr> 
 </tbody> 
</table>

### 1.2 注意 ###

因为包含了pop（出栈）、push（入栈）两个方法，所以 Deque不仅可以当成双端队列使用，而且可以被当成栈来使用。

--------------------

## 二、ArrayDeque 集合 ##

Deque 接口提供了一个典型的实现类：ArrayDeque，它是一个基于数组实现的双端队列，创建 Deque 时同样可指定一个 numElements 参数，该参数用于指定 Object 数组的长度；如果不指定 numElements 参数，Deque 底层数组的默认长度为16。它是线程安全的，不支持多线程的并发访问。 零元素被禁止。当用作堆栈时，此类可能会比 Stack 快，并且当用作队列时速度高于 LinkedList 。

### 2.1 构造方法 ###

![20200415113043548.png][]

### 2.2 示例 ###

> ArrayDeque 作为 “栈”

public class ArrayDequeStack { 
    	public static void main(String[] args)
    		ArrayDeque stack = new ArrayDeque();
    		// 依次将三个元素 push 入 "栈"
    		stack.push("Java SE"):
    		stack.push("Java EE");
    		stack.push("Java ME");
    		// 输出：[Java ME，Java EE，Java SE]
    		System.out.println(stack);
    		// 访问第一个元素，但并不将其 pop 出 "栈"，输出：Java ME
    		System.out.println(stack.peek());
    		// 依然输出：[Java ME，Java EE，Java SE]
    		System.out.println(stack);
    		//pop 出第一个元素，输出：Java ME
    		System.out.println(stack.pop());
    		//输出：[Java EE，Java SE]
    		System.out.println(stack);
    	}
    }

> ArrayDeque 作为 “队列”

public class ArrayDequeQueue { 
    	public static void main(String[] args) { 
    		ArrayDeque queue = new ArrayDeque();
    		// 依次将三个元素加入队列
    		queue.offer("Java SE");
    		queue.offer("Java EE");
    		queue.offer("Java ME");
    		// 输出：[Java SE，Java EE，Java ME]
    		System.out.println(queue);
    		// 访问队列头部的元素，但并不将其 poll 出队列，输出：Java SE
    		System.out.printin(queue.peek());
    		// 依然输出：[Java SE，Java EE，Java ME]
    		System.out.println(queue);
    		// poll 出第一个元素，输出：Java SE
    		System.out.printin(queue.poll());
    		// 输出：[Java SE，Java EE，Java ME]
    		System.out.println(queue);
    	}
    }

--------------------

## 三、LinkedList 集合 ##

LinkedList 集合是 List 接口的实现类，所以它可以被当作 List 集合使用，根据索引来随机访问集合中的元素。除此之外，LinkedList 集合还实现了 Deque 接口，既可以被当成 “栈” 来使用，也可以当成 “队列” 使用。

### 3.1 示例 ###

public class DemoLinkedList { 
        public static void main(String[] args) { 
            //创建集合
            LinkedList<String> list = new LinkedList<>();
    
            //开头添加数据
            list.addFirst("前");
            //末尾添加数据
            list.addLast("后");
            //压栈
            list.push("Java");
    
    		// 输出：[Java，前，后]
            System.out.println(list);
    
            //删除开头数据，输出：Java
            System.out.println(list.removeFirst());
            //删除末尾数据，输出：后
            System.out.println(list.removeLast());
            //弹栈，输出：前
            System.out.println(list.pop());
    		// 输出：[]
            System.out.println(list);
        }
    }

### 3.2 注意 ###

LinkedList 与 ArrayList、ArrayDeque 的实现机制完全不同，ArrayList、ArrayDeque 内部以数组的形式来保存集合中的元素，因此随机访问集合元素时有较好的性能；而 LinkedList 内部以链表的形式来保存集合中的元素，因此随机访问集合元素时性能较差，但在插入、删除元素时性能比较出色（只需改变指针所指的地址即可）。需要指出的是，虽然 Vector 也是以数组的形式来存储集合元素的，但因为它实现了线程同步功能（而且实现机制也不好），所以各方面性能都比较差。  
   如果需要遍历 List 集合元素，对于 ArrayList、Vector 集合，应该使用随机访问方法 get( ) 来遍历集合元素，这样性能更好；对于 LinkedList 集合，则应该采用迭代器（Iterator）来遍历集合元素。  
   如果需要经常执行插入、删除操作来改变包含大量数据的 List 集合的大小，可考虑使用 LinkedList 集合。使用 ArrayList、Vector 集合可能需要经常重新分配内部数组的大小，效果可能较差。

[20200415113043548.png]: /images/20230528/f4700d0304c54677b9ae57b93deb1890.png