Deque - Python Collection Module

We'll focus our attention on the deque module of Python's built-in collections package. This module introduces the concept of double-ended queues, providing a powerful and efficient data structure for a variety of programming scenarios.

Understanding Deques (Double-Ended Queues)

A deque, short for double-ended queue, is a dynamic array that allows for quick and efficient append and pop operations on both ends. It provides O(1) time complexity for these operations, making it a valuable tool in scenarios where performance is critical.

Have a look at simple usage of deque

from collections import deque

# Creating a deque
double_ended_queue = deque([1, 2, 3])

# Inserting and deleting elements from deque
double_ended_queue.append(4)
double_ended_queue.popleft()

Output: ----------------------------------------
Deque after appending 4:  deque([1, 2, 3, 4])
Leftmost element after popleft(): 1
Deque after popping leftmost element i.e 1:  deque([2, 3, 4])

Advanced Operations with Deque

1. Appending and Popping Operations:

'append(x)': Adds element `x` to the right end of the deque.
'appendleft(x)': Adds element `x` to the left end of the deque.
'pop()': Removes and returns the rightmost element.
'popleft()': Removes and returns the leftmost element.

2. Extending and Reducing:

'extend(iterable)': Extends the right end of the deque by appending elements from the iterable.
'extendleft(iterable)': Extends the left end of the deque by appending elements from the iterable in reverse order.
'rotate(n)': Rotates the deque to the right (positive `n`) or left (negative `n`) by `n` steps.

double_ended_queue = deque([1, 2, 3])
double_ended_queue.extend([6, 7, 8])
double_ended_queue.extendleft([-3, -2, -1])
double_ended_queue.rotate(2)

Output: ----------------------------------------
Deque Initially:
deque([1, 2, 3])

Deque after extending to the right:
deque([1, 2, 3, 6, 7, 8])

Deque after extending to the left:
deque([-1, -2, -3, 1, 2, 3, 6, 7, 8])

deque after rotating 2:
deque([7, 8, -1, -2, -3, 1, 2, 3, 6])

Real-World Applications

1. Efficient Windowed Iterations

Deques are ideal for maintaining a sliding window of elements efficiently.

def sliding_window(iterable, size):
    d = deque(maxlen=size)
        for item in iterable:
            d.append(item)
            if len(d) == size:
                yield tuple(d)

data = [1, 2, 3, 4, 5, 6, 7, 8]
windows = list(sliding_window(data, 3))

Output:----------------------------
Sliding windows of size 3: [(1, 2, 3), (2, 3, 4), (3, 4, 5), (4, 5, 6), (5, 6, 7), (6, 7, 8)]

2. Undo/Redo Functionality

Deques are often used to implement undo and redo functionality in applications.

undo_stack = deque()
redo_stack = deque()

def perform_action(action):
    # Perform the action
    # ...
    # Add to undo stack
    undo_stack.append(action)

    # Undo
    undone_action = undo_stack.pop()
    redo_stack.append(undone_action)

    # Redo
    redone_action = redo_stack.pop()
    undo_stack.append(redone_action)

Output:----------------------------------
Undoing the last action and redoing it.

Conclusion

In this article, we have highlighted its basic operations, advanced functionalities and real-world applications. Deque shines in scenarios that require efficient append and pop operations on both ends, making them a valuable asset in your programming toolkit.

As you continue your journey in Python, experiment with these tools in your projects, and see how Deque optimizes performance and simplifies complex tasks.
Happy coding!

Python