Python’s Deque: How to Easily Implement Queues and Stacks

If you use Python, you're probably familiar with lists, and you probably use them a lot, too. They're great data structures with many helpful methods that allow the user to modify the list by adding, removing, and sorting items. However, there are some use cases when a list may look like a great choice, but it just isn't. 

In this article, we'll cover how the deque() function from the collections module can be a much better choice when you need to implement queues and stacks in Python.

To follow along with this article, we assume that you have some experience with Python programming, using lists and its methods, as most of them can be extrapolated for the use of collections.deque.

Queues and Stacks

First things first: let's understand the concepts of queues and stacks before we get into the collections module.

Queues

A queue is a data structure that stores items in a First-in-First-out (FIFO) manner. That is, the first item added to the queue will be the first item removed from the queue. 

Let's say, for instance, that you're adding songs to a queue in your favorite music player. You haven't started yet, so your queue is empty. You then add three songs: song_1, song_2, and song_3, in this order. Now your queue looks like this:

queue = ['song_1', 'song_2', 'song_3']

You then start playing the song in the queue. The first one played and moved out of the queue is the first one added: song_1— thus, first in, first out. Following this rule, if you play a couple of songs and then add three more, this would be your queue:

queue = ['song_3', 'song_4', 'song_5', 'song_6']

Stacks

A stack is a data structure that stores items in a Last-in-First-out (LIFO) manner. That is, the last item added to the stack will be the first item removed from the stack.

A classic example of a stack is a pile of plates. Let's say you had a few friends over for dinner and used five plates. After dinner, you pile up those five plates in the sink. So you'd have this stack:

stack = ['plate_1', 'plate_2', 'plate_3', 'plate_4', 'plate_5']

When you start to wash the dishes, you start from the top of the pile, plate_5, which means last in, first out. So after you wash three plates, a friend brings another one that she used for dessert and puts it on the top of the pile. Your stack now looks like this:

stack = ['plate_1', 'plate_2', 'plate_6']

This means that plate_6 would be the next one to be washed.

Why Not Lists?

Now that we understand the concepts of queues and stacks, it may look like lists would be just fine to implement these structures in Python. After all, they were used to represent the queue of songs and the stack of plates above, right? Well, not so much.

Lists are not the best data structure for queues or stacks in Python for a couple of reasons. First, lists are not thread-safe, which means that if a list is being accessed and modified by multiple threads simultaneously, things might not go well, and you'll probably end up with inconsistent data or an error message.

Also, lists are not efficient when you need to insert or delete an element from its left end. If you use list.append() to insert an element in the right end or list.pop() to delete the rightmost element, the list will perform just fine. However, when you try to perform these operations at the left end, the list needs to shift all other elements to the right, which means that the size of the list affects the time it takes to perform such operations, resulting in poor performance.

Using collections.deque

The deque object from collections is a list-like object that supports fast append and pops from both sides. It also supports thread-safe, memory-efficient operations, and it was specifically designed to be more efficient than lists when used as queues and stacks.

The name deque is short for double-ended queue and it's pronounced like "deck."

Creating a deque Object

The deque takes an iterable as an argument that will become a deque object. If none is passed, it will be empty:

from collections import deque

queue = deque()
print(queue)

deque([])

But we can also pass any iterable to deque. Below, we can see how to transform lists, tuples, sets, keys, and values from dictionaries into a deque object:

songs_list = ['song_1', 'song_2', 'song_3']
songs_tuple = ('song_1', 'song_2', 'song_3')
songs_set = {'song_1', 'song_2', 'song_3'}
songs_dict = {'1': 'song_1', '2': 'song_2', '3': 'song_3'}

deque_from_list = deque(songs_list)
deque_from_tuple = deque(songs_tuple)
deque_from_set = deque(songs_set)
deque_from_dict_keys = deque(songs_dict.keys())
deque_from_dict_values = deque(songs_dict.values())

print(deque_from_list)
print(deque_from_tuple)
print(deque_from_set)
print(deque_from_dict_keys)
print(deque_from_dict_values)

deque(['song_1', 'song_2', 'song_3'])
deque(['song_1', 'song_2', 'song_3'])
deque(['song_3', 'song_1', 'song_2'])
deque(['1', '2', '3'])
deque(['song_1', 'song_2', 'song_3'])

So now that we have our deque object initialized, we can use the append and pop methods to insert and delete items from the right end:

queue = deque(songs_list)
print(queue)

queue.append('song_4')
print(queue)

queue.pop()
print(queue)

deque(['song_1', 'song_2', 'song_3'])
deque(['song_1', 'song_2', 'song_3', 'song_4'])
deque(['song_1', 'song_2', 'song_3'])

Notice that song_4 was inserted at the rightmost position and then deleted.

Appending and Deleting from the Left

One of the biggest advantages of deque over a list is the possibility to append and delete items from the left end.

While in a list we use the insert() method, with a deque, we can use the appendleft() method. Here's how each one works:

songs_list.insert(0, 'new_song')
print(songs_list)

queue.appendleft('new_song')
print(queue)

['new_song', 'song_2', 'song_3']
deque(['new_song', 'song_1', 'song_2', 'song_3'])

The same goes for deleting items at the left end. In a list, we use the pop() method with the index zero as an argument, indicating that the first item should be deleted. In a deque, we have the popleft() method to perform this task:

songs_list.pop(0)
print(songs_list)

queue.popleft()
print(queue)

['song_2', 'song_3']
deque(['song_1', 'song_2', 'song_3'])

As mentioned earlier, a deque object is much more efficient for these operations at the left end, especially as the size of the queue increases.

According to the concepts of queues and stacks, we use the popleft() method to remove the first inserted item from the list. We append from the right and remove from the left: first in, first out.

However, both pop() and popleft() methods will raise an error if the queue is empty. It's a good practice to have these methods inside try and except clauses to prevent errors. We'll see an example later in this article.

Finally, we can also use the extendleft() method to insert multiple elements into the queue. This method takes an iterable. Here's an example:

queue.extendleft(['new_song_1', 'new_song_2'])
print(queue)

deque(['new_song_2', 'new_song_1', 'song_1', 'song_2', 'song_3'])

Built-in Functions and Iterations on Queues

Just like lists, tuples, and sets, the deque object also supports Python's built-in functions.

For example, we can use len() to check the size of a deque:

print(len(queue))

5

We can use the sorted() function to sort a deque:

print(sorted(queue))

['new_song_1', 'new_song_2', 'song_1', 'song_2', 'song_3']

And we use the reversed() function to invert the order of the items inside a deque object:

print(deque(reversed(queue)))

deque(['song_3', 'song_2', 'song_1', 'new_song_1', 'new_song_2'])

The max() and min() functions are also supported:

new_queue = deque([1, 2, 3])
print(max(new_queue))
print(min(new_queue))

3
1

Of course, we can iterate through the queue:

for song in queue:
    print(song)

new_song_2
new_song_1
song_1
song_2
song_3

Implementing a Queue

Now, let's put a simplified version of a queue into practice. We'll keep using the example of a queue of songs, which means our queue will keep receiving new songs as it plays the oldest songs in line and then removes them. Although we're implementing a queue, we could use the same concepts to implement a stack in a very similar manner.

First, we'll write a function that takes in a deque object as a queue and a list of songs. The function then selects a random song and adds it to the queue. The function also prints which song was added as well as the current queue. This process will go on infinitely.

def add_song(queue, songs):
    while True:
        index = randint(0, len(songs))
        song = songs[index]
        queue.append(song)
        print(f'Song Added: {song}, Queue: {queue}')
        sleep(randint(0, 5))

We now need a function to remove the songs as they are played. This function won't actually play a song since the goal is just to make a representation of queue functioning in Python. Instead, this function takes in a queue, deletes the leftmost element, and prints the deleted item and the current queue. If the queue is empty, the function will print that.

def play_song(queue):
    while True:
        try:
            song = queue.popleft()
            print(f'Song Played: {song}, Queue: {queue}')
        except IndexError:
            print('Queue is empty.')
        sleep(randint(0, 5))

Next, we'll create a list of songs and instantiate a deque object. Finally, we'll use Python's threading module to run both functions simultaneously. This is the final code:

from threading import Thread
from collections import deque
from time import sleep
from random import randint

songs = [f'song_{i+1}' for i in range(100)]

def add_song(queue, songs):
    while True:
        index = randint(0, len(songs))
        song = songs[index]
        queue.append(song)
        print(f'Song Added: {song}, Queue: {queue}')
        sleep(randint(0, 5))

def play_song(queue):
    while True:
        try:
            song = queue.popleft()
            print(f'Song Played: {song}, Queue: {queue}')
        except IndexError:
            print('Queue is empty.')
        sleep(randint(0, 5))

queue = deque()

Thread(target=add_song, args=(queue, songs)).start()
Thread(target=play_song, args=(queue,)).start()

If we run the above code, we'll have an output like the following:

Song Added: song_60, Queue: deque(['song_60'])
Song Played: song_60, Queue: deque([])
Queue is empty.
Queue is empty.
Song Added: song_13, Queue: deque(['song_13'])
Song Played: song_13, Queue: deque([])
Queue is empty.
Song Added: song_59, Queue: deque(['song_59'])
Song Added: song_46, Queue: deque(['song_59', 'song_46'])
Song Added: song_48, Queue: deque(['song_59', 'song_46', 'song_48'])
Song Played: song_59, Queue: deque(['song_46', 'song_48'])
Song Added: song_3, Queue: deque(['song_46', 'song_48', 'song_3'])
Song Played: song_46, Queue: deque(['song_48', 'song_3'])
Song Added: song_98, Queue: deque(['song_48', 'song_3', 'song_98'])
Song Played: song_48, Queue: deque(['song_3', 'song_98'])

Notice that the code adds songs at the right end of the queue and removes them from the left end, respecting the order of songs defined by the user. Also, since deque supports multithreading, we have no problems with two functions accessing and modifying the same object simultaneously.

Conclusion

In this article, we covered how the deque object from collections can be a great choice for implementing queues and stacks in Python. We also covered the following:

• The concepts of queues and stacks

• Why lists aren't the best choice in this case

• How to use the deque object

• Implementing a simplified version of a queue working in production