Python Deque Explained: Efficient Stack and Queue Operations

Deque in Python, also known as a double-ended queue, is a type of data structure that allows you to add and remove elements from either end. Python’s collections module provides us with the deque class to create deques.

They are different from queues and stacks as they support more flexible, memory-efficient, and in some cases, faster operations.

Unlike lists or tuples, deques are linked lists that can handle append and pop operations from both ends with fast time complexity.

This makes it suitable for data structures such as queues (FIFO – First In First Out) and stacks (LIFO – Last In First Out).
Let’s proceed with our Python deque tutorial.

 

 

Creating Deques in Python

Here’s how you create a deque using the collections module:

from collections import deque

# Create a deque
d = deque()

To add elements to the deque, you can use the append() method:

d.append('a')
d.append('b')
d.append('c')

Now, if we print our deque, we’ll get:

print(d)

Output:

deque(['a', 'b', 'c'])

In the above code, we first import the deque class from the collections module. Then we create a deque d. We append three elements ‘a’, ‘b’, and ‘c’ to the right end of the deque using the append() method.

When we print the deque, we see these elements in the order they were added.
You can also initialize a deque with multiple elements at once, and optionally set a maximum length:

d = deque(['x', 'y', 'z'], maxlen=5)

This creates a deque with a maximum length of 5. If more elements are added, it will automatically remove elements from the opposite end to maintain the size.

 

Accessing Elements in a Deque

Accessing elements in a deque is done by indexing, similar to how you would access elements in a list:

from collections import deque
d = deque(['a', 'b', 'c', 'd', 'e'])

# Access elements
print(d[0])
print(d[-1])

Output:

'a'
'e'

In the code above, we create a deque d with five elements.

When we print d[0], we get the first element ‘a’. When we print d[-1], we get the last element ‘e’.

Python allows negative indexing where -1 refers to the last element, -2 refers to the second last, and so on.
However, unlike lists, deques do not support slicing because they are designed to be primarily append and pop operations on both ends and thus are optimized for such operations.

 

Modifying Elements

Here’s how you modify an element:

from collections import deque
d = deque(['a', 'b', 'c', 'd', 'e'])

# Modify an element
d[0] = 'z'
print(d)

Output:

deque(['z', 'b', 'c', 'd', 'e'])

In this code, we first create a deque d with five elements. Then we change the first element (at index 0) to ‘z’.

When we print the deque, we see that the first element has been modified to ‘z’.
Remember that modifying an element in a deque has a time complexity of O(n) as it has to iterate through the deque to find the element.

Therefore, if you need frequent modifications in the middle of your data structure, choose a different data type.

 

Deque Length

You can use the built-in len() function to get the number of items in a deque:

from collections import deque
d = deque(['a', 'b', 'c', 'd', 'e'])
print(len(d))

Output:

5

In this code, we first create a deque d with five elements. Then we print the length of the deque using len(d), and we get 5, which is the number of elements in the deque.
You can also check if a deque is empty or not:

# Check if deque is empty
if not d:
    print("Deque is empty.")
else:
    print("Deque is not empty.")

Output:

Deque is not empty.

Here, not d checks if the deque d is empty. If it is, it prints “Deque is empty.” If it’s not, it prints “Deque is not empty.”

 

Adding Elements to the Right End (append())

You can add elements to the end of a deque using the append() method. Here’s how you do it:

from collections import deque
d = deque(['a', 'b', 'c'])

# Add element to the right end
d.append('d')
print(d)

Output:

deque(['a', 'b', 'c', 'd'])

In the code above, we first create a deque d with three elements. Then we add ‘d’ to the right end of the deque using the append() method.
When we print the deque, we see ‘d’ at the right end of the deque.
The append() operation has a time complexity of O(1), which means it’s a very fast operation no matter how large the deque is.

 

Adding Elements to the Left End (appendleft())

You can also add elements to the left end of a deque using the appendleft() method. Here’s how:

from collections import deque
d = deque(['b', 'c', 'd'])

# Add element to the left end
d.appendleft('a')
print(d)

Output:

deque(['a', 'b', 'c', 'd'])

In the code above, we first create a deque d with three elements. Then we add ‘a’ to the left end of the deque using the appendleft() method. When we print the deque, we see ‘a’ at the left end of the deque.
Similar to append(), the appendleft() operation also has a time complexity of O(1).

 

Adding Multiple Elements to the Right End (extend())

The extend() method allows you to add multiple elements to the right end of a deque. Here’s how:

from collections import deque
d = deque(['a', 'b'])

# Add multiple elements to the right end
d.extend(['c', 'd', 'e'])
print(d)

Output:

deque(['a', 'b', 'c', 'd', 'e'])

In the code above, we first create a deque d with two elements. Then we add three elements ‘c’, ‘d’, and ‘e’ to the right end of the deque using the extend() method.

When we print the deque, we see these new elements at the right end.
The time complexity of the extend() operation is O(k), where k is the number of elements to be added.

 

Adding Multiple Elements to the Left End (extendleft())

The extendleft() method allows you to add multiple elements to the left end of a deque. Here’s how you do it:

from collections import deque
d = deque(['d', 'e'])

# Add multiple elements to the left end
d.extendleft(['c', 'b', 'a'])
print(d)

Output:

deque(['a', 'b', 'c', 'd', 'e'])

In the code above, we first create a deque d with two elements. Then we add three elements ‘c’, ‘b’, and ‘a’ to the left end of the deque using the extendleft() method. When we print the deque, we see these new elements at the left end.

Notice that the extendleft() method iterates over the input in reverse order, which can be observed in the output.
Similar to extend(), the time complexity of extendleft() operation is also O(k).

 

Iterating over a deque

You can iterate over a deque in the same way you would iterate over a list.
Here is how you can iterate over a deque in forward direction:

from collections import deque
d = deque(['a', 'b', 'c', 'd', 'e'])

# Forward iteration
for i in d:
    print(i)

Output:

'a'
'b'
'c'
'd'
'e'

And for backward iteration, you can use the reversed() function:

# Backward iteration
for i in reversed(d):
    print(i)

Output:

'e'
'd'
'c'
'b'
'a'

In the code above, we first create a deque d with five elements. Then, we iterate over the deque in forward and backward direction and print each element.

 

Sorting a Deque

Deques do not have a built-in sort method, but you can use the sorted() function to get a sorted list from the deque.
Here’s an example:

from collections import deque
d = deque([3, 1, 4, 1, 5, 9, 2])

# Get a sorted list from the deque
sorted_d = sorted(d)
print(sorted_d)

Output:

[1, 1, 2, 3, 4, 5, 9]

In the code above, we first create a deque d with seven elements. Then, we create a sorted list sorted_d from the deque using the sorted() function.

The resulting list is in ascending order.
Remember that sorted() doesn’t sort the deque in-place, but returns a new list.

This is because deques are designed to have fast append and pop operations from both ends, but not for operations like sorting that require random access to the elements.

 

Searching Deque

You can perform a linear search in a deque using the index() method. The index() method returns the index of the first occurrence of the specified value.
Here’s an example:

from collections import deque
d = deque(['a', 'b', 'c', 'b', 'a'])

# Get the index of 'b'
index = d.index('b')
print(index)

Output:

1

In the code above, we first create a deque d with five elements. Then, we use the index() method to get the index of the first occurrence of ‘b’, which is 1.

 

Removing Elements from a Deque

Deque provides methods to remove elements from either end: pop() removes and returns an element from the right end of the deque, and popleft() removes and returns an element from the left end. Let’s look at an example:

from collections import deque
d = deque(['a', 'b', 'c', 'd', 'e'])

# Remove elements from either end
right_end = d.pop()
left_end = d.popleft()
print(right_end)
print(left_end)
print(d)

Output:

'e'
'a'
deque(['b', 'c', 'd'])

In the code above, we first create a deque d with five elements. Then we remove an element from the right end using pop() and from the left end using popleft().

When we print the deque, we see that the left and right end elements are removed.

Remove all elements

The clear() method removes all elements from the deque:

d.clear()
print(d)

Output:

deque([])

Here, after invoking d.clear(), all elements in the deque are removed, and we get an empty deque as the output.
The time complexity of pop(), popleft(), and clear() operations is O(1).

 

Deque Rotation

Deque provides a rotate() method that allows you to rotate the deque by n steps to the right. If n is negative, rotate to the left.
Here’s an example:

from collections import deque
d = deque(['a', 'b', 'c', 'd', 'e'])

# Rotate deque by 2 steps to the right
d.rotate(2)
print(d)

Output:

deque(['d', 'e', 'a', 'b', 'c'])

In the code above, we first create a deque d with five elements.

Then we rotate the deque by 2 steps to the right using rotate(2). The last two elements are shifted to the front of the deque.

Negative Rotation

If you rotate by a negative value, it rotates to the left:

# Rotate deque by 2 steps to the left
d.rotate(-2)
print(d)

Output:

deque(['a', 'b', 'c', 'd', 'e'])

Here, after invoking d.rotate(-2), the first two elements are shifted to the end of the deque.
The rotate() operation has a time complexity of O(k), where k is the number of steps.

 

Using Deque as a Stack

A stack is a LIFO (Last In, First Out) data structure. In Python, you can use a deque to implement a stack.
Here’s how you do it:

from collections import deque
stack = deque()

# Add elements to the stack
stack.append('a')
stack.append('b')
stack.append('c')
print(stack)

# Remove elements from the stack
top = stack.pop()
print(top)
print(stack)

Output:

deque(['a', 'b', 'c'])
'c'
deque(['a', 'b'])

In the code above, we first create an empty deque stack. Then we add three elements to the stack using the append() method, which adds elements to the right end of the deque.

To remove elements from the stack, we use the pop() method, which removes and returns the rightmost element.
Thus, the last element added is the first one to be removed, following the LIFO principle.

 

Using Deque as a Queue

A queue is a FIFO (First In, First Out) data structure. You can use a deque to implement a queue.
Here’s how:

from collections import deque
queue = deque()

# Add elements to the queue
queue.append('a')
queue.append('b')
queue.append('c')
print(queue)

# Remove elements from the queue
front = queue.popleft()
print(front)
print(queue)

Output:

deque(['a', 'b', 'c'])
'a'
deque(['b', 'c'])

In the code above, we first create an empty deque queue. Then we add three elements to the queue using the append() method.

To remove elements from the queue, we use the popleft() method, which removes and returns the leftmost element.

Thus, the first element added is the first one to be removed, following the FIFO principle.

 

Using Deque as a Circular Queue

A circular queue, also known as a ring buffer, is a queue in which the last element points to the first element making a circular link.

Deque in Python can be used to implement a circular queue by using the rotate() function. Here’s how:

from collections import deque
circular_queue = deque(['a', 'b', 'c', 'd', 'e'], maxlen=5)

# Rotate the queue to the right
circular_queue.rotate(1)
print(circular_queue)

Output:

deque(['e', 'a', 'b', 'c', 'd'], maxlen=5)

In the code above, we first create a deque circular_queue with five elements and a maxlen of 5.

Then we rotate the deque by one step to the right using rotate(1).

The last element ‘e’ is shifted to the front of the deque, making it act like a circular queue.

 

Nesting a Deque

Similar to lists, deques can also contain other deques (or lists) as elements. This is called nesting.
Here’s an example:

from collections import deque

# Initialize a deque with another deque as an element
d = deque(['a', deque(['b', 'c', 'd']), 'e'])
print(d)

Output:

deque(['a', deque(['b', 'c', 'd']), 'e'])

In the code above, we create a deque d with three elements.

The second element is another deque with three elements. The output shows a deque within a deque.
Remember that when you modify a nested deque, the changes reflect in the outer deque as well.

 

Understanding Thread-Safety in Deque

Deque operations (append(), appendleft(), pop(), popleft(), and so on) are thread-safe in Python.

This makes deque a suitable choice when implementing data structures that need to handle concurrent operations.
Here’s a simple example:

from collections import deque
from threading import Thread

# This function appends 100000 elements to the deque
def append_elements(d):
    for i in range(100000):
        d.append(i)
d = deque()

# Create two threads that execute the same function
t1 = Thread(target=append_elements, args=(d,))
t2 = Thread(target=append_elements, args=(d,))

# Start the threads
t1.start()
t2.start()

# Wait for both threads to finish
t1.join()
t2.join()
print(len(d))

Output:

200000

In this code, we define a function append_elements() that appends 100000 elements to the deque. We then create two threads that execute this function concurrently.

Since deque operations are thread-safe, we don’t need to worry about any race conditions that might occur due to simultaneous access and modification of the deque.

 

Deque vs. Lists (Performance Comparison)

Deques and lists have different performance characteristics, and understanding these differences can help you choose the right data structure for your use case.
For operations involving appending or popping elements at the ends (either end for deques, right end for lists), deques are more efficient than lists.

This is because these operations have a time complexity of O(1) for deques.

from collections import deque
from timeit import timeit

# A large number of elements
N = 10**6

lst = [0] * N
deq = deque(lst)

# Measure the time taken to append and pop elements at the ends
list_time = timeit(lambda: lst.append(10) or lst.pop(), number=N)
deque_time = timeit(lambda: deq.append(10) or deq.pop(), number=N)
print(f"List time: {list_time}")
print(f"Deque time: {deque_time}")

Output:

List time: 0.2596190000003844
Deque time: 0.20638569999937317

In this code, we first create a list and a deque with a large number of elements.

Then we measure the time taken to append and pop elements at the ends for both data structures. You’ll find that deque is faster.
On the other hand, for operations involving accessing or modifying elements in the middle, lists are much more efficient than deques.

This is because lists in Python are implemented as dynamic arrays, which provide fast O(1) random access.

list_time = timeit(lambda: lst[N//2] or lst.insert(N//2, 10), number=N)
deque_time = timeit(lambda: deq[N//2] or deq.insert(N//2, 10), number=N)
print(f"List time: {list_time}")
print(f"Deque time: {deque_time}")

Output:

List time: 0.1969280000012077
Deque time: 50.14866749999965

In this code, we measure the time taken to access and modify an element in the middle for both data structures. You’ll find that list is significantly faster.

 

Memory Consumption of Deque vs. Lists

In addition to time complexity, another important factor to consider when choosing between a deque and a list is memory consumption.

Deques are implemented as a doubly-linked list, which means they require storing two pointers (next and prev) for each item.

This results in higher memory overhead compared to lists.
Let’s look at a simple comparison using the sys module to measure the size of a list and a deque with the same elements:

import sys
from collections import deque

# Create a list and a deque with 1 million elements
lst = [0] * 10**6
deq = deque(lst)
list_size = sys.getsizeof(lst)
deque_size = sys.getsizeof(deq)
print(f"List size: {list_size} bytes")
print(f"Deque size: {deque_size} bytes")

Output:

List size: 8000056 bytes
Deque size: 8250624 bytes

The deque has a larger size than the list.

The additional memory overhead of deques is a trade-off for their flexibility and performance advantages in certain scenarios (like efficient appends/pops at both ends).

 

Common Mistakes and Pitfalls in Deque Usage

When using deques, it’s important to be aware of some common mistakes and pitfalls that could lead to errors or unexpected behavior.
Over-Popping a Deque
When you pop from an empty deque, Python raises an IndexError. Always ensure your deque has elements before you attempt to pop.

from collections import deque
d = deque()
try:
    d.pop()
except IndexError:
    print("Cannot pop from an empty deque.")

Output:

Cannot pop from an empty deque.

Ignoring Maxlen Parameter
If you specify a maxlen when creating a deque, when the deque is full, adding new elements will discard elements from the opposite end.

If you do not wish for elements to be automatically discarded, do not set a maxlen.

from collections import deque
d = deque(maxlen=3)
d.append(1)
d.append(2)
d.append(3)
d.append(4)
print(d)  # Output: deque([2, 3, 4], maxlen=3)

In this code, when we append the element 4 to a deque that is already full, the element 1 is automatically discarded to make room.

 

When to Use Deque vs. List

Understanding when to use a deque versus other data structures is key to writing efficient code.

• Deque: Use a deque when you need to efficiently add or remove items from the ends, such as when implementing queues, stacks, or circular queues. Deques are also a good choice for maintaining a ‘sliding window’ of elements, thanks to the maxlen parameter.
• List: Use a list when you need to access or modify items by index, as lists provide O(1) time complexity for these operations. Lists also consume less memory than deques.

In the end, the choice of data structure will largely depend on the specific requirements of your application.

Real-world Applications of Deque

The deque data structure is quite versatile and finds utility in numerous real-world applications.

• Undo Operations: Many applications provide an undo feature, which can be implemented with a deque. Each operation is added to the deque, and when the user requests an undo, the operation from the end of the deque is taken and reversed.
• Maintaining History: Deque can be used to maintain history in applications where only a certain number of recent records are needed.
• Scheduling Algorithms: Deques can be used to implement scheduling algorithms like Round Robin Scheduling, which is used in the design of time-sharing systems.

Remember, when the problem involves adding or removing elements from either end of the collection, consider using a deque.
That brings us to the end of this tutorial on Python deques. I hope you found this information useful and that it deepens your understanding of deque in Python and when to use them.

 

Resources

https://docs.python.org/3/library/collections.html#collections.deque