java ArrayDeque vs ArrayList 实现栈
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/29583171/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
ArrayDeque vs ArrayList to implement a stack
提问by Paul Boddington
The documentation for ArrayDequesays:
的文档ArrayDeque说：
This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue.
这个类在用作堆栈时可能比 Stack 更快，当用作队列时比 LinkedList 更快。
There is no mention of the difference between using an ArrayDequeas a stack and using an ArrayList. You can use an ArrayListas a stack as follows.
没有提到使用 anArrayDeque作为堆栈和使用ArrayList. 您可以将 anArrayList用作堆栈，如下所示。
list.add(object); // push
object = list.remove(list.size() - 1); // pop
I found that when I used an ArrayListin this way only, its performance is worse than ArrayDeque. What accounts for this difference? Surely, it can't just be the calls to size()? Internally, both ArrayListand ArrayDequeare implemented using an Object[]that is replaced by a larger array when required, so surely the performance should be about the same?
我发现当我只用ArrayList这种方式使用 an时，它的性能比ArrayDeque. 造成这种差异的原因是什么？当然，它不能只是调用size()? 在内部，ArrayList和ArrayDeque都使用Object[]在需要时由更大的数组替换的 来实现，那么性能肯定应该大致相同吗？
回答by Gerald Mücke
The main difference between both implementation is the resize strategy
两种实现的主要区别在于调整大小策略
ArrayListis resized to a new size ofoldCapacity + (oldCapacity >> 1), resulting in an increse of ~50%. The default capacity is 10, resulting in a capacities after resize of 15, 22, 33, 49, 73, 109, 163, 244, 366...ArrayDequeis always resized to a power of 2. On resize, the capacity is doubled. Starting with the default of 16, the resuling capacities after resize are 32, 64, 128, 256,...
ArrayList调整为新的大小oldCapacity + (oldCapacity >> 1)，导致增加约 50%。默认容量为 10，因此调整大小后的容量为 15、22、33、49、73、109、163、244、366...ArrayDeque始终调整为 2 的幂。调整大小时，容量加倍。从默认值 16 开始，resize 后的结果容量为 32, 64, 128, 256, ...
So the ArrayDeque reaches higher capacities with much less resize operation, which are costly because of array copy. I.e. to store 256 in default-sized ArrayList, it requires 9 resize calls, while the ArrayDeque only need 4. Array copy may be fast, but may also require a GC to free some space for the new data sets, in addition to the memory copy costs (where the ArrayDeque might also perform better due to it's alignment to power-of-2).
因此 ArrayDeque 以更少的调整大小操作达到更高的容量，由于数组复制而成本高昂。即将 256 存储在默认大小的 ArrayList 中，需要 9 次调整大小调用，而 ArrayDeque 只需要 4 次。 数组复制可能很快，但可能还需要 GC 为新数据集释放一些空间，除了内存复制成本（其中 ArrayDeque 也可能表现得更好，因为它与 2 的幂对齐）。
Both datastructures have best-case complexity of O(1) for push and pop through direct access on either head& tail(ArrayDequeue) respectively add and remove(Last) size(ArrayList)
两种数据结构都具有 O(1) 的最佳情况复杂度，用于通过直接访问head& tail(ArrayDequeue) 分别添加和移除 (Last) size(ArrayList)
