Fun with deques in Python

In most python code, lists and dictionaries are the workhorses. The deque or double-ended queue, is a lesser known, but useful abstract data type from Python’s collections module. Deques are sequence containers so they support the well-known operations of the list, although with different performance tradeoffs.

The deque allows you to add and remove elements from both the head and the tail in constant time, unlike the list which only has constant time operations for adding and removing element at the tail of the list.

Actually, let’s stop for a moment and compare it to 2 related abstract data types, the queue and the stack.

The stack allow you to add and remove elements from one end and the queue allows adding at one end and removing from the other end. So stacks and queues are just degenerate forms of the the deque.

The deque is thread-safe, so the elements can be removed from both ends of the deque concurrently by several threads.

In addition to add and remove operation, the deque can rotate the elements clockwise and counter-clockwise in constant time. In the small snippet below, you can see the results we get in python (CPython) when we compare deque rotation to list rotation (with slices).

You can restrict the capacity of the deque in python using the maxlen parameter. When the elements are added to a full deque, elements at the opposite end are discarded.

Example 1:

You need to keep track of a customer’s navigation history and maintain a sequence of the last 5 viewed products.

Example 2:

You want to search a textfile for the occurrence of a pattern and return the matching line with the 5 preceding lines of context.

Summary — The deque is a handy weapon in your toolbelt. It can give you a performance boost if you predominantly add and remove elements from the ends of a sequence. Hope you found it helpful.