// 基于本地 JDK 源码 (D:/1ForCode/JAVA_Source, java.base, 2024 版), java.util.ArrayDeque
public class ArrayDeque<E> extends AbstractCollection<E>
                           implements Deque<E>, Cloneable, Serializable
{
    // ...

    transient Object[] elements;    // 环形数组。不放元素的格子恒为 null, 且至少留一个 null 槽(在 tail 处)

    transient int head;             // 队头元素的下标; 队列为空时 head == tail

    transient int tail;             // 下一个入队元素要放的位置; elements[tail] 恒为 null

    public ArrayDeque() {
        elements = new Object[16 + 1];      // +1 就是那个永远的空槽, 用来区分"满"和"空"
    }

    public ArrayDeque(int numElements) {
        elements =
            new Object[(numElements < 1) ? 1 :
                       (numElements == Integer.MAX_VALUE) ? Integer.MAX_VALUE :
                       numElements + 1];    // 同样 +1
    }

    // 循环 +1: 走到数组尾就绕回 0。用 if 不用取模, 因为 % 是除法指令, 比一次分支慢得多
    static final int inc(int i, int modulus) {
        if (++i >= modulus) i = 0;
        return i;
    }

    // 循环 -1: 走到 0 之前就绕回数组尾
    static final int dec(int i, int modulus) {
        if (--i < 0) i = modulus - 1;
        return i;
    }

    public void addFirst(E e) {
        if (e == null)
            throw new NullPointerException();   // null 禁入, 原因见下面串讲
        final Object[] es = elements;
        es[head = dec(head, es.length)] = e;    // head 往左退一格, 放进去
        if (head == tail)
            grow(1);                            // 追尾了说明唯一的空槽被吃掉, 立刻扩容
    }

    public void addLast(E e) {
        if (e == null)
            throw new NullPointerException();
        final Object[] es = elements;
        es[tail] = e;                           // tail 本来就指着空槽, 直接放
        if (head == (tail = inc(tail, es.length)))
            grow(1);
    }

    public E pollFirst() {
        final Object[] es;
        final int h;
        E e = elementAt(es = elements, h = head);
        if (e != null) {                        // e == null 就是队列空, 直接返回 null
            es[h] = null;                       // 清引用, 帮 GC
            head = inc(h, es.length);
        }
        return e;
    }

    public E pollLast() {
        final Object[] es;
        final int t;
        E e = elementAt(es = elements, t = dec(tail, es.length));
        if (e != null)
            es[tail = t] = null;
        return e;
    }

    public E peekFirst() {
        return elementAt(elements, head);       // 空则拿到 null, 不抛异常
    }

    // 迭代器取元素用的加强版: 撞到 null 说明遍历途中队列被改了
    static final <E> E nonNullElementAt(Object[] es, int i) {
        @SuppressWarnings("unchecked") E e = (E) es[i];
        if (e == null)
            throw new ConcurrentModificationException();
        return e;
    }
}

// 基于本地 JDK 源码 (D:/1ForCode/JAVA_Source, java.base, 2024 版), java.util.ArrayDeque
    private void grow(int needed) {
        final int oldCapacity = elements.length;
        int newCapacity;
        // 小数组翻倍(+2), 大数组加 50%, 和 ArrayList 的 1.5 倍同一思路
        int jump = (oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1);
        if (jump < needed
            || (newCapacity = (oldCapacity + jump)) - MAX_ARRAY_SIZE > 0)
            newCapacity = newCapacity(needed, jump);    // 边界与溢出处理
        final Object[] es = elements = Arrays.copyOf(elements, newCapacity);
        // 特殊情况: 刚好在 grow 里 tail == head 需要靠 es[head] != null 消歧
        if (tail < head || (tail == head && es[head] != null)) {
            // 内容绕圈了: [head..旧末尾] 这一段要平移到新数组的末尾去
            int newSpace = newCapacity - oldCapacity;
            System.arraycopy(es, head,
                             es, head + newSpace,
                             oldCapacity - head);
            for (int i = head, to = (head += newSpace); i < to; i++)
                es[i] = null;                           // 旧位置清掉
        }
    }

为什么当栈用比 Stack 好:Stack 继承 Vector,每个方法都挂着 synchronized,单线程刷题白付锁开销;而且 Vector 的 `get(i)`、`insertElementAt` 全部漏进 Stack 接口,栈语义根本关不住。
为什么当队列用通常比 LinkedList 好:LinkedList 每个元素一个 Node 对象(自身引用 + prev + next 三个指针的内存),遍历时内存跳跃;ArrayDeque 连续存储,一次缓存行装好几个元素。