ArrayDeque比Stack更快的原因是什么？

Question

根据Javadoc，

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

我不明白ArrayDeque如何比stack更快。假设stack是使用链表实现的，如下所示：

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究竟比Stack快在哪里呢？

- Gaurav

Answer 1

ArrayDeque是Java集合框架的一部分，没有被写成固有的线程安全。

Stack、Vector和Hashtable与Java 1.0一起发布，并使用线程安全操作实现（因为当时看起来很不错）。获取和释放线程锁在时间上相对较昂贵，因此这些数据结构比JCF中的同类结构要慢得多。

- Steve C

Answer 2

由于大多数操作不需要数组调整大小，特别是一旦队列达到稳定大小并且不再增长时。

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

`ArrayDeque`只需要将对象放入数组中并更新索引。

- Tim B

---

这个说法正确吗？考虑到Java堆栈实际上没有使用任何链式结构，只是由OP假设的。 - ptntialunrlsd

Answer 3

根据我的经验，在仅需要在单次遍历列表时频繁添加或删除多个元素的情况下，链表比数组列表更有效。在其他情况下，数组列表通常更好 - 查找速度更快，随机访问和内存占用更少。如果ArrayDeque基于一个数组，则可能不需要为其中存储的每个项分配额外的节点对象。

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

- tofarr

---

实际上，我认为仅在列表条件中随机选取点仍然不够具体。除非您已经在遍历列表，否则ArrayList可能仍然比LinkedList更快，因为将修改后的元素向上随机排列的速度不比仅查找LinkedList中的元素所需的列表扫描要慢多少。基本上，在搜索列表时修改列表或进行大量操作位于列表头部是LinkedList具有优势的地方。 - Tim B

@Tim B - 我已经更新了我的答案以反映这一点 - 你是正确的。 - tofarr

Answer 4

使用ArrayDeque而不是Stack有多个原因，因为ArrayDeque是一个双端队列，实现为数组。因此，它的增长速度相对较快。如果您不打算使用同步堆栈，则ArrayDeque可能比Stack更好，因为Stack是线程安全的（因此较慢）。ArrayDeque还具有更好的参考位置。

- Kamal

Answer 5

关键词是“likely”。如果发生调整大小，则可能会变慢，但堆栈不太可能增长那么多。

- Kayaman

Answer 6

只要你的主要操作不是“包含”搜索或“批量插入”等，与其他数据结构相比，数组将更快。 “更快”的部分始终取决于使用情况。平均而言，即如果您采用平均时间，ArrayDeque将比Stack更快。

- Girish