Deque

栈和队列

Deque的含义是“double ended queue”，即双端队列，它既可以当作栈使⽤，也可以当作队列使⽤。下表列出了Deque与Queue相对应的接⼝：参考 java Deque文档

ArrayDeque

Queue和Deque等效方法

Queue方法	Deque方法	说明
add(e)	addLast(e)	向队尾插⼊元素，失败则抛出异常
offer(e)	offerLast(e)	向队尾插⼊元素，失败则返回 false
remove()	removeFirst()	获取并删除队⾸元素，失败则抛出异常
poll()	pollFirst()	获取并删除队⾸元素，失败则返回 null
element()	getFirst()	获取但不删除队⾸元素，失败则抛出异常
peek()	peekFirst()	获取但不删除队⾸元素，失败则返回 null

Stack和Deque等效方法

Stack方法	Deque方法	说明
push(e)	addFirst(e)	向栈顶插⼊元素，失败则抛出异常
⽆	offerFirst(e)	向栈顶插⼊元素，失败则返回 false
pop()	removeFirst()	获取并删除栈顶元素，失败则抛出异常
⽆	pollFirst()	获取并删除栈顶元素，失败则返回 null
peek()	getFirst()	获取但不删除栈顶元素，失败则抛出异常
⽆	peekFirst()	获取但不删除栈顶元素，失败则返回 null

ArrayDeque是⾮线程安全的（not thread-safe），当多个线程同时使⽤的时候，需要⼿动同步；另外，该容器不允许放⼊ null 元素。
add

java

  public void addFirst(E e) {
    if (e == null)  // 不允许放入 null
      throw new NullPointerException();
    final Object[] es = elements;
    es[head = dec(head, es.length)] = e; // 下标是否越届
    if (head == tail) // 空间是否够用
      grow(1); // 扩容
  }

java8 doubleCapacity() java17 grow() 用于在需要时扩大数组的容量

java

  private void grow(int needed) {
    // overflow-conscious code
    final int oldCapacity = elements.length;
    int newCapacity;
    // Double capacity if small; else grow by 50%
    int jump = (oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1); // 如果容量较小(64)，则容量加倍；否则增长50%
    if (jump < needed || (newCapacity = (oldCapacity + jump)) - MAX_ARRAY_SIZE > 0) newCapacity = newCapacity(needed, jump); // 计算新容量，如果容量超过最大值，则返回最大值
    final Object[] es = elements = Arrays.copyOf(elements, newCapacity); // 创建一个新数组，大小为newCapacity
    // Exceptionally, here tail == head needs to be disambiguated
    if (tail < head || (tail == head && es[head] != null)) { // 判断head是否在tail之前，或者head等于tail且head位置不为空
      // wrap around; slide first leg forward to end of array
      int newSpace = newCapacity - oldCapacity; // 新容量减去旧容量
      System.arraycopy(es, head, es, head + newSpace, oldCapacity - head);   // 将旧数组中head到oldCapacity之间的元素复制到新数组中
      for (int i = head, to = (head += newSpace); i < to; i++) 
        es[i] = null; // 将新数组中head到head+newSpace之间的元素置空
    }
  }

总结当需要实现先进先出(FIFO)或者先进后出(LIFO)的数据结构时，可以考虑使⽤ ArrayDeque。以下是⼀些使⽤ ArrayDeque 的场景：管理任务队列：如果需要实现⼀个任务队列，可以使⽤ ArrayDeque 来存储任务元素。在队列头部添加新任务元素，从队列尾部取出任务进⾏处理，可以保证任务按照先进先出的顺序执⾏。实现栈：ArrayDeque 可以作为栈的实现⽅式，⽀持 push、pop、peek 等操作，可以⽤于需要后进先出的场景。实现缓存：在需要缓存⼀定数ᰁ的数据时，可以使⽤ ArrayDeque。当缓存的数据超过容量时，可以从队列头部删除最⽼的数据，从队列尾部添加新的数据。实现事件处理器：ArrayDeque 可以作为事件处理器的实现⽅式，⽀持从队列头部获取事件进⾏处理，从队列尾部添加新的事件。
ArrayDeque 是 Java 标准库中的⼀种双端队列实现，底层基于数组实现。与 LinkedList 相⽐，ArrayDeque 的性能更优，因为它使⽤连续的内存空间存储元素，可以更好地利⽤ CPU 缓存，在⼤多数情况下也更快。
因为ArrayDeque 的底层实现是数组，⽽ LinkedList 的底层实现是链表。数组是⼀段连续的内存空间，⽽链表是由多个节点组成的，每个节点存储数据和指向下⼀个节点的指针。因此，在使⽤LinkedList 时，需要频繁进⾏内存分配和释放，⽽ ArrayDeque 在创建时就⼀次性分配了连续的内存空间，不需要频繁进⾏内存分配和释放，这样可以更好地利⽤ CPU 缓存，提⾼访问效率。
现代计算机CPU对于数据的局部性有很强的依赖，如果需要访问的数据在内存中是连续存储的，那么就可以利⽤CPU的缓存机制，提⾼访问效率。⽽当数据存储在不同的内存块⾥时，每次访问都需要从内存中读取，效率会受到影响。
当然了，使⽤ ArrayDeque 时，数组复制操作也是需要考虑的性能消耗之⼀。
当 ArrayDeque 的元素数量超过了初始容量时，会触发扩容操作。扩容操作会创建⼀个新的数组，并将原有元素复制到新数组中。扩容操作的时间复杂度为 O(n)。不过，ArrayDeque 的扩容策略（当 ArrayDeque 中的元素数ᰁ达到数组容ᰁ时，就需要进⾏扩容操作，扩容时会将数组容ᰁ扩⼤为原来的两倍）
可以在⼀定程度上减少数组复制的次数和时间消耗，同时保证 ArrayDeque 的性能和空间利⽤率。
ArrayDeque 不仅⽀持常⻅的队列操作，如添加元素、删除元素、获取队列头部元素、获取队列尾部元素等。同时，它还⽀持栈操作，如 push、pop、peek 等。这使得 ArrayDeque 成为⼀种⾮常灵活的数据结构，可以⽤于各种场景的数据存储和处理。

Deque ​

栈和队列 ​

Deque

栈和队列