一、介绍

双端队列，一个支持在两端插入和移除元素的线性集合。

Deque 是 “double ended queue”（双端队列）的缩写，通常发音为 “deck”。大多数 Deque 实现对其包含的元素数量没有固定限制，但该接口同时支持容量受限和没有固定大小限制的双端队列。

该接口定义了访问双端队列两端元素的方法，提供了插入、移除和检索元素的方法。每个方法都有两种形式：一种在操作失败时抛出异常，另一种则返回一个特殊值（取决于操作，返回 null 或 false）。后一种插入操作形式专门为容量受限的双端队列设计；在大多数实现中，插入操作不会失败。

以下是 12 种双端队列方法总结：

  • 操作头部元素（First Element）
操作类型 抛出异常 返回特殊值
插入 addFirst(e) offerFirst(e)
删除 removeFirst() pollFirst()
检索 getFirst() peekFirst()
  • 操作尾部元素（Last Element）
操作类型 抛出异常 返回特殊值
插入 addLast(e) offerLast(e)
删除 removeLast() pollLast()
检索 getLast() peekLast()

此接口扩展了 Queue 接口。当双端队列用作队列时，会表现出 FIFO（先进先出）行为。元素添加到双端队列的末尾，从开头移除。继承自 Queue 接口的方法与双端队列方法完全等价，Queue 和 Deque 方法比较如下表所示：

Queue 方法 Deque 等价方法
add(e) addLast(e)
offer(e) offerLast(e)
remove() removeFirst()
poll() pollFirst()
element() getFirst()
peek() peekFirst()

双端队列还可以用作 LIFO（后进先出）栈。该接口应优先于传统的 Stack 类使用。当双端队列用作栈时，元素从双端队列的开头被推入或弹出。栈方法与双端队列方法等价，Stack 和 Deque 方法比较如下表所示：

Stack 方法 Deque 等价方法
push(e) addFirst(e)
pop() removeFirst()
peek() getFirst()

需要注意的是，peek 方法在双端队列用作队列或栈时都适用；在这两种情况下，元素都来自双端队列的开头。

此接口还提供了两个用于移除内部元素的方法：removeFirstOccurrence 和 removeLastOccurrence。

与 List 接口不同，该接口不提供基于索引的元素访问支持。

尽管双端队列的实现并不严格禁止插入 null 元素，但强烈建议不要这样做。使用允许插入 null 元素的双端队列实现的用户也被强烈建议不要利用此功能。这是因为 null 在多种方法中被用作特殊返回值，表示双端队列为空。

双端队列的实现通常不定义基于元素的 equals 和 hashCode 方法，而是继承自 Object 类的基于对象身份的版本。

二、源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
public interface Deque<E> extends Queue<E>, SequencedCollection<E> {

    void addFirst(E e);
    
    void addLast(E e);
    
    boolean offerFirst(E e);
    
    boolean offerLast(E e);
    
    E removeFirst();
    
    E removeLast();
    
    E pollFirst();
    
    E pollLast();
    
    E getFirst();
    
    E getLast();
    
    E peekFirst();
    
    E peekLast();
    
    boolean removeFirstOccurrence(Object o);
    
    boolean removeLastOccurrence(Object o);

    // *** Queue methods ***
    
    boolean add(E e);
    
    boolean offer(E e);
    
    E remove();
    
    E poll();
    
    E element();
    
    E peek();

    // *** Stack methods ***
    
    void push(E e);
    
    E pop();

    // *** Collection methods ***
    
    boolean remove(Object o);

    boolean contains(Object o);
    
    int size();
    
    Iterator<E> iterator();
    
    Iterator<E> descendingIterator();
    
    default Deque<E> reversed() {  
        return ReverseOrderDequeView.of(this);  
    }
}

1、removeFirstOccurrence

boolean removeFirstOccurrence(Object o); 方法从此双端队列中移除入参元素的第一次出现。如果双端队列不包含该元素，则保持不变。

移除第一个满足 Objects.equals(o, e) 的元素（如果该元素存在）。如果此双端队列包含指定元素（或等价地说，此调用导致双端队列发生了变化），则返回 true。

2、removeLastOccurrence

boolean removeLastOccurrence(Object o); 方法从此双端队列中移除指定元素的最后一次出现。如果双端队列不包含该元素，则保持不变。

移除最后一个满足 Objects.equals(o, e) 的元素（如果该元素存在）。如果此双端队列包含指定元素（或等价地说，此调用导致双端队列发生了变化），则返回 true。

3、继承自 Collection 的方法

1
2
3
4
5
6
7
boolean remove(Object o);

boolean contains(Object o);

Iterator<E> iterator();

int size();

3.1 remove 方法

从此双端队列中移除指定元素的第一次出现。如果双端队列不包含该元素，则保持不变。

更正式地说，移除第一个满足 Objects.equals(o, e) 的元素（如果该元素存在）。如果此双端队列包含指定元素（或等价地说，此调用导致双端队列发生了变化），则返回 true。

此方法等同于 removeFirstOccurrence(Object)。

3.2 contains 方法

如果此双端队列包含指定元素，则返回 true。更正式地说，当且仅当此双端队列中至少存在一个元素 e 满足 Objects.equals(o, e) 时，返回 true。

3.3 iterator 方法

返回一个按正确顺序遍历此双端队列中元素的迭代器。元素将按从第一个（头部）到最后一个（尾部）的顺序返回。

4、继承自 Queue 的方法

1
2
3
4
5
6
7
8
9
10
11
boolean add(E e);

boolean offer(E e);

E remove();

E poll();

E element();

E peek();

4.1 add 方法

如果可以在不违反容量限制的情况下立即将指定元素插入此双端队列表示的队列中（换句话说，插入到此双端队列的尾部），则插入成功时返回 true，如果当前没有可用空间，则抛出 IllegalStateException。在使用容量受限的双端队列时，通常更倾向于使用 offer 方法。

此方法等同于 addLast。

4.2 offer 方法

如果可以在不违反容量限制的情况下立即将指定元素插入此双端队列表示的队列中（即插入到此双端队列的尾部），则插入成功时返回 true，如果当前没有可用空间，则返回 false。在使用容量受限的双端队列时，此方法通常优于 add 方法，后者只能通过抛出异常来表示插入失败。

此方法等同于 offerLast。

4.3 remove 方法

检索并移除此双端队列表示的队列的头部元素（换句话说，即此双端队列的第一个元素）。此方法与 poll() 的区别在于，当此双端队列为空时，它会抛出异常。

此方法等同于 removeFirst()。

4.4 poll 方法

检索并移除此双端队列表示的队列的头部元素（换句话说，即此双端队列的第一个元素），如果此双端队列为空，则返回 null。

此方法等同于 pollFirst()。

4.5 element 方法

检索但不移除此双端队列表示的队列的头部元素（换句话说，即此双端队列的第一个元素）。此方法与 peek() 的区别在于，当双端队列为空时，它会抛出异常。

此方法等同于 getFirst()。

4.6 peek

检索但不移除此双端队列表示的队列的头部元素（换句话说，即此双端队列的第一个元素），如果此双端队列为空，则返回 null。

此方法等同于 peekFirst()。

5、descendingIterator

返回一个按逆序遍历此双端队列中元素的迭代器。元素将按从最后一个（尾部）到第一个（头部）的顺序返回。

6、双端队列的 12 个方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void addFirst(E e);

void addLast(E e);

boolean offerFirst(E e);

boolean offerLast(E e);

E removeFirst();

E removeLast();

E pollFirst();

E pollLast();

E getFirst();

E getLast();

E peekFirst();

E peekLast();

6.1 addFirst

如果可以在不违反容量限制的情况下立即将指定元素插入到此双端队列的前端，则进行插入操作；如果当前没有可用空间，则抛出 IllegalStateException。在使用容量受限的双端队列时，通常更倾向于使用 offerFirst 方法。

6.2 addLast

如果可以在不违反容量限制的情况下立即将指定元素插入到此双端队列的末尾，则进行插入操作；如果当前没有可用空间，则抛出 IllegalStateException。在使用容量受限的双端队列时，通常更倾向于使用 offerLast 方法。

此方法等同于 add。

6.3 offerFirst

在不违反容量限制的情况下，将指定元素插入到此双端队列的前端。在使用容量受限的双端队列时，此方法通常优于 addFirst 方法，后者只能通过抛出异常来表示插入失败。

6.4 offerLast

在不违反容量限制的情况下，将指定元素插入到此双端队列的末尾。在使用容量受限的双端队列时，此方法通常优于 addLast 方法，后者只能通过抛出异常来表示插入失败。

6.5 removeFirst

检索并移除此双端队列的第一个元素。此方法与 pollFirst 的区别在于，当此双端队列为空时，它会抛出异常。

6.6 removeLast

检索并移除此双端队列的最后一个元素。此方法与 pollLast 的区别在于，当此双端队列为空时，它会抛出异常。

6.7 pollFirst

检索并移除此双端队列的第一个元素，如果此双端队列为空，则返回 null。

6.8 pollLast

检索并移除此双端队列的最后一个元素，如果此双端队列为空，则返回 null。

6.9 getFirst

检索但不移除此双端队列的第一个元素。此方法与 peekFirst 的区别在于，当此双端队列为空时，它会抛出异常。

6.10 getLast

检索但不移除此双端队列的最后一个元素。此方法与 peekLast 的区别在于，当此双端队列为空时，它会抛出异常。

6.11 peekFirst

检索但不移除此双端队列的第一个元素，如果此双端队列为空，则返回 null。

6.12 peekLast

检索但不移除此双端队列的最后一个元素，如果此双端队列为空，则返回 null。

相关链接

Queue | z2huo

JEP 431 Sequenced Collections 顺序集合 | z2huo

[[Queue]]

[[SequencedCollection]]

[[JEP 431 Sequenced Collections 顺序集合]]

OB tags

#Java