双端队列（Deque）原理及实现

基本原理
如果你理解了前面讲解的内容，这个双端队列其实没啥可讲的了。所谓双端队列，主要是对比标准队列（FIFO 先进先出队列）多了一些操作罢了：
标准队列 只能在队尾插入元素，队头删除元素，而双端队列的队头和队尾都可以插入或删除元素。
普通队列就好比排队买票，先来的先买，后来的后买；而双端队列就好比一个过街天桥，两端都可以随意进出。当然，双端队列的元素就不再满足「先进先出」了，因为它比较灵活嘛。
在做算法题的场景中，双端队列用的不算很多。感觉只有 Python 用到的多一些，因为 Python 标准库没有提供内置的栈和队列，一般会用双端队列来模拟标准队列。
用链表实现双端队列
很简单吧，直接复用 我们之前实现的MyLinkedList 或者标准库提供的 LinkedList 就行了。因为双链表本就支持 O(1) 时间复杂度在链表的头尾增删元素：
Java
运行代码
复制代码
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
import java.util.LinkedList;

public class MyListDeque {
private LinkedList list = new LinkedList<>();

// 从队头插入元素，时间复杂度 O(1)
void addFirst(E e) {
    list.addFirst(e);
}

// 从队尾插入元素，时间复杂度 O(1)
void addLast(E e) {
    list.addLast(e);
}

// 从队头删除元素，时间复杂度 O(1)
E removeFirst() {
    return list.removeFirst();
}

// 从队尾删除元素，时间复杂度 O(1)
E removeLast() {
    return list.removeLast();
}

// 查看队头元素，时间复杂度 O(1)
E peekFirst() {
    return list.getFirst();
}

// 查看队尾元素，时间复杂度 O(1)
E peekLast() {
    return list.getLast();
}

public static void main(String[] args) {
    MyListDeque<Integer> deque = new MyListDeque<>();
    deque.addFirst(1);
    deque.addFirst(2);
    deque.addLast(3);
    deque.addLast(4);

    System.out.println(deque.removeFirst()); // 2
    System.out.println(deque.removeLast()); // 4
    System.out.println(deque.peekFirst()); // 1
    System.out.println(deque.peekLast()); // 3
}

}
用数组实现双端队列
也很简单吧，直接复用我们在 环形数组技巧 中实现的 CycleArray 提供的方法就行了。环形数组头尾增删元素的复杂度都是 O(1)：
Java
运行代码
复制代码
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
class MyArrayDeque {
private CycleArray arr = new CycleArray<>();

// 从队头插入元素，时间复杂度 O(1)
void addFirst(E e) {
    arr.addFirst(e);
}

// 从队尾插入元素，时间复杂度 O(1)
void addLast(E e) {
    arr.addLast(e);
}

// 从队头删除元素，时间复杂度 O(1)
E removeFirst() {
    return arr.removeFirst();
}

// 从队尾删除元素，时间复杂度 O(1)
E removeLast() {
    return arr.removeLast();
}

// 查看队头元素，时间复杂度 O(1)
E peekFirst() {
    return arr.getFirst();
}

// 查看队尾元素，时间复杂度 O(1)
E peekLast() {
    return arr.getLast();
}

}