Double-ended queues, or deques, are available in Python as part of the collections module. At first glance, that sentence may have had a lot of words and concepts in them that may not be immediately clear. If that’s the case, don’t worry! By the end of this tutorial, you’ll be a pro at deques and know exactly when you may want to use one.
In this tutorial, you’ll learn how to use the Python collection’s module deque class. Deques allow you to use a list-like structure but have the benefit of adding and removing elements from both the front and the back in an efficient way.
By the end of this tutorial, you’ll have learned the following:
- What deques are and when they may be preferred over normal Python lists
- How to use a deque to add items to and remove items from the front of a list
- How to limit items in a Python deque
- How to rotate all items in a Python deque forward and backward
Table of Contents
What are Double-Ended Queues in Python
Python lists provide helpful methods for adding an item or multiple items to the end of a list. However, adding items to the front of a list is a bit more complicated. When working with lists, adding items to the front of list involves moving every element of a list back. This is, of course, a very memory-inefficient process. This is where deques come in, which provide memory-efficient ways to add and remove items from the front of a list-like structure.
When speaking in terms of Big O notation, adding items to the end of a list is of O(1) complexity. However, adding items to the front of a list is of O(n) complexity, since it involves updating each item in the list. With relatively small lists, this may not be an issue. However, as the size of your list grows, as does the time complexity required to complete it.
Similar to Python lists, deques in Python can contain any data type and are mutable. They support iteration and indexing. However, they don’t support slicing, nor do they support in-place sorting.
How to Create A Python Deque
To create a deque, we can instantiate it using the deque() function. Because the collections module is built into Python, we don’t need to install anything. Let’s see how we can instantiate an empty deque:
# Instantiating an Empty Deque in Python
import collections
empty = collections.deque()
print(empty)
# Returns: deque([])In many cases, you’ll see people import the function directly. Let’s see how we can do this and instantiate the deque with some items this time.
# Instantiating a Deque with Items
from collections import deque
queue = deque([1, 2, 3, 4, 5])
print(queue)
# Returns: deque([1, 2, 3, 4, 5])On the surface, this looks quite similar to a list. However, as we already know, the object provides a number of helpful methods. Let’s dive into how to add items to the front of a deque in the following section.
How to Add Items to the Front of a Deque in Python
To add items to the left side (the front) of a deque in Python, you can use either the .appendleft() or .extendleft() methods. Similar to their list counterparts, the methods add either a single item or multiple items to a deque’s front.
Let’s see how we can use the deque we previously created to prepend a single item using the .appendleft() method:
# Prepending an Item to a Deque in Python
from collections import deque
queue = deque([1, 2, 3, 4, 5])
queue.appendleft(0)
print(queue)
# Returns:
# deque([0, 1, 2, 3, 4, 5])We can see that by using the .appendleft() method, we’re able to add a single item. Even if we pass in a list of values, the list will simply be added as a single item.
If we wanted to add multiple items to the front of a list, we can use the .extendleft() and pass in another collection, such as list of items:
# Prepending Multiple Items to a Deque in Python
from collections import deque
queue = deque([1, 2, 3, 4, 5])
queue.extendleft([6, 7, 8])
print(queue)
# Returns:
# deque([8, 7, 6, 1, 2, 3, 4, 5])We can see that by using the .extendleft() method, that items are added to the left of the deque. It’s important to note that the items are added to the queue as they appear in the list. This means that the first item is added first, followed by the remaining items one by one. This emulates how a queue would work in real life.
How to Remove Items from the Front of a Deque in Python
Similar to adding items to the front of a deque, it’s easy to remove items from the front of a deque. Unlike adding items, we can only remove a single item at a time. This can be done using the .popleft() method. This method, like its .pop() counterpart, removes an item and returns it.
Let’s see how we can remove an item from the front of a deque using the .popleft() method:
# Remove a Single Item From the Front of a Deque
from collections import deque
queue = deque([1, 2, 3, 4, 5])
queue.popleft()
print(queue)
# Returns:
# deque([2, 3, 4, 5])We can remove more than one time by calling the method multiple times, We can even use the range function to iterate of the action multiple times. Let’s see how we can use a for loop to remove multiple items from the front of a deque in Python:
# Remove Multiple Items From the Front of a Deque
from collections import deque
queue = deque([1, 2, 3, 4, 5])
for _ in range(3):
queue.popleft()
print(queue)
# Returns:
# deque([2, 3, 4, 5])
# deque([3, 4, 5])
# deque([4, 5])We can see that by using a for loop, we were able to call the method multiple times. While there isn’t a built-in way to remove items from the left at once, using the .popleft() method and a for loop we can remove as many items as we need.
How to Limit the Number of Items a Python Deque Can Have
In some cases, you’ll want to limit the number of items that appear in a queue. This means that as more items are added to a deque, some items are dropped. In order to do this, we can use the maxlen= parameter to pass in a max number of items that the deque can hold.
Let’s see what this looks like:
# Creating a Deque with a Max Length
from collections import deque
queue = deque([1, 2, 3, 4], maxlen=5)
print(queue)
# Returns:
# deque([1, 2, 3, 4], maxlen=5)We can see that nothing has really changed, except that when we print the deque, it now includes the maximum length of that stack. Let’s see what happens when we now add items to the deque and how the max length is handled:
# Working with a Deque of a Max Length
from collections import deque
queue = deque([1, 2, 3, 4], maxlen=5)
for i in range(5, 8):
queue.appendleft(i)
print(queue)
# Returns:
# deque([5, 1, 2, 3, 4], maxlen=5)
# deque([6, 5, 1, 2, 3], maxlen=5)
# deque([7, 6, 5, 1, 2], maxlen=5)We can see that as we add the item 5 through 7, that they’re added to the left of the deque using the .appendleft() method. As the hit the maximum length of the deque, in this case 5, items on the other end of the stack are dropped. In this case, in the second iteration of the loop, the item 4 is dropped.
How to Rotate a Python Deque’s Items
Python deque’s also provide a great opportunity to rotate, or shuffle, items. This means that the items in the queue are pushed forward or backward a certain number of items. We can use the .rotate() method to pass in a positive or negative integer to rotate the items in the deque.
Let’s see what happens when we instantiate a deque with the numbers 1 through 5 and rotate it:
# Rotating a Deque's Items
from collections import deque
queue = deque([1, 2, 3, 4, 5])
queue.rotate(1)
print(queue)
# Returns:
# deque([5, 1, 2, 3, 4])We can see that by passing in the value of 1, that items are rotated to the right by one value. The last item is then moved to the beginning of the deque.
Similarly, we can increase the number of rotations by changing to a different value. Similarly, we can use a negative value to rotate in the opposite direction. Let’s see what happens when we pass in a value of -2:
# Rotating a Deque Using a Negative Value
from collections import deque
queue = deque([1, 2, 3, 4, 5])
queue.rotate(-2)
print(queue)
# Returns:
# deque([3, 4, 5, 1, 2])In this case, our deque’s items were rotated to the left by two items. This means that the items on the left were pushed to the end.
Conclusion
In this tutorial, you learned how to work with the deque object from the Python collections module. Deques were added to resemble stacks and queues, which are common abstract data types. You first learned why you may need a deque, such as when you need to easily append and remove items from the front of a list in Python. From there, you learned how to use the Python collections module to create your first deque.
Then, you learned how to create deques with items, as well as how to add a single item and multiple items to the front. From there, you learned how to remove a single item from the left of the deque, as well as creating a deque with a maximum number of items. Doing this allowed you to ensure that a queue doesn’t exceed a certain number of items. From there, you learned how to rotate a deque’s items, both in left and right directions.
Additional Resources
To learn more about related topics, check out the tutorials below: