Python's deque: Implement Efficient Queues and Stacks

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.

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.

Popping and Appending Items Efficiently

The most important difference between deque and list is that the former allows you to perform efficient append and pop operations on both ends of the sequence. The deque class implements dedicated .popleft() and .appendleft() methods that operate on the left end of the sequence directly:

>>> from collections import deque

>>> numbers = deque([1, 2, 3, 4])
>>> numbers.popleft()
1
>>> numbers.popleft()
2
>>> numbers
deque([3, 4])

>>> numbers.appendleft(2)
>>> numbers.appendleft(1)
>>> numbers
deque([1, 2, 3, 4])

Here, you use .popleft() and .appendleft() to remove and add values, respectively, to the left end of numbers. These methods are specific to the design of deque, and you won’t find them in list.

Just like list, deque also provides .append() and .pop() methods to operate on the right end of the sequence. However, .pop() behaves differently:

>>> from collections import deque

>>> numbers = deque([1, 2, 3, 4])
>>> numbers.pop()
4

>>> numbers.pop(0)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: pop() takes no arguments (1 given)

Here, .pop() removes and returns the last value in the deque. The method doesn’t take an index as an argument, so you can’t use it to remove arbitrary items from your deques. You can only use it to remove and return the rightmost item.

As you learned earlier, deque is implemented as a doubly linked list. So, every item in a given deque holds a reference (pointer) to the next and previous item in the sequence.

Doubly linked lists make appending and popping items from either end light and efficient operations. That’s possible because only the pointers need to be updated. As a result, both operations have similar performance, O(1). They’re also predictable performance-wise because there’s no need for reallocating memory and moving existing items to accept new ones.

Appending and popping items from the left end of a regular Python list requires shifting all the items, which ends up being an O(n) operation. Additionally, adding items to the right end of a list often requires Python to reallocate memory and copy the current items to the new memory location. After that, it can add the new items. This process takes longer to complete, and the append operation passes from being O(1) to O(n).

Consider the following performance tests for appending items to the left end of a sequence, deque vs list:

# time_append.py

from collections import deque
from time import perf_counter

TIMES = 10_000
a_list = []
a_deque = deque()

def average_time(func, times):
    total = 0.0
    for i in range(times):
        start = perf_counter()
        func(i)
        total += (perf_counter() - start) * 1e9
    return total / times

list_time = average_time(lambda i: a_list.insert(0, i), TIMES)
deque_time = average_time(lambda i: a_deque.appendleft(i), TIMES)
gain = list_time / deque_time

print(f"list.insert()      {list_time:.6} ns")
print(f"deque.appendleft() {deque_time:.6} ns  ({gain:.6}x faster)")

In this script, average_time() computes the average time that executing a function (func) a given number of times takes. If you run the script from your command line, then you get the following output:

$ python time_append.py
list.insert()      3735.08 ns
deque.appendleft() 238.889 ns  (15.6352x faster)

In this specific example, .appendleft() on a deque is several times faster than .insert() on a list. Note that deque.appendleft() is O(1), which means that the execution time is constant. However, list.insert() on the left end of the list is O(n), which means that the execution time depends on the number of items to process.

In this example, if you increment the value of TIMES, then you’ll get higher time measurements for list.insert() but stable (constant) results for deque.appendleft(). If you’d like to try a similar performance test on pop operations for both deques and lists, then you can expand the exercise block below and compare your results to Real Python’s after you’re done.

# time_pop.py

from collections import deque
from time import perf_counter

TIMES = 10_000
a_list = [1] * TIMES
a_deque = deque(a_list)

def average_time(func, times):
    total = 0.0
    for _ in range(times):
        start = perf_counter()
        func()
        total += (perf_counter() - start) * 1e9
    return total / times

list_time = average_time(lambda: a_list.pop(0), TIMES)
deque_time = average_time(lambda: a_deque.popleft(), TIMES)
gain = list_time / deque_time

print(f"list.pop(0)     {list_time:.6} ns")
print(f"deque.popleft() {deque_time:.6} ns  ({gain:.6}x faster)")

list.pop(0)     2002.08 ns
deque.popleft() 326.454 ns  (6.13282x faster)

The deque data type was designed to guarantee efficient append and pop operations on either end of the sequence. It’s ideal for approaching problems that require the implementation of queue and stack data structures in Python.

Accessing Random Items in a deque

Python’s deque returns mutable sequences that work quite similarly to lists. Besides allowing you to append and pop items from their ends efficiently, deques provide a group of list-like methods and other sequence-like operations to work with items at arbitrary locations. Here are some of them:

You can use these methods and techniques to work with items at any position inside a deque object. Here’s how to do that:

>>> from collections import deque

>>> letters = deque("abde")

>>> letters.insert(2, "c")
>>> letters
deque(['a', 'b', 'c', 'd', 'e'])

>>> letters.remove("d")
>>> letters
deque(['a', 'b', 'c', 'e'])

>>> letters[1]
'b'

>>> del letters[2]
>>> letters
deque(['a', 'b', 'e'])

Here, you first insert "c" into letters at position 2. Then you remove "d" from the deque using .remove(). Deques also allow indexing to access items, which you use here to access "b" at index 1. Finally, you can use the del keyword to delete any existing items from a deque. Note that .remove() lets you delete items by value, while del removes items by index.

Even though deque objects support indexing, they don’t support slicing. In other words, you can’t extract a slice from an existing deque using the slicing syntax, [start:stop:step], as you would with a regular list:

>>> from collections import deque

>>> numbers = deque([1, 2, 3, 4, 5])

>>> numbers[1:3]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: sequence index must be integer, not 'slice'

Deques support indexing, but interestingly, they don’t support slicing. When you try to get a slice from a deque, you get a TypeError. In general, performing a slicing on a linked list would be inefficient, so the operation isn’t available.

So far, you’ve seen that deque is quite similar to list. However, while list is based on arrays, deque is based on a doubly linked list.

There is a hidden cost behind deque being implemented as a doubly linked list: accessing, inserting, and removing arbitrary items aren’t efficient operations. To perform them, the interpreter has to iterate through the deque until it gets to the desired item. So, they’re O(n) instead of O(1) operations.

Here’s a script that shows how deques and lists behave when it comes to working with arbitrary items:

# time_random_access.py

from collections import deque
from time import perf_counter

TIMES = 10_000
a_list = [1] * TIMES
a_deque = deque(a_list)

def average_time(func, times):
    total = 0.0
    for _ in range(times):
        start = perf_counter()
        func()
        total += (perf_counter() - start) * 1e6
    return total / times

def time_it(sequence):
    middle = len(sequence) // 2
    sequence.insert(middle, "middle")
    sequence[middle]
    sequence.remove("middle")
    del sequence[middle]

list_time = average_time(lambda: time_it(a_list), TIMES)
deque_time = average_time(lambda: time_it(a_deque), TIMES)
gain = deque_time / list_time

print(f"list  {list_time:.6} μs ({gain:.6}x faster)")
print(f"deque {deque_time:.6} μs")

This script times inserting, deleting, and accessing items in the middle of a deque and a list. If you run the script, then you get an output that looks like the following:

$ python time_random_access.py
list  63.8658 μs (1.44517x faster)
deque 92.2968 μs

Deques aren’t random-access data structures like lists. Therefore, accessing elements from the middle of a deque is less efficient than doing the same thing on a list. The main takeaway here is that deques aren’t always more efficient than lists.

Python’s deque is optimized for operations on either end of the sequence, so they’re consistently better than lists in this regard. On the other hand, lists are better for random-access and fixed-length operations. Here are some of the differences between deques and lists in terms of performance:

In the case of lists, .append() has amortized performance affected by memory reallocation when the interpreter needs to grow the list to accept new items. This operation requires copying all the current items to the new memory location, which significantly affects the performance.

This summary can help you choose the appropriate data type for the problem at hand. However, make sure to profile your code before switching from lists to deques. Both of them have their performance strengths.

Building Efficient Queues With deque

As you already learned, deque is implemented as a double-ended queue that provides a generalization of stacks and queues. In this section, you’ll learn how to use deque for implementing your own queue abstract data types (ADT) at a low level in an elegant, efficient, and Pythonic way.

Queues are collections of items. You can modify queues by adding items at one end and removing items from the opposite end.

Queues manage their items in a First-In/First-Out (FIFO) fashion. They work as a pipe where you push in new items at one end of the pipe and pop old items out from the other end. Adding an item to one end of a queue is known as an enqueue operation. Removing an item from the other end is called dequeue.

To better understand queues, take your favorite restaurant as an example. The restaurant has a queue of people waiting for a table to order their food. Typically, the last person to arrive will stand at the end of the queue. The person at the beginning of the queue will leave it as soon as a table is available.

Here’s how you can emulate the process using a bare-bones deque object:

>>> from collections import deque

>>> customers = deque()

>>> # People arriving
>>> customers.append("Jane")
>>> customers.append("John")
>>> customers.append("Linda")

>>> customers
deque(['Jane', 'John', 'Linda'])

>>> # People getting tables
>>> customers.popleft()
'Jane'
>>> customers.popleft()
'John'
>>> customers.popleft()
'Linda'

>>> # No people in the queue
>>> customers.popleft()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
IndexError: pop from an empty deque

Here, you first create an empty deque object to represent the queue of people arriving at the restaurant. To enqueue a person, you use .append(), which adds individual items to the right end. To dequeue a person, you use .popleft(), which removes and returns individual items on the left end of a deque.

Cool! Your queue simulation works! However, since deque is a generalization, its API doesn’t match the typical queue API. For example, instead of .enqueue(), you have .append(). You also have .popleft() instead of .dequeue(). Additionally, deque provides several other operations that might not fit your specific needs.

The good news is that you can create custom queue classes with the functionality you need and nothing else. To do this, you can internally use a deque to store the data and provide the desired functionality in your custom queues. You can think of it as an implementation of the adapter design pattern, in which you convert the deque’s interface into something that looks more like a queue interface.

For example, say you need a custom queue abstract data type that provides only the following features:

• Enqueuing items
• Dequeuing items
• Returning the length of the queue
• Supporting membership tests
• Supporting normal and reverse iteration
• Providing a user-friendly string representation

In this case, you can write a Queue class that looks like the following:

# custom_queue.py

from collections import deque

class Queue:
    def __init__(self):
        self._items = deque()

    def enqueue(self, item):
        self._items.append(item)

    def dequeue(self):
        try:
            return self._items.popleft()
        except IndexError:
            raise IndexError("dequeue from an empty queue") from None

    def __len__(self):
        return len(self._items)

    def __contains__(self, item):
        return item in self._items

    def __iter__(self):
        yield from self._items

    def __reversed__(self):
        yield from reversed(self._items)

    def __repr__(self):
        return f"Queue({list(self._items)})"

Here, ._items holds a deque object that allows you to store and manipulate the items in the queue. Queue implements .enqueue() using deque.append() to add items to the end of the queue. It also implements .dequeue() with deque.popleft() to efficiently remove items from the beginning of the queue.

The special methods support the following features:

Ideally, .__repr__() should return a string representing a valid Python expression. This expression will allow you to recreate the object unambiguously with the same value.

However, in the example above, the intent is to use the method’s return value to gracefully display the object on the interactive shell. You can make it possible to build Queue instances from this specific string representation by accepting an initialization iterable as an argument to .__init__() and building instances from it.

With these final additions, your Queue class is complete. To use this class in your code, you can do something like the following:

>>> from custom_queue import Queue

>>> numbers = Queue()
>>> numbers
Queue([])

>>> # Enqueue items
>>> for number in range(1, 5):
...     numbers.enqueue(number)
...
>>> numbers
Queue([1, 2, 3, 4])

>>> # Support len()
>>> len(numbers)
4

>>> # Support membership tests
>>> 2 in numbers
True
>>> 10 in numbers
False

>>> # Normal iteration
>>> for number in numbers:
...     print(f"Number: {number}")
...
Number: 1
Number: 2
Number: 3
Number: 4

As an exercise, you can test the remaining features and implement other features, such as supporting equality tests, removing and accessing random items, and more. Go ahead and give it a try!

Exploring Other Features of deque

In addition to the features you’ve seen so far, deque also provides other methods and attributes specific to their internal design. They add new and useful functionalities to this versatile data type.

In this section, you’ll learn about other methods and attributes that deques provide, how they work, and how to use them in your code.

>>> from collections import deque

>>> four_numbers = deque([0, 1, 2, 3, 4], maxlen=4) # Discard 0
>>> four_numbers
deque([1, 2, 3, 4], maxlen=4)

>>> four_numbers.append(5)  # Automatically remove 1
>>> four_numbers
deque([2, 3, 4, 5], maxlen=4)

>>> four_numbers.append(6)  # Automatically remove 2
>>> four_numbers
deque([3, 4, 5, 6], maxlen=4)

>>> four_numbers.appendleft(2) # Automatically remove 6
>>> four_numbers
deque([2, 3, 4, 5], maxlen=4)

>>> four_numbers.appendleft(1)  # Automatically remove 5
>>> four_numbers
deque([1, 2, 3, 4], maxlen=4)

>>> four_numbers.maxlen
4

>>> from collections import deque

>>> ordinals = deque(["first", "second", "third"])

>>> # Rotate items to the right
>>> ordinals.rotate()
>>> ordinals
deque(['third', 'first', 'second'])

>>> ordinals.rotate(2)
>>> ordinals
deque(['first', 'second', 'third'])

>>> # Rotate items to the left
>>> ordinals.rotate(-2)
>>> ordinals
deque(['third', 'first', 'second'])

>>> ordinals.rotate(-1)
>>> ordinals
deque(['first', 'second', 'third'])

>>> from collections import deque

>>> numbers = deque([1, 2])

>>> # Extend to the right
>>> numbers.extend([3, 4, 5])
>>> numbers
deque([1, 2, 3, 4, 5])

>>> # Extend to the left
>>> numbers.extendleft([-1, -2, -3, -4, -5])
>>> numbers
deque([-5, -4, -3, -2, -1, 1, 2, 3, 4, 5])

Using Sequence-Like Features of deque

Since deques are mutable sequences, they implement almost all the methods and operations that are common to sequences and mutable sequences. So far, you’ve learned about some of these methods and operations, such as .insert(), indexing, membership tests, and more.

Here are a few examples of other actions you can perform on deque objects:

>>> from collections import deque

>>> numbers = deque([1, 2, 2, 3, 4, 4, 5])

>>> # Concatenation
>>> numbers + deque([6, 7, 8])
deque([1, 2, 2, 3, 4, 4, 5, 6, 7, 8])

>>> # Repetition
>>> numbers * 2
deque([1, 2, 2, 3, 4, 4, 5, 1, 2, 2, 3, 4, 4, 5])

>>> # Common sequence methods
>>> numbers = deque([1, 2, 2, 3, 4, 4, 5])
>>> numbers.index(2)
1
>>> numbers.count(4)
2

>>> # Common mutable sequence methods
>>> numbers.reverse()
>>> numbers
deque([5, 4, 4, 3, 2, 2, 1])

>>> numbers.clear()
>>> numbers
deque([])

You can use the addition operator (+) to concatenate two existing deques. On the other hand, the multiplication operator (*) returns a new deque equivalent to repeating the original deque as many times as you want.

Regarding other sequence methods, the following table provides a summary:

Here, .index() can also take two optional arguments: start and stop. They allow you to restrict the search to those items at or after start and before stop. The method raises a ValueError if value doesn’t appear in the deque at hand.

Unlike lists, deques don’t include a .sort() method to sort the sequence in place. This is because sorting a linked list would be an inefficient operation. If you ever need to sort a deque, then you can still use sorted().

Putting Python’s deque Into Action

You can use deques in a fair amount of use cases, such as to implement queues, stacks, and circular buffers. You can also use them to maintain an undo-redo history, enqueue incoming requests to a web service, keep a list of recently open files and websites, safely exchange data between multiple threads, and more.

In the following sections, you’ll code a few small examples that will help you better understand how to use deques in your code.

>>> from collections import deque

>>> sites = (
...     "google.com",
...     "yahoo.com",
...     "bing.com"
... )

>>> pages = deque(maxlen=3)
>>> pages.maxlen
3

>>> for site in sites:
...     pages.appendleft(site)
...

>>> pages
deque(['bing.com', 'yahoo.com', 'google.com'], maxlen=3)

>>> pages.appendleft("facebook.com")
>>> pages
deque(['facebook.com', 'bing.com', 'yahoo.com'], maxlen=3)

>>> pages.appendleft("twitter.com")
>>> pages
deque(['twitter.com', 'facebook.com', 'bing.com'], maxlen=3)

# threads.py

import logging
import random
import threading
import time
from collections import deque

logging.basicConfig(level=logging.INFO, format="%(message)s")

def wait_seconds(mins, maxs):
    time.sleep(mins + random.random() * (maxs - mins))

def produce(queue, size):
    while True:
        if len(queue) < size:
            value = random.randint(0, 9)
            queue.append(value)
            logging.info("Produced: %d -> %s", value, str(queue))
        else:
            logging.info("Queue is saturated")
        wait_seconds(0.1, 0.5)

def consume(queue):
    while True:
        try:
            value = queue.popleft()
        except IndexError:
            logging.info("Queue is empty")
        else:
            logging.info("Consumed: %d -> %s", value, str(queue))
        wait_seconds(0.2, 0.7)

logging.info("Starting Threads...\n")
logging.info("Press Ctrl+C to interrupt the execution\n")

shared_queue = deque()

threading.Thread(target=produce, args=(shared_queue, 10)).start()
threading.Thread(target=consume, args=(shared_queue,)).start()

$ python threads.py
Starting Threads...

Press Ctrl+C to interrupt the execution

Produced: 1 -> deque([1])
Consumed: 1 -> deque([])
Queue is empty
Produced: 3 -> deque([3])
Produced: 0 -> deque([3, 0])
Consumed: 3 -> deque([0])
Consumed: 0 -> deque([])
Produced: 1 -> deque([1])
Produced: 0 -> deque([1, 0])
  ...

>>> from collections import deque

>>> def tail(filename, lines=10):
...     try:
...         with open(filename) as file:
...             return deque(file, lines)
...     except OSError as error:
...         print(f'Opening file "{filename}" failed with error: {error}')
...

Conclusion

Queues and stacks are commonly used abstract data types in programming. They typically require efficient pop and append operations on either end of the underlying data structure. Python’s collections module provides a data type called deque that’s specially designed for fast and memory-efficient append and pop operations on both ends.

With deque, you can code your own queues and stacks at a low level in an elegant, efficient, and Pythonic way.

In this tutorial, you learned how to:

• Create and use Python’s deque in your code
• Efficiently append and pop items from both ends of a sequence with deque
• Use deque to build efficient queues and stacks in Python
• Decide when to use deque instead of list

In this tutorial, you also coded a few examples that helped you approach some common use cases of deque in Python.