Advanced Python: Deque or Double ended queues

Python’s deque (double-ended queue) is a versatile and efficient data structure that provides constant time complexity for appending and popping elements from either end of the deque. This makes it an ideal choice for scenarios where you need to add or remove elements frequently from both ends of the data structure.

In this article, we will explore the deque class in Python and learn how to use it with step-by-step code examples.

Creating a deque

To create a deque object, we need to import the deque class from the collections module:

from collections import deque

We can create a deque object by calling the deque() function and passing an iterable as an argument. Here’s an example:

my_deque = deque([1, 2, 3])
print(my_deque)

Output:

deque([1, 2, 3])

In this example, we create a deque object called my_deque containing the elements 1, 2, and 3.

We can also create an empty deque by calling the deque() function with no arguments:

empty_deque = deque()
print(empty_deque)

Output:

deque([])

Appending and popping elements

One of the key features of deque is its ability to append and pop elements from either end of the deque in constant time. We can append elements to the right end of the deque using the append() method:

my_deque.append(4)
print(my_deque)

Output:

deque([1, 2, 3, 4])

In this example, we append the element 4 to the right end of the my_deque deque using the append() method.

We can also append elements to the left end of the deque using the appendleft() method:

my_deque.appendleft(0)
print(my_deque)

Output:

deque([0, 1, 2, 3, 4])

In this example, we append the element 0 to the left end of the my_deque deque using the appendleft() method.

We can pop elements from the right end of the deque using the pop() method:

popped = my_deque.pop()
print(popped)
print(my_deque)

Output:

4
deque([0, 1, 2, 3])

In this example, we pop the last element (4) from the right end of the my_deque deque using the pop() method.

We can also pop elements from the left end of the deque using the popleft() method:

popped = my_deque.popleft()
print(popped)
print(my_deque)

Output:

0
deque([1, 2, 3])

In this example, we pop the first element (0) from the left end of the my_deque deque using the popleft() method.

Accessing elements

We can access elements of a deque using index notation, just like with a list. Here’s an example:

print(my_deque[0])
print(my_deque[-1])

Output:

1
3

In this example, we print the first (1) and last (3) elements of the my_deque deque using index notation.

We can also use slicing to access a range of elements in a deque. Here’s an example:

print(my_deque[1:3])

Output:

deque([2, 3])

In this example, we print a deque containing the elements at indices 1 and 2 ([2, 3]) using slicing notation.

Rotating elements

deque provides a rotate() method that allows us to rotate the elements in the deque by a given number of steps. Positive values rotate the elements to the right, while negative values rotate the elements to the left.

my_deque.rotate(1)
print(my_deque)

Output:

deque([3, 1, 2])

In this example, we rotate the my_deque deque by one step to the right using the rotate() method.

my_deque.rotate(-2)
print(my_deque)

Output:

deque([2, 3, 1])

In this example, we rotate the my_deque deque by two steps to the left using the rotate() method.

Clearing a deque

We can clear all elements from a deque using the clear() method:

my_deque.clear()
print(my_deque)

Output:

deque([])

In this example, we clear all elements from the my_deque deque using the clear() method.

Conclusion

In this article, we learned how to use the deque class in Python to create a double-ended queue data structure. We explored various methods of adding and removing elements from either end of the deque, accessing elements by index or slicing, and rotating the elements of the deque. We also learned how to clear all elements from a deque.

deque provides a versatile and efficient data structure for many common scenarios where we need to add or remove elements frequently from both ends of the data structure.