27.7 Java集合Deque学习（双端队列）_java双向队列

1. Deque接口

Deque,双端队列，它的特点是既支持先进先出，也支持先进后出。
通过上面的图片可以看到，Deque继承了Queue，它在Queue的基础上进行了增强。
下面我们看一下Deque不同于Queue的特殊方法定义：

//在队列的前面插入元素，如果队列容量已满，则抛出异常
void addFirst(E e);

//在队列后面插入元素，如果队列已满，则抛出异常
void addLast(E e);

//如果队列容量允许，向队列前面添加元素，成功返回true， 否则返回false
boolean offerFirst(E e);

//如果队列容量允许，在队列后面添加元素，成功返回true， 否则返回false
boolean offerLast(E e);

//从队列中取出前面的元素并删除，如果队列为空，则抛出异常
E removeFirst();

//从队列中取出后面的元素并删除，如果队列为空，则抛出异常
E removeLast();

//从队列中取出前面的元素并删除，如果队列为空，则返回null
E pollFirst();

//从队列中取出后面的元素并删除，如果队列为空，则返回null
E pollLast();

//取出队列前面的元素但不删除,如果队列为空则抛出异常
E getFirst();

//取出队列后面的元素但不删除，如果队列为空则抛出异常
E getLast();

//取出队列前面的元素但不删除,如果队列为空，则返回null
E peekFirst();

//取出队列后面的元素但不删除，如果队列为空，则返回null
E peekLast();

//删除前面开始第一个和o相等的元素
boolean removeFirstOccurrence(Object o);

//删除后面开始第一个和o相等的元素
boolean removeLastOccurrence(Object o);

//这个方法和addFirst等价
void push(E e);

// 这个方法和removeFirst等价
E pop();

//返回一个倒序迭代器
Iterator<E> descendingIterator();
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

2.具体实现

从图中我们可以看到实现Deque接口的具体类有：ArrayDeque
通过之前的经验，我们也可以猜出也会有一个对应的AbstractDeque抽象类，提供了一些公用代码。

2.1 AbstractDeque（并不存在）

有时，根据经验也会判断失误，事实上，Jdk里并没有一个名为AbstractDeque的抽象类哈哈哈。
猜测归猜测，我们还是要实事求是的去验证。

不过，我们好像有了意外发现，除了ArrayDeque外，LinkedList也实现了Deque接口哦。

2.2 ArrayDeque

2.2.1 存储原理

transient Object[] elements; // non-private to simplify nested class access
1

通过阅读源码可以知道，ArrayDeque的存储结构也是基于数组实现的。
既然是基于数组，那么它一定会有相应的扩容机制：

private void doubleCapacity() {
    assert head == tail;
    int p = head;
    int n = elements.length;
    int r = n - p; // number of elements to the right of p
    int newCapacity = n << 1;
    if (newCapacity < 0)
        throw new IllegalStateException("Sorry, deque too big");
    Object[] a = new Object[newCapacity];
    System.arraycopy(elements, p, a, 0, r);
    System.arraycopy(elements, 0, a, r, p);
    elements = a;
    head = 0;
    tail = n;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

在ArrayDeque的扩容也很直接，直接doubleCapacity蛤，当容量满了后，直接将其容量扩为原来的两倍。

2.2.2 使用案例

public class ArrayDequeStudy {

    public static void main(String[] args) {
        FIFOTest();
        LIFOTest();
    }
    /**
     * 先进先出测试
     */
    public static void FIFOTest(){
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        System.out.println("将0-99按顺序放入队列中");
        for(int i=0;i<100;i++){
            queue.addLast(i);
        }
        System.out.println(queue.size());
        System.out.println("取出10个元素： ");
        for(int i=0;i<10;i++){
            System.out.print(queue.poll()+" ");
        }
        System.out.println("队列大小： ");
        System.out.println(queue.size());
    }
    /**
     * 后进先出测试
     */
    public static void LIFOTest(){
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        System.out.println("将0-99按顺序放入栈中");
        for(int i=0;i<100;i++){
            queue.addFirst(i);
        }
        System.out.println(queue.size());
        System.out.println("取出10个元素： ");
        for(int i=0;i<10;i++){
            System.out.print(queue.poll()+" ");
        }
        System.out.println("栈大小： ");
        System.out.println(queue.size());
    }
}
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

2.3 LinkedList

简单概述一下LinkedList的实现就是：
LinkedList是基于双向链表实现的一个链表数据结构实现的一个线程不安全的类。

2.3.1 存储原理

LinkedList 采用链表存储，所以，如果是在头尾插入或者删除元素不受元素位置的影响（add(E e)、addFirst(E e) addLast(E e)、removeFirst()、 removeLast()），时间复杂度为 O(1)，如果是要在指定位置 i 插入和删除元素的话（add(int index, E element)，remove(Object o)）， 时间复杂度为 O(n) ，因为需要先移动到指定位置再插入。但是不需要进行原有数据的整体移动处理，这相比于数组实现具有它自己的优势

需要注意的是： LinkedList不支持高效随机元素访问，ArrayList支持。 LinkedList则无需担心扩容问题，它的存储原理是需要的时候进行开辟空间，然后通过引用链接到一起，所以LinkedList的存储位置是碎片化，不连续的。
具体的实现请查阅源码。

2.3.2 使用案例

public class LinkedListStudy {
    public static void main(String[] args) {
        FIFOTest();
        LIFOTest();
    }
    /**
     * 先进先出测试
     */
    public static void FIFOTest(){
        LinkedList<Integer> queue = new LinkedList<>();
        System.out.println("将0-99按顺序放入队列中");
        for(int i=0;i<100;i++){
            queue.addLast(i);
        }
        System.out.println(queue.size());
        System.out.println("取出10个元素： ");
        for(int i=0;i<10;i++){
            System.out.print(queue.poll()+" ");
        }
        System.out.println("队列大小： ");
        System.out.println(queue.size());
    }

    /**
     * 后进先出测试
     */
    public static void LIFOTest(){
        LinkedList<Integer> queue = new LinkedList<>();
        System.out.println("将0-99按顺序放入栈中");
        for(int i=0;i<100;i++){
            queue.addFirst(i);
        }
        System.out.println(queue.size());
        System.out.println("取出10个元素： ");
        for(int i=0;i<10;i++){
            System.out.print(queue.poll()+" ");
        }
        System.out.println("栈大小： ");
        System.out.println(queue.size());
    }
}
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

3.代码地址

Java基础学习/src/main/java/Progress/exa27_7 · 严家豆/Study - 码云 - 开源中国 (gitee.com)