ArrayDeque如何比堆栈更快？

Question

根据javadoc，

当用作堆栈时，ArrayDeque类可能比Stack更快。

我不明白ArrayDeque怎么能比堆栈更快。假设堆栈是使用链接列表实现的，如下所示：

Push: Insert new element at the head, teamp->next = head; head = temp 
(where temp is the element to be inserted)
Pop: Remove the element from head, and make head = head->next

对于大量的元素，ArrayDeque将有调整大小的开销，在使用LinkedList实现的Stack中就不是这样。那么，ArrayDeque到底是如何比堆栈更快呢？

Answer 1

ArrayDeque是Java框架的一部分，并不是为了本质上是线程安全而编写的。

堆栈与一起随Java1.0一起出现，并且是用线程安全操作实现的(因为在当时这似乎是个好主意)。就时间而言，获取和释放线程锁是相对昂贵的，因此这些数据结构将比它们在JCF中的同胞慢得多。

Answer 2

因为大多数操作都不需要调整数组的大小，特别是当队列达到稳定的大小并且不再增长时。

每次添加项时，Stack都必须分配新对象，更新链接，等等。

ArrayDeque只需要在数组中放置一个对象并更新一个索引。

Answer 3

在我的经验中，仅在一种情况下，链接列表比数组列表更有效--在这种情况下，您经常希望在一次遍历中从列表中的随机点中添加或删除多个元素。在其他每一种情况下，数组列表通常更好--更快的查找、随机访问、更少的内存。如果ArrayDeque是基于数组的，那么很可能不需要为存储在其中的每个项分配额外的节点对象。

由于堆栈通常将项添加/移除到列表的末尾，基于数组的解决方案可能更有效。