ArrayDeque 和 java.util.Stack 和 MutableList 的区别是什么
ArrayDeque、java.util.Stack 和 MutableList（如 ArrayList）是实现栈的不同方式，它们有一些区别：
- 实现接口：
ArrayDeque实现了Deque接口，而java.util.Stack继承自Vector类，MutableList则是 Kotlin 标准库中的可变列表接口。 - 内部数据结构：
ArrayDeque使用循环数组（circular array）作为内部数据结构，而java.util.Stack内部使用数组（Array），MutableList则可以使用数组、链表或其他数据结构。 - 动态扩容：
ArrayDeque和MutableList都支持动态扩容，可以根据需要自动调整容量，而java.util.Stack不支持动态扩容，需要手动调整容量。 - 性能：
ArrayDeque在大多数操作上具有更好的性能，因为它使用了循环数组和更优化的实现。而java.util.Stack是一个遗留类，性能可能相对较差。MutableList的性能取决于具体实现。
综上所述，如果你想要使用性能较好且功能丰富的栈实现，推荐使用 ArrayDeque。如果你需要与现有的代码兼容或使用特定的接口，可以选择 java.util.Stack 或 MutableList。
ArrayDeque 怎么用循环数组实现的
ArrayDeque 使用循环数组（circular array）实现，它在内部维护了一个固定大小的数组来存储元素。下面是简单介绍 ArrayDeque 如何使用循环数组实现的一些关键点：
- 内部数组：
ArrayDeque内部有一个对象数组来存储元素，通常使用elements或array字段表示。 - 头部和尾部指针：
ArrayDeque有两个指针，分别指向头部和尾部。通常使用head和tail字段表示。 - 循环数组特性：
ArrayDeque的关键之处在于利用循环数组的性质。当头部或尾部指针到达数组的边界时，它们会回绕到数组的另一侧，形成循环效果。 - 扩容和缩容：当元素数量达到数组容量时，
ArrayDeque会自动扩容。在扩容时，会创建一个更大的数组，并将原始数组中的元素按照循环顺序复制到新数组中。类似地，当元素数量较少时，ArrayDeque也会自动缩容。 - 添加和移除元素：添加元素时，头部指针向前移动一个位置，并将元素放入头部位置。移除元素时，头部指针向后移动一个位置，并返回头部位置的元素。
通过这种方式，ArrayDeque 可以在不断添加和移除元素的过程中高效地利用数组空间，并保持循环数组的特性。这使得 ArrayDeque 在栈和队列等数据结构的实现中具有较高的性能和灵活性。
ArrayList 和 ArrayDeque 的区别
两种实现之间的主要区别在于调整大小的策略。
ArrayList 的调整大小策略是将其调整为 oldCapacity + (oldCapacity >> 1) 的新大小，增加了约 50%。默认容量为 10，在调整大小后的容量为 15、22、33、49、73、109、163、244、366…
ArrayDeque 总是调整为 2 的幂次方。在调整大小时，容量会加倍。从默认值 16 开始，调整大小后的容量为 32、64、128、256…
因此，ArrayDeque 达到了更高的容量，而调整大小的操作更少，这是因为数组的复制操作很耗费资源。例如，要在默认大小的 ArrayList 中存储 256，需要进行 9 次调整大小操作，而 ArrayDeque 只需要 4 次。数组的复制操作可能很快，但也可能需要 GC 来释放一些空间用于新的数据集，此外还需要进行内存复制操作（ArrayDeque 可能在这方面表现更好，因为它对齐到 2 的幂次方）。
这两种数据结构的最佳情况复杂度为 O(1)。ArrayList 的 push 和 pop 操作通过直接访问头部和尾部（ArrayDeque）来实现，而 add 和 removeLast 操作（ArrayList）则是通过直接访问大小来实现。