Supercharge lists in Python: deque

Welcome to the second part of my advanced Python series, where we explore the hidden gems within Python's standard library. In this post, we'll delve into the deque data structure, a versatile tool that can supercharge your algorithms and applications.

What is a Deque?

A deque, short for "double-ended queue," is a data structure that allows efficient insertion and removal of elements from both ends. This flexibility makes it a powerful tool for various algorithms and scenarios, offering a generalization of both stacks and queues.

Tailing and Iterables

One common application of deques is in tailing iterables. By utilizing a deque, you can efficiently record the tail of an iterable, adding elements to the back and removing them from the front as needed. This is particularly useful when you want to keep a fixed-size window of the most recent elements.

1
2
3
4
5
6
7
8
9
from collections import deque


def tail(iter, n=10):
    return deque(iter, n)


my_iter = range(4, 56, 2)
print(tail(my_iter, 3))  # Output: deque([10, 12, 14])

In the above example, the tail function takes an iterable and a window size n as arguments. It returns a deque containing the last n elements of the iterable.

Undo Operations and History Management

Deques are also invaluable for implementing undo operations in software applications. By using a deque as a stack, you can store a history of actions, allowing users to revert to previous states by removing actions from the back of the deque.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class History:
    def __init__(self):
        self.undo_stack = deque() 

    def perform_action(self, action):
        self.undo_stack.append(action)

    def undo(self):
        """Undoes the last action."""
        if self.undo_stack:
            action = self.undo_stack.pop()
            print(f"Undone: {action}")
        else:
            print("No action to undo.")

history = History()

history.perform_action("Open File")
history.perform_action("Edit File")
history.undo()       # Output: Undone: Edit File
history.perform_action("Save File")
history.undo()       # Output: Undone: Save File

In this example, the History class maintains an undo stack using a deque. The perform_action method adds actions to the stack, while the undo method removes the last action, effectively undoing it.

"Play Next" Music Queue

A creative application of deques is in managing a "play next" music queue. In this scenario, songs are added to the back of the deque to be played in order. However, a "play next" feature allows users to add songs to the front of the deque, ensuring they are played immediately after the current song.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
from collections import deque


class MusicPlayer:
    play_queue: deque = deque()
    playing: str | None = None

    def add(self, song: str):
        self.play_queue.append(song)

    def add_next(self, song: str):
        self.play_queue.appendleft(song)

    def play_next_song(self):
        if self.play_queue:
            self.playing = self.play_queue.popleft()
        else:
            self.playing = None

    def __str__(self) -> str:
        return f"Now playing: {self.playing}, Queue: {self.play_queue}"


player = MusicPlayer()

# Add songs to the queue
player.add("Song 1")
player.add("Song 2")
player.add("Song 3")

print(player)  # Output: Now playing: None, Queue: ['Song 1', 'Song 2', 'Song 3']

player.play_next_song()
print(player)  # Output: Now playing: Song 1, Queue: ['Song 2', 'Song 3']

player.add_next("Song 4")
print(player)  # Output: Now playing: Song 1, Queue: ['Song 4', 'Song 2', 'Song 3']

player.play_next_song()
print(player)  # Output: Now playing: Song 4, Queue: ['Song 2', 'Song 3']

In this example, the MusicPlayer class uses a deque to manage the music queue. The add method adds songs to the back of the deque, while the add_next method adds songs to the front, ensuring they are played next. The play_next_song method advances the queue, updating the currently playing song.

Conclusion

Deques are a powerful and versatile data structure in Python, offering efficient solutions for a wide range of problems. By understanding and leveraging their capabilities, you can write more elegant and optimized code, especially in scenarios where you need to manage data from both ends of a collection.

Stay tuned for the final part of our advanced Python series, where we'll explore another exciting module and its applications!

Happy coding!