Python Deque for Python Queue and Stack

Copy Link LinkedIn Message Facebook Email X

You've built your own custom stacks and queues and used Python's list data type to model the functionality of these Abstract Data Structures. You also learned that using a Python list isn't the best or most performant implementation of these data structures. You should avoid building your own implementations of Abstract Data Types if it isn't about the intellectual pursuit or job interview preparation.

So, what should you do if you want to ensure constant time for insertion and deletion in one of your programs? Python's got you covered!

In this lesson, you'll use collections.deque to model both stacks and queues. The abbreviation stands for "double-ended queue. You should pronounce it as "deck" to avoid confusing it with a queue's deque method.

Stacks With deque

Stacks have quite a few use cases in programming; for example, you can think of an Undo functionality in any text editing program. Usually, this functionality is built with a highly performant stack, which can quickly pop the most recent actions from the stack.

Choose the Base Data Structure

You might have already guessed it by now, but here's the raw truth: There's no pure stack in Python. But you can use other data structures as stacks:

1. list involves the least effort to use because it's built into the language itself. However, it's not thread-safe and doesn't give you the best performance.
2. collections.deque is the most performant and closest to a focused stack data structure, even though it still provides quite a few additional methods. While the methods you strictly need for a stack are thread-safe, not all methods that the class provides are.
3. queue.LifoQueue is a completely thread-safe implementation of a stack, but it comes with a performance overhead. You should use this if you write code that'll make use of parallelism, and you need to assure thread safety.

Use Deque

In most cases, your best choice for implementing a stack in Python is collections.deque:

from collections import deque

stack = deque()
stack.append(1)
stack.append(2)
stack.append(3)
print(stack)  # deque([1, 2, 3])
stack.pop()  # 3
stack.pop()  # 2
stack.pop()  # 1
print(stack)  # deque([])
stack.pop()  
# IndexError: pop from an empty deque

If you compare this code snippet with the one shown in a previous lesson where you used the built-in list to model a stack, you'll notice that it's almost exactly the same code. The method names for pushing to the stack (.append()) and popping from the stack (.pop()) are identical. Only now you are using a different object, namely a deque, that you first need to import from the collections module.

Using collections.deque over a list brings performance improvements for adding and removing items at the start and end of the collection but makes accessing items in the middle more costly. You've swapped trade-offs between these two data structures. Because stacks are meant to retrieve items only from the end of the collection, deque is a more optimal implementation of this data structure in Python than a list.

Queues With deque

Queues also have a lot of use cases in programming. For example, you can think of a set of tasks that your operating system needs to perform. There might be a lot of tasks coming in, but your system has limited resources. So, it can only tackle one task after another.

Info: Actual task queues in your operating system are usually modeled as priority queue. This is another data structure that is similar to a queue, but each element also has a priority.

Use Deque

If you've taken a look at the documentation on collections.deque, you'll notice that it mentions that deque is a generalization for both stacks and queues. If you look at the Python documentation for the class, you'll see that you can add and remove items from both ends of the collection.

That makes it possible to use deque also as a queue:

from collections import deque

queue = deque()
queue.append(1)
queue.append(2)
queue.append(3)
print(queue)  # deque([1, 2, 3])
queue.popleft()  # 1
queue.popleft()  # 2
queue.popleft()  # 3
print(queue)  # deque([])
queue.popleft()  # IndexError: pop from an empty deque

The code for using deque as a queue is almost identical to the code when using it as a stack data structure. The only difference in the code snippets above is that you use .popleft() instead of .pop() when removing items from the collection.

This approach is in line with the FIFO functionality of a queue, where the first item you add to the collection is the first you get out.

The performance gain compared to using a list to model a queue is significant in this case. Using Python lists as queues is very slow, but using a deque scales well also with bigger collections.

Note: If you're writing code that is meant to run in parallel, then there are even better options than deque. If you use threading, then you should work with queue.Queue. If you use multiprocessing, then you should use multiprocessing.Queue. Both of these implement all methods as thread-safe, atomic operations, which is important for parallelism.

Additional Resources

• Real Python: Common Python Data Structures
• Real Python: How to Implement a Stack

Summary: Python Deque for Python Queue and Stack

• collections.deque, list, queue.LifoQueue can all be used as the base data structure for your queue and stack
• collections.deque is usually a great choice for creating a Python Stack and Queue
• deque is a data type that can be imported from Python's standard library
• Using collections.deque over a list brings performance improvements for adding and removing items at the start and end of the collection
• Using collections.deque over a list makes accessing items in the middle more costly