
Data structures are data management formats that enable efficient access and modification of a collection of data values. It is comprised of data values, relationships between the values, and functions that can be used on them. In this post, we will discuss how we can use the ‘deque’ data structure in Python. The examples in this post are based off of the ‘Data Structures and Algorithms’ chapter of the _Python Cookbook_.
UNDERSTANDING DEQUES
‘Deque’ is an acronym for double ended queue. It is a sequence container where elements can be appended or removed from either end. ‘Deques’ are useful when you want to keep a limited history of the last few items seen during iteration or another form of processing. For example, suppose you want to perform a simple text match on a sequence of lines in the following text containing an Amazon review for _Python Cookbook_ :

Let’s import ‘deque’ from the collections package:
from collections import deque
Next, let’s define a ‘deque’ object with a max length of 5:
previous_lines = deque(maxlen=5)
To motivate use for ‘deque’ data structures, let’s begin by iterating over the text file and printing each line:
with open('amazon_review.txt') as f:
for line in f:
print(line)

Next let’s check for the presence of the ‘Python’ in each line and print the line if it is present:
with open('amazon_review.txt') as f:
for line in f:
if 'Python' in line:
print(line)

Now we define a generator function, which is a function that behaves like an iterator. As we iterate over the text file, each line is appended to the ‘deque’, ‘previous_line’, before moving on to the next line:
def search_text(pattern):
previous_lines = deque(maxlen=5)
with open('amazon_review.txt') as f:
for line in f:
if pattern in line:
yield line, previous_lines
previous_lines.append(line)
We can then iterate over the ‘search_text()’ function with the search patter ‘Python’. I’ll truncate the output to include a few appended lines:
for line, previous_lines in search_text('Python'):
print(line, previous_lines)

We can further iterate over the ‘deque’ data structures. Here we limit the history to max length = 5:
for line, previous_lines in search_text('Python'):
for pline in previous_lines:
print(pline, end='')

Again, the purpose of using a ‘deque’ data structure is to limit the history to the last few items seen during iteration.
We can define a function that generalizes this logic:
def search_text(lines, pattern, history=5):
previous_lines = deque(maxlen=history)
for line in lines:
if pattern in line:
yield line, previous_lines
previous_lines.append(line)
And call our function with our input values:
if __name__ == '__main__':
with open('amazon_review.txt') as f:
for line, previous_lines in search_text(f, 'Python', 5):
for pline in previous_lines:
print(pline, end='')
print(line, end='')
print('-'*150)

Next, I will walk through some of the methods available to ‘deque’ objects. Let’s define a fixed-sized ‘deque’ object of a length 3:

Now, let’s append a few string values. Let’s append a few website URLs:

If we add another element:

As you can see, ‘ https://pythonprogramming.net‘ was added to the ‘deque’, ‘https://www.kaggle.com‘ and ‘https://www.kdnuggets.com‘ shifted down, and ‘https://www.python.org‘ was removed.
We can use the ‘appendleft()’ method to add an element to the bottom of the ‘deque’. Let’s add the link to the documentation for the Pandas library:

We can use the ‘pop()’ method to remove the element at the top of the ‘deque’:

We can also use ‘popleft()’ to remove from the bottom of the ‘deque’:

Adding (appending) or removing (popping) items to/from either end of a queue has constant time O(1) complexity, unlike lists which have O(N) (linear time complexity).
I’ll stop here, but feel free to apply this code to other text files and play around with the search method input values. For example, you can try to change the max length (history) and search for alternative text patterns.
CONCLUSIONS
To summarize, in this post we discussed a use case for the ‘deque’ data structure using an implementation in python. These data structures are useful when you need to keep a limited history of information. Though we used a text matching example, ‘deques’ are also useful for storing web browser history. Similar to the last example shown, recently visited URLs are added to the front of the ‘deque’ and the URLs in the back of the ‘deque’ are removed after a certain number of insertions. I hope you found this post helpful/interesting. Leave a comment if you have any questions. The code from this post is available on GitHub.