Deque in Python: collections-deque

About deque

It started because I wanted to implement a “Feeling Lucky” feature. To improve performance, I planned to use a queue. By chance I saw a discussion on Stack Overflow: “Efficiency of using a Python list as a queue”

Python lists have a pop method that can implement taking items from a queue, but performance is said to be mediocre. A highly upvoted answer said

You won't run out of memory using the list implementation, but performance will be poor.

So I’ll just use deque. This deque is also thread-safe. I’ll set aside the specific implementation for now and look at how it’s implemented when I have time. Here’s the official intro:

Deques support thread-safe, memory efficient appends and pops from either side of the deque with approximately the same O(1) performance in either direction.

Usage

Copying the docs wholesale feels too wordy… Using it is similar to a lsit, but note that a list can only append and pop on the far right, while a deque can appendleft and popleft on the left, and the time complexity is still O(1). Pretty nice~

References

• Official docs: https://docs.python.org/3/library/collections.html#collections.deque
• https://stackoverflow.com/questions/1296511/efficiency-of-using-a-python-list-as-a-queue
• https://zhuanlan.zhihu.com/p/32201189