浅谈java中集合框架-双端队列 deque_java双向队列deque

deque（double-ended queue，双端队列）是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出

实现：

Deque表示双端队列。双端队列是在两端都可以进行插入和删除的队列。
1. LinkedList
新建一个双端队列：Deque deque = new LinkedList();
2.ArrayDeque
新建一个双端队列：Deque deque = new ArrayDeque();
二者的区别：
ArrayDeque 比 LinkedList 更优秀
因为 ArrayDeque 在插入、删除和访问元素时都具有常数时间的时间复杂度 O(1)， ArrayDeque 内部实现了一个循环数组，可以在队列的两端高效地插入和删除元素。队列的两端都有空余空间时，插入和删除操作只需要修改数组的指针，时间复杂度是 O(1)；当队列的两端空间不足时，需要进行扩容操作，但由于 ArrayDeque 内部实现了循环数组，扩容操作只需要把原来的数组复制到新的更大的数组中即可，时间复杂度也是 O(1)。ArrayDeque 不安全
而 LinkedList 在访问元素时的时间复杂度是 O(n)，插入和删除元素的时间复杂度是 O(1)，安全的
如果一直是插入，没有查询，则LinkedList更适合，因为不需要扩容 ，如果涉及到查询就选择ArrayDeque

安全集合类：
3. ConcurrentLinkedDeque
Deque deque = new ConcurrentLinkedDeque<>(); 基于链表实现的双端并发队列，支持高效的插入、删除和访问操作，并且可以在多线程环境下安全地使用。
4.LinkedBlockingDeque
Deque deque= new LinkedBlockingDeque<>(); 基于链表实现的阻塞队列（不是双端队列，单端队列，只是为了实现deque接口，内部做了些转化），支持高效的插入、删除和访问操作，并且在队列为空或满时可以阻塞等待。（LinkedBlockingDeque 内部使用了锁和条件变量来实现线程同步和阻塞等待，以保证线程安全）

区别：1.线程安全性：ConcurrentLinkedDeque 是线程安全的，支持多线程并发操作，
而 LinkedBlockingDeque 也是线程安全的，但是它的实现方式是阻塞式的，即当队列为空或满时，操作会被阻塞，等待条件满足后再执行（LinkedBlockingDeque 支持阻塞操作，当队列为空时，从队头获取元素或者向队尾插入元素的操作会被阻塞，直到队列中有元素可用；当队列满时，向队尾插入元素的操作也会被阻塞，直到队列中有空闲空间。）因此它的性能可能会受到影响。
2.ConcurrentLinkedDeque 的实现方式是基于无锁算法实现的，因此在多线程环境下具有较好的性能和可扩展性。而 LinkedBlockingDeque 的实现方式是基于锁实现的，并且需要使用两个锁来实现阻塞操作和线程安全，因此在高并发环境下可能会出现性能瓶颈

5.PriorityDeque：
基于堆实现的优先级队列，支持按照元素的优先级进行插入和删除操作。 除了此类，其他都支持双端操作，因为都以上几种都实现了deque的双端操作方法

常用方法

：

1. size()：返回链表中元素的数量。
   2.判断是否为空： deque.isEmpty()
   3.增：deque.offerFirst()， deque.offerLast();//从头添加和尾部添加 如果队列已满，则会返回false，表示添加失败
   deque.addFirst() deque.addFirst() /从头添加和尾部添加 如果队列已满，则会抛出异常（IllegalStateException）。
   4.删：deque.pollFirst()， deque.pollLast()//从头添加和尾部出队 如果队列为空，则会返回null，表示没有元素可供移除
   deque.removeFirst() deque.removeLast() //从头添加和尾部出队 如果队列为空，则会抛出异常（NoSuchElementException）
   查：deque.peekFirst(), deque.peekLast()//查看头添加和尾部元素 如果队列为空，则会返回null，表示没有元素可供获取。
   deque.getFirst() deque.getLast() //查看头添加和尾部元素 如果队列为空，则会抛出异常（NoSuchElementException）。
   高级用法：
   5.deque.removeFirstOccurrence()
   6.deque.removeLastOccurrence()
   分别代表删除第一次出现的该元素和最后一次出现的该元素，返回true则执行成功否则失败。