How to Use a Python Deque for Fast and Efficient Queues

The list is one of the most frequently used and familiar data collections for anyone who codes regularly with Python. They are excellent data structures with lots of useful functions that let the user add, remove, and sort items. There’s no doubt that the list is the right choice for many situations, but Python also provides alternatives that are better suited to certain scenarios.

For example, lists may not be the optimal data structure for implementing stack or queue abstract data types. This is because lists are not thread-safe, which means that things can go wrong if multiple threads attempt to access and modify the same element at the same time. This gives us error messages and inconsistent data.

The queue abstract data type is one of the most popular data structures for first-in-first-out (FIFO) data problems. One way that we can efficiently implement a queue is with a doubly-linked list. These are ideal for applications where you need quick access to both the first and last elements of the queue.

In this blog post, we'll take a look at the Python deque (a double-ended queue data structure provided with the Python standard library). We will look at what a deque is, and we will cover how to use the Python deque implementation to create and manipulate data structures.

What is a Deque in Python?

A deque, also known as a double-ended queue (pronounced "deck"), is an ordered collection of items where you can add new items to either the front or the back of the queue. Deques are similar to lists, but they are more efficient at adding or removing items from the beginning or end of the list.

Deques are often used as a queue, but you can also use them as a stack.

When used as a queue, we add items to one end of the queue (usually the back) and remove them from the other end (usually the front). This represents the defining quality of a queue where items are First-In-First-Out (FIFO).

When used as a stack, we add items to one end of the queue (usually the back) and remove them from the same end (also, usually the back). This means that the deque can represent the Last-In-First-Out (LIFO) behavior of a stack. 

Python implements a deque as a doubly linked list. Each node in the list has a reference to the previous node and the next node. The head node has a reference to the tail node and the tail node has a reference to the head node.

Why Use the Python Deque?

Lists are not optimal when you need to add or remove an element from the front (index 0). In these situations, the entire list has to be shifted to the right to make space for a newly added element, or the list has to be shifted to the left to fill the gap from the newly deleted element. In either case, the time that this takes grows linearly with the list size. This means that these operations have a time complexity of O(n), or linear time complexity.

If however, you use the .append() method to add an element to the end of a list, then this will be a very fast operation with constant time complexity, or O(1). Similarly, if you remove the rightmost element using the .pop() method, then this is equally as fast. 

Deques solve the problems associated with lists when trying to access the front elements. This is because deques are implemented as a doubly-linked list with append and pop operations that are equally stable and fast. This means that deques can give us thread-safe and memory-efficient appends and pops from either side of the queue with approximately constant time complexity, or O(1).

Python Deque Characteristics

The generalized linear queue abstract data type requires that insertion must take place at one end (usually the back) and deletion at the other end (usually the front). This represents the FIFO characteristic of a queue and it can lead to several limitations for element insertion and deletion. 

The Python deque, however, allows us to access both ends of the queue for insertion and deletion.

The following are the characteristics of the Python deque:

• Deques allow memory-efficient and thread-safe appends and pops from either side of the queue with roughly constant time complexity at either end, which is O(1)
• Deques can be efficiently implemented with a variety of data structures, including arrays, linked lists, and trees
• Deques can be used as a drop-in replacement for lists in many algorithms and data structures
• Deques have more predictable worst-case performance than lists
• Deques are easier to use ‘correctly’ than lists
• Deques are more flexible than lists
• Deques are more efficient than lists in many situations
• Deques can be efficiently rotated to the left or right, this is known as a "cyclic buffer"
• Deques are a good choice for keeping track of the head and tail elements of a list
• Deques can be easily reversed without creating a new list or copying existing data
• Deques consume less memory than lists when storing large numbers of elements
• Deques can be used as a FIFO queue or a LIFO stack
• A deque is a double-ended queue, meaning it can be used as a stack or a queue
• A deque is a linear data structure that supports fast insertion and deletion at both ends
• A deque is often implemented as a dynamic array, which can be resized as needed
• A deque can be used to implement other data structures, including the stack, queue, or priority queue

Now we have seen the characteristics of the deque, let’s look at the types of deque in Python.

Types of Python Deque

Depending on the way that operations are restricted, deques can be one of two types:

1. Input-Restricted Deque
2. Output-Restricted Deque

Input-Restricted Deque

An input-restricted deque is a data structure that allows for the deletion of elements from either end of the deque, but only allows for the insertion of elements at one end of the deque.

Input-restricted deques are often used in applications where we require a queue, but the ordering of the elements is not important. For example, we could use an input-restricted deque to store CPU tasks that require processing. The CPU can remove and process the first task from the front of the deque without being concerned about the order of remaining tasks in the deque.

Input-restricted deques are also often used in applications where space is limited. This is because they only require two pointers (one for the front and one for the back of the deque) and do not require contiguous memory to store deque elements in an array.

Output-Restricted Deque

An output-restricted deque is a data structure that allows for the insertion of elements from either side of the deque, but only allows for the deletion of elements from one end of the deque.

This type of deque can be useful in situations where you need the flexibility of a FIFO queue, but you also need to delete elements from the back of the queue. For example, if you implemented a LIFO stack using an output-restricted deque, you would be able to push (insert) and pop (delete) elements at the top of the stack, which is the back of the deque.

Overall, an output-restricted deque is a versatile data structure that you can use in a variety of situations. If you need the functionality of a queue but also need the flexibility to delete from the back of the queue, then this type of deque would make sense. 

Features of a Deque

Deques allow us to perform several types of operations:

• Append items
• Pop items
• Access items
• Rotate items

More explicitly, these objects support the following Python deque methods:

The table above shows the different operations that we can perform on a deque object. In the next section, we will create a deque object and perform these operations in Python.

Operations on a Python Deque

The deque is available as a class in the collections module of the Python standard library. We can import the Python deque from the collections module and we can perform different operations on a deque object. In the next section, we will explore a Python deque example.

Inserting elements into a Python Deque

Firstly, let’s create an empty deque and then perform several operations:

from collections import deque

seq = deque() #create an empty deque
print(seq) #print the deque

seq.append(1) #use append() to insert element at right end
print('The deque after appending right:',seq) #print the deque

seq.appendleft(2) #use appendleft() to insert element at left end
print('The deque after appending left:', seq) #print the deque

seq.extend([4,5]) #use extend() to insert several elements at the right end
print('The deque after extending right:', seq) #print the deque

seq.extendleft([6,7]) #use extendleft() to insert elements at the left end
print('The deque after extending left:', seq) #print the deque

seq.insert(3,2) #use insert() to insert the value 2 at 4th position
print('The deque after inserting element:', seq) #print the deque​

The above code outputs the following:

deque([])
The deque after appending right: deque([1])
The deque after appending left: deque([2, 1])
The deque after extending right: deque([2, 1, 4, 5])
The deque after extending left: deque([7, 6, 2, 1, 4, 5])
The deque after inserting element: deque([7, 6, 2, 2, 1, 4, 5])

So what happened here? We imported the deque class from the collections module in the first step. In the second step, we created a new instance of a deque object with no values, which means we created an empty deque. 

After this, we used the .append() method to add an element to the right side of the deque. Then we used the .appendleft() method to add the element ‘2’ to the left side of the deque. 

Similarly, we used the .extend() method to add elements [4,5] to the right side of the deque, and we used the .extendleft() method to add elements [7,6] to the left side of the deque. In the last step, we used the .insert() method to add the element ‘2’ at the fourth position (which is index 3).

Now, let’s see how to remove elements from a deque object. 

Removing Elements from Python Deque

Now, we will cover the different methods to remove elements from a Python deque.

from collections import deque

seq = deque([1,2,3,4,5,6]) #create a new deque
print(seq) #print the deque

seq.pop() #use pop() to remove right most element
print(seq) #print the deque

seq.popleft() #use popleft() to remove leftmost element
print(seq) #print the deque

seq.remove(3) #use remove() to remove the given element
print(seq) #print the deque

seq.clear() #use clear() to clear all elements in the deque
print(seq) #print the deque

The above code outputs the following:

deque([1, 2, 3, 4, 5, 6])
deque([1, 2, 3, 4, 5])
deque([2, 3, 4, 5])
deque([2, 4, 5])
deque([])​

In the first step, we imported the deque class from the collections module and then defined a new deque object. Then, we used the .pop() method to remove the rightmost element from the deque object. We also used the .popleft() method to remove the leftmost element. After this, we used the .remove() method to remove the element ‘3’ by passing an argument. Lastly, we used the .clear() method to clear all of the elements in the deque, which left us with an empty deque object. 

In the next section, we will explore more of the operations that deque has to offer.

Other Operations on a Python Deque

Aside from adding and removing elements, we can perform other operations including counting elements, finding the index of an element, rotating the deque object, etc. The following code shows how these operations work:

from collections import deque

seq = deque([1,1,2,3,4,5,6]) #create a new deque
print(seq) #print the deque

a = seq.count(1) #count the occurrence of 1
print('Count of 1 is:', a) #print the count of 1

b = seq.copy() #copy the deque object using count()
print(b) #print the deque

c = seq.index(2) #get the index of the element 2
print('The index of 2:', c)  #print the index

seq.reverse() #reverse the deque object using reverse()
print(seq) #print the deque

seq.rotate(1) #rotate the deque object to the right
print(seq) #print the deque

The above code outputs the following:

deque([1, 1, 2, 3, 4, 5, 6])
Count of 1 is: 2
deque([1, 1, 2, 3, 4, 5, 6])
The index of 2: 2
deque([6, 5, 4, 3, 2, 1, 1])
deque([1, 6, 5, 4, 3, 2, 1])

In the first step we imported the deque class from the collections module and then created a deque object. Next, we used the .count() method to count the occurrence of ‘1’ in the deque, and we printed the result. We then used the .copy() method to copy the deque object to a variable, ‘b’. We used the .index() method to return the index of a random element, ‘2’. We also used the .reverse() method to reverse the deque object, and finally we rotated the deque to the right with the .rotate() method and an argument of ‘1’.

These are some of the operations that can be performed on a deque object. Other methods we can use with a Python deque implementation include .maxlen(), .len(), and .reversed().

Conclusion

The Python deque is an important data structure with many applications. In this article, we discussed what a deque is, along with the different operations that we can perform on a deque object. Deques are mainly used when:

• We need fast time complexity
• We need a small memory footprint
• We want to create a LIFO stack
• We want to create a FIFO queue

To learn more about becoming a Python expert, check out our Intro to Coding in Python article, as well as the Top Python Interview Questions and Answers.

Frequently Asked Questions

1. What Are Queues and Deques in Python?

A queue is an abstract data type that represents a list of elements with FIFO ordering. A deque is a built-in Python data structure that represents a double-ended queue where elements can be added or removed from either end.

2. Is a Python Deque a List?

No, a deque is not a list. The deque is its own data structure which is similar to a list, but with additional functionality.

3. Is the Deque Better Than a Queue in Python?

There is no definitive answer to this question since it depends on the specific needs of the program. However, in general, a deque (double-ended queue) can be more versatile than a regular queue since it allows for efficient insertion and deletion at both the front and back of the queue.

4. Why Do We Use a Deque?

A deque is used when you need a queue-like data structure that allows for fast insertion and deletion at both the front and the back of the data structure.

5. How Do I Use Deque as a Stack in Python?

There are two ways to use a python deque as a stack. The first way is to use the append() and pop() methods. The second way is to use the appendleft() and popleft() methods.

Also read: 

• Python Programming Language: Intro to Coding in Python
• The Difference Between Python 'is' vs '==' Operator