Implement Efficient Queues Using Python’s collections Module

Create custom queues using deque in Python’s collections module

The collections module in Python implements some specialized container data types in addition to built-in containers, dictionary, list, set, and tuple. deque is one of them. Using deque we can create our custom queue data structure efficiently.

In one of my previous articles, I discussed the simplest way to implement a queue in Python using lists. To grasp a proper understanding of how a queue works you can read this article.

Today I will discuss a more efficient approach to creating a custom queue using Python’s collections module. This module provides us with the following container data types:

deque will help us to implement efficient and fast queues.

The Basics of deque

To use deque we need to import it from the collections module:

from collections import deque

Creating a deque is fairly straightforward:

Output:

deque([])
deque([1, 2, 3, 4, 5])
deque(['H', 'e', 'l', 'l', 'o', ' ', 'w', 'o', 'r', 'l', 'd'])
deque([('one', 1), ('two', 2), ('three', 3)])

deque stands for double-ended queue. That means we can perform pop() and append() operations on both ends of the sequence. Let’s see how we can perform pop() and append() operations in a deque:

Output:

1
2
deque([10, 20, 3, 4, 5])
5
4
deque([10, 20, 3, 100, 200])

This knowledge should be enough to implement our custom queue.

Creating a Custom Queue Class Using deque

A simple queue may have the following operations:

• enQueue(). Adding items to the queue
• deQueue(). Removing items from the queue
• Retrieving the front element of the queue
• Retrieving the rear element of the queue

We can modify append(), and popleft() to implement enQueue(), and deQueue() operations in a queue respectively.

We can add the following additional functionalities to the Queue class:

• Returning the length of the queue
• Supporting membership check
• Supporting iterations on the queue
• Providing a user-friendly string representation of the queue

Here is the complete Queue class:

Let’s summarize the features of the Queue class:

• enQueue() will add elements to the queue
• deQueue() will remove elements from the queue
• frontElement() will return the front element of the queue
• rearElement() will return the rear element of the queue
• __len__() will return the length of the queue
• __iter__() will allow iterations on the queue
• __reveresed__() will allow backward iterations
• __contains__() will allow membership check in the queue
• __repr__() will provide a user-friendly string representation of the queue

Using the Queue Class

We can use the Queue class like the following:

Output:

Queue([])
Queue([1, 2, 3, 4, 5])
Queue([3, 4, 5])
3
False
True
3
4
5

Conclusion

deque is implemented based on doubly-linked-list. It is optimized for operations on either side of a sequence. On the other hand, list is implemented based on array. Pop and append operations are faster, and more memory-efficient in deque than list. So implementing queues using deque is more efficient.

That’s it for today. I hope you find this article helpful. Thanks for reading.

References

• https://realpython.com/python-deque/
• https://docs.python.org/3/library/collections.html