ArrayDeque 如何比 stack 快？

stack java arraydeque

2022-09-02 03:03:06

根据javadoc，

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

我不明白 ArrayDeque 怎么可能比 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究竟比堆栈快多少呢？

答案 1

ArrayDeque 是 Java Collections Framework 的一部分，它不是为固有的线程安全而编写的。

Stack与Vector和Hashtable一起随Java 1.0一起实现，并使用线程安全操作实现（因为当时这似乎是一个好主意）。获取和释放线程锁在时间上相对昂贵，因此这些数据结构将比JCF中的同胞慢得多。

答案 2

因为大多数操作不需要调整数组大小，尤其是在队列达到稳定大小并且不再增长时。

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

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