Should I use a Python deque or list as a stack? [duplicate]

Your mileage may vary according to your application and precise use case, but in the general case, a list is well suited for a stack:

append is O(1)

pop() is O(1) - as long as you do not pop from an arbitrary position; pop() only from the end.

Deques are also O(1) for these operations, but require importing a module from the standard library, require 'O(n)' for random access. An argument could be made to prefer using vanilla lists though, unless for specific applicatins.

Correction:

from this post by Raymond Hettinger, a principal author of the C code for both list and deque, it appears that deques may perform slightly better than lists: The pop() operation of deques seem to have the advantage.

In [1]: from collections import dequeIn [2]: s = list(range(1000))      # range(1000) if python 2In [3]: d = deque(s)In [4]: s_append, s_pop = s.append, s.popIn [5]: d_append, d_pop = d.append, d.popIn [6]: %timeit s_pop(); s_append(None)10000000 loops, best of 3: 115 ns per loopIn [7]: %timeit d_pop(); d_append(None)10000000 loops, best of 3: 70.5 ns per loop

the real differences between deques and list in terms of performanceare:

Deques have O(1) speed for appendleft() and popleft() while lists haveO(n) performance for insert(0, value) and pop(0).
List appendperformance is hit and miss because it uses realloc() under the hood.As a result, it tends to have over-optimistic timings in simple code(because the realloc doesn't have to move data) and really slowtimings in real code (because fragmentation forces realloc to move allthe data). In contrast, deque append performance is consistent becauseit never reallocs and never moves data.