Python's deque: Implement Efficient Queues and Stacks

If you often work with lists in Python, then you probably know that they don’t perform fast enough when you need to pop and append items on their left end. Python’s collections module provides a class called deque that’s specially designed to provide fast and memory-efficient ways to append and pop item from both ends of the underlying data structure.

Python’s deque is a low-level and highly optimized double-ended queue that’s useful for implementing elegant, efficient, and Pythonic queues and stacks, which are the most common list-like data types in computing.

In this tutorial, you’ll learn:

• How to create and use Python’s deque in your code
• How to efficiently append and pop items from both ends of a deque
• How to use deque to build efficient queues and stacks
• When it’s worth using deque instead of list

To better understand these topics, you should know the basics of working with Python lists. It’ll also be beneficial for you to have a general understanding of queues and stacks.

Finally, you’ll write a few examples that walk you through some common use cases of deque, which is one of Python’s most powerful data types.

Free Download: Get a sample chapter from Python Tricks: The Book that shows you Python’s best practices with simple examples you can apply instantly to write more beautiful + Pythonic code.

Getting Started With Python’s deque

Appending items to and popping them from the right end of a Python list are normally efficient operations. If you use the Big O notation for time complexity, then you can say that they’re O(1). However, when Python needs to reallocate memory to grow the underlying list for accepting new items, these operations are slower and can become O(n).

Additionally, appending and popping items on the left end of a Python list are known to be inefficient operations with O(n) speed.

Since Python lists provide both operations with .append() and .pop(), they’re usable as stacks and queues. However, the performance issues you saw before can significantly affect 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 list.

Deques are sequence-like data types designed as a generalization of stacks and queues. They support memory-efficient and fast append and pop operations on both ends of the data structure.

Note: deque is pronounced as “deck.” The name stands for double-ended queue.

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 also thread safe and memory efficient. These features make deques particularly useful for creating custom stacks and queues in Python.

Deques are also the way to go if you need to keep a list of last-seen items because you can restrict the maximum length of your deques. If you do so, then once a deque is full, it automatically discards items from one end when you append new items on the opposite end.

Here’s a summary of the main characteristics 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
• Ensures fast, memory-efficient, and thread-safe pop and append operations on both ends

Creating deque instances is a straightforward process. 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 and input 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 supply 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.

Read the full article at https://realpython.com/python-deque/ »

---

[ Improve Your Python With 🐍 Python Tricks 💌 – Get a short & sweet Python Trick delivered to your inbox every couple of days. >> Click here to learn more and see examples ]

from Real Python
read more