我应该使用Python deque还是list作为堆栈？

Question

我应该使用Python deque还是list作为堆栈？

pythonpython-3.xlistpython-2.7data-structures

22

我想要一个可以用作栈的 Python 对象。使用 deque 还是 list 更好？无论元素个数是少还是多，是否有所区别？

- Casebash

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Reblochon Masque · Accepted Answer

根据您的应用和精确用例，您的结果可能会有所不同，但一般情况下，列表非常适合作为堆栈：

append 是O（1）

pop()是O（1）-只要您不从任意位置弹出；只从末尾 pop()。

对于这些操作，双端队列也是O（1），但需要从标准库导入一个模块，并且对于随机访问需要“ O（n）”时间。虽然可以提出使用原始列表，但除非针对特定应用程序，否则还是推荐使用双端队列。

更正：

根据Raymond Hettinger在两个列表和双端队列的C代码的主要作者的帖子中，双端队列似乎比列表表现略好：双端队列的pop()操作似乎具有优势。

In [1]: from collections import deque

In [2]: s = list(range(1000))      # range(1000) if python 2

In [3]: d = deque(s)

In [4]: s_append, s_pop = s.append, s.pop

In [5]: d_append, d_pop = d.append, d.pop

In [6]: %timeit s_pop(); s_append(None)
10000000 loops, best of 3: 115 ns per loop

In [7]: %timeit d_pop(); d_append(None)
10000000 loops, best of 3: 70.5 ns per loop

就性能而言，deque和list之间的真正区别如下：

对于appendleft()和popleft()操作，deque具有O(1)的速度，而list在insert(0, value)和pop(0)操作上的性能为O(n)。
由于其内部实现使用realloc()函数，因此列表的append性能因代码复杂程度而异。这是因为在简单代码中（realloc无需移动数据），它往往会给出过于乐观的时间；而在实际代码中（由于碎片化导致realloc需要移动所有数据），它会变得非常缓慢。相比之下，deque的append性能始终保持一致，因为它从不重新分配内存也不移动数据。