Python’s deque: Implement Efficient Queues and Stacks

You can use Python’s deque for efficient appends and pops at both ends of a sequence-like data type. These capabilities are critical when you need to implement queue and stack data structures that operate efficiently even under heavy workloads.

In this tutorial, you’ll learn how deque works, when to use it over a list, and how to apply it in real code.

By the end of this tutorial, you’ll understand that:

• deque internally uses a doubly linked list, so end operations are O(1) while random indexing is O(n).
• You can build a FIFO queue with .append() and .popleft(), and a LIFO stack with .append() and .pop().
• deque supports indexing but doesn’t support slicing.
• Passing a value to maxlen creates a bounded deque that drops items from the opposite end when full.
• In CPython, .append(), .appendleft(), .pop(), .popleft(), and len() are thread-safe for multithreaded use.

Up next, you’ll get started with deque, benchmark it against list, and explore how it shines in real-world use cases, such as queues, stacks, history buffers, and thread-safe producer-consumer setups.

Get Started With Python’s deque

Appending to and popping from the right end of a Python list are efficient operations most of the time. Using the Big O notation for time complexity, these operations are O(1). However, when Python needs to reallocate memory to grow the underlying list to accept new items, these operations slow down and can become O(n).

In contrast, appending and popping items from the left end of a Python list are always inefficient and have O(n) time complexity.

Because Python lists provide both operations with the .append() and .pop() methods, you can use them as stacks and queues. However, the performance issues you saw before can significantly impact the overall performance of your applications.

Python’s deque was the first data type added to the collections module back in Python 2.4. This data type was specially designed to overcome the efficiency problems of .append() and .pop() in Python lists.

A deque is a sequence-like data structure designed as a generalization of stacks and queues. It supports memory-efficient and fast append and pop operations on both ends.

Append and pop operations on both ends of a deque object are stable and equally efficient because deques are implemented as a doubly linked list. Additionally, append and pop operations on deques are thread-safe and memory-efficient. These features make deques particularly useful for creating custom stacks and queues in Python.

Deques are also a good choice when you need to keep a list of recently seen items, as you can restrict the maximum length of your deque. By setting a maximum length, once a deque is full, it automatically discards items from one end when you append new items to the opposite end.

Here’s a summary of the main features of deque:

• Stores items of any data type
• Is a mutable data type
• Supports membership operations with the in operator
• Supports indexing, like in a_deque[i]
• Doesn’t support slicing, like in a_deque[0:2]
• Supports built-in functions that operate on sequences and iterables, such as len(), sorted(), reversed(), and more
• Doesn’t support in-place sorting
• Supports normal and reverse iteration
• Supports pickling with pickle
• Supports fast, memory-efficient, and thread-safe pop and append operations on both ends

To create deques, you just need to import deque from collections and call it with an optional iterable as an argument:

>>> from collections import deque

>>> # Create an empty deque
>>> deque()
deque([])

>>> # Use different iterables to create deques
>>> deque((1, 2, 3, 4))
deque([1, 2, 3, 4])

>>> deque([1, 2, 3, 4])
deque([1, 2, 3, 4])

>>> deque(range(1, 5))
deque([1, 2, 3, 4])

>>> deque("abcd")
deque(['a', 'b', 'c', 'd'])

>>> numbers = {"one": 1, "two": 2, "three": 3, "four": 4}
>>> deque(numbers.keys())
deque(['one', 'two', 'three', 'four'])

>>> deque(numbers.values())
deque([1, 2, 3, 4])

>>> deque(numbers.items())
deque([('one', 1), ('two', 2), ('three', 3), ('four', 4)])

If you instantiate deque without providing an iterable as an argument, then you get an empty deque. If you provide an iterable, then deque initializes the new instance with data from it. The initialization goes from left to right using deque.append().

The deque initializer takes the following two optional arguments:

1. iterable holds an iterable that provides the initialization data.
2. maxlen holds an integer number that specifies the maximum length of the deque.

As mentioned previously, if you don’t supply an iterable, then you get an empty deque. If you provide a value to maxlen, then your deque will only store up to maxlen items.

Finally, you can also use unordered iterables, such as sets, to initialize your deques. In those cases, you won’t have a predefined order for the items in the final deque.