循环数组Circular Array / Ring Buffer循环数组是ArrayDeque的核心数据结构。它的精髓在于用固定长度的数组通过下标绕回实现队列的两端操作避免数据搬移。一、普通数组做队列的问题假设用普通数组实现队列容量为 8队头在索引 0队尾在索引 5 [10, 20, 30, 40, 50, 60, _, _] 0 1 2 3 4 5 6 7出队一个元素删除 10如果要求数据连续就得把后面所有元素往前挪[20, 30, 40, 50, 60, _, _, _] ← 所有元素左移O(n)同样入队时如果在尾部也可能需要扩容和搬移。问题根源下标只能单调增长数组空间被一次性消耗。二、循环数组的核心思想关键点下标到达数组末尾后不越界而是绕回到 0。索引增长: 0 → 1 → 2 → ... → 7 → 0 → 1 → 2 ... 绕回物理上是一个线性数组逻辑上把它弯成一个环0 7 1 6 2 5 3 4这样队头、队尾都可以在这个环上自由移动删除元素时不需要搬移任何数据只需要移动 head 指针。三、两个指针head 和 tailArrayDeque内部维护两个关键字段transientObject[]elements;// 存储元素的数组transientinthead;// 队头元素的下标transientinttail;// 下一个入队位置的下标约定head指向队头元素下一个出队的位置tail指向下一个可插入的位置队尾的下一个空位数组始终有一个空位不用后面解释四、环形下标的计算这是循环数组最核心的公式。前进/后退时用按位与实现取模前提是容量为 2 的幂// 前进一格tail 后移tail(tail1)(elements.length-1);// 后退一格head 前移用于 addFirsthead(head-1)(elements.length-1);为什么能用代替%当length是 2 的幂如 8 2³length - 1 7 0b0111。(tail 1) 7: 当 tail1 8 → 1000 0111 0000 0 ✅ 绕回 当 tail1 9 → 1001 0111 0001 1 ✅ 当 tail1 3 → 0011 0111 0011 3 ✅而head - 1在 head0 时会变成 -1在补码中 -1 0xFFFFFFFF与 7 按位与得到 7(-1) 7 0xFFFFFFFF 0x7 7 ✅ 从 0 绕回到末尾这就是为什么ArrayDeque容量必须是 2 的幂。位运算比取模快得多且天然处理负数下标。五、一个完整的例子容量 8初始: head0, tail0 [_, _, _, _, _, _, _, _] addLast(A): elements[0]A, tail(01)71 [A, _, _, _, _, _, _, _] ↑head ↑tail addLast(B): elements[1]B, tail2 [A, B, _, _, _, _, _, _] ↑head ↑tail addLast(C): elements[2]C, tail3 [A, B, C, _, _, _, _, _] ↑head ↑tail pollFirst(): 返回 A, head(01)71 [_, B, C, _, _, _, _, _] ↑head ↑tail addLast(D): elements[3]D, tail4 [_, B, C, D, _, _, _, _] ↑head ↑tail现在把 tail 推到末尾绕回addLast(E): elements[4]E, tail5 addLast(F): elements[5]F, tail6 addLast(G): elements[6]G, tail7 [_, B, C, D, E, F, G, _] ↑head ↑tail addLast(H): elements[7]H, tail(71)70 ← 绕回 [_, B, C, D, E, F, G, H] ↑tail ↑head此时 tail0head1队列逻辑顺序是B C D E F G H物理上从索引 1 一直排到索引 7 再到索引 0。tail跑到了head前面。六、判断空和满为什么留一个空位有了 head 和 tail怎么区分空和满空: head tail 满: head tail ← 冲突了如果允许数组全满空和满的状态完全一样无法区分。解决方案永远留一个空槽数组最多存length - 1个元素。// 判空headtail// 判满tail 前进一格就撞上 head((tail1)(elements.length-1))head上面例子中H 入队后head1, tail0检查满(01)7 1 head→ 满此时实际存了 7 个元素B~H数组 8 格中空了索引 0tail 位置……等等这里 tail0 指向的就是那个空槽。所以容量为 8 的数组最多装 7 个元素触发扩容。七、扩容doubleCapacity当判满成立时ArrayDeque会申请一个两倍大小的新数组仍然是 2 的幂把旧数组的元素按逻辑顺序复制过去让 head 归到索引 0更新 head0, tail原元素个数privatevoiddoubleCapacity(){intnelements.length;intrn-head;// head 右边的元素个数intnewCapacityn1;// 翻倍Object[]anewObject[newCapacity];// 先复制 head 到末尾这一段System.arraycopy(elements,head,a,0,r);// 再复制 0 到 tail 这一段System.arraycopy(elements,0,a,r,head);elementsa;head0;tailn;}用上面的例子head1, tail0元素 B~H旧: [_, B, C, D, E, F, G, H] head1 新: [B, C, D, E, F, G, H, _, _, _, _, _, _, _, _, _] ↑head0 ↑tail7这样逻辑顺序就拉直了后续操作可以继续。八、性能与特点操作复杂度说明addFirst/addLast均摊 O(1)扩容时单次 O(n)均摊后 O(1)pollFirst/pollLastO(1)只移动指针不搬移数据peekFirst/peekLastO(1)直接读下标随机访问get(i)O(1)通过(head i) mask定位对比 LinkedList空间循环数组连续内存缓存友好LinkedList 每个节点额外两个指针内存碎片多。速度ArrayDeque通常比LinkedList快尤其在大数据量下。限制ArrayDeque不允许null元素因为要用 null 表示空槽。与%取模的对比ArrayDeque用 (length-1)前提是长度 2 的幂速度极快。如果容量不是 2 的幂比如某些自定义环形缓冲区就得用(i 1) % n或者用条件判断i (i 1 n) ? 0 : i 1。九、一句话总结循环数组 一个线性数组 两个会绕圈的下标。它把数组首尾相连成环删除和插入只需移动指针无需搬移数据用 2 的幂容量 位与运算实现 O(1) 的环形寻址用留一个空槽区分空与满满了就翻倍扩容并拉直。这正是ArrayDeque能同时高效支持栈push/pop和队列offer/poll两种用法的底层原因。