If you’re a Python developer, you’ve likely heard of a deque, or “double-ended queue.” It’s a powerful tool that can increase your application’s efficiency and speed up its performance.
A deque is a specialized container data type that offers quicker append and pop operations from both ends of the container. This makes it a valuable tool for implementing queues and stacks, which are common list-like data types in computing.
It’s a low-level and highly optimized data structure that is very useful for a variety of applications. As a Python programmer, a deque is one tool that you’re going to want to have in your arsenal.
Keep on reading to learn more about Deques and how you can implement them in your Python code!
What is a Deque?
If you’re new to Python or computer programming in general, you might be wondering what a deque is. Deque stands for “double-ended queue,” and it’s a data structure that allows you to add and remove elements from both ends of the queue.
It’s similar to a regular queue but with the added flexibility of being able to add and remove elements from both the front and back of the queue. This is possible because Python’s deque is implemented as a doubly linked list.
In Python, deques are implemented using the collections module, which provides a deque class. This class provides a number of methods for adding and removing elements from the deque.
It also provides functions for other useful operations such as rotating the deque or clearing it entirely.
Features of A Python Deque
Unlike a regular list, which has an O(n) time complexity for append and pop operations, a deque provides an O(1) time complexity. This makes it significantly faster and memory efficient for these read-and-write operations.
Here are some more Python deque features you should know about:
It is a mutable data structure.
It can store multiple data types e.g., Integers, tuples, arrays, etc.
It supports indexing, but not slicing operations.
It doesn’t support in-place sorting
It supports common built-in iterable functions and operations like in, sorted(), len(), reverse(), etc.
Applications of A Deque
Deques are useful for a variety of reasons. For example, they can be used to implement a queue or a stack, both of which are common data structures in computer science.
They can also be used to efficiently process data in real-time, such as in streaming applications or in systems that require fast access to data.
In addition to being used for queues and stacks, deques can also be used for implementing breadth-first search algorithms. They are also useful for maintaining a sliding window of items in a larger sequence.
How to Create and Initialize a Deque
You can create a deque using a built-in function from the collections module. Let’s take a close look at how you can create and fill up this data structure.
Using the deque() Function
To create a deque in Python, you can use the built-in deque() function from the collections module. This function returns a new empty deque object that you can use to implement a double-ended queue.
Here is an example of how to create an empty deque object:
from collections import deque
my_deque = deque() You can also create a deque with initial elements by passing an iterable (list, tuple, etc.)to the deque() function. The deque will be initialized with the elements in the iterable, from left to right.
Here is an example:
from collections import deque
my_list = [1, 2, 3, 4, 5]
my_deque = deque(my_list)Initializing a Deque with Elements
You can also initialize an empty deque with elements using various methods. One way to do this is to use the append() and appendleft() methods to add elements to the deque from the right and left sides, respectively.
Here is an example:
from collections import deque
#Initialize the empty deque
my_deque = deque()
print(my_deque)
#Add Values to the deque
my_deque.append(1)
my_deque.append(2)
my_deque.appendleft(3)
print(my_deque)After running this code, the deque will contain the elements [3, 1, 2].
Another way to initialize a deque with elements is to pass a list of elements to the deque() function.
Here is an example:
from collections import deque
my_deque = deque([1, 2, 3]) Running this code will create a deque object containing the elements [1, 2, 3].
Overall, creating and initializing a deque in Python is straightforward and can be done using the built-in deque() function. You can also do this by adding elements to an empty deque using the append() and appendleft() methods.
How to Perform Common Deque Operations
There are many operations you can perform on deque objects in Python. Let’s check out some of the more popular ones.
Adding Elements to a Deque
You can add elements to a Python deque using the append() and appendleft() methods. The append() method adds an element to the right end of the deque while the appendleft() method adds an element to the left end of the deque.
Here’s an example:
import collections
# Create an empty deque
my_deque = collections.deque()
# Add elements to the deque
my_deque.append(1)
my_deque.appendleft(2)
my_deque.append(3)
print(my_deque)
# Output:
deque([2, 1, 3])Adding Multiple Data Elements to A Deque
If you don’t want to add data elements to a deque one by one, you can speed up the process with the extend() or extendleft() functions. These functions take in an iterable and append the iterable’s content to the end or left end of the deque respectively.
Here’s an example:
from collections import deque
my_list = [1, 2, 3, 4, 5]
my_deque = deque(my_list)
#Creating a tuple and list
cont = (11, 12, 13, 14)
full = [10,20,30]
#Extending the deque from the right
my_deque.extend(cont)
print(my_deque)
#Extending the deque from the left
my_deque.extendleft(full)
print(my_deque)In the code above the extend() function appends the multiple values in the cont tuple to the end of the deque. Next, the extendleft() function appends the multiple data elements in the full list to the left end of the deque.
Removing Elements from a Deque
You can remove elements from a Python deque using the pop() and popleft() methods. The pop() method removes and returns the rightmost element of the deque while the popleft() method removes and returns the leftmost element of the deque.
Here’s an example:
import collections
#Create a deque with some elements
my_deque = collections.deque([1, 2, 3, 4, 5])
#Remove elements from the deque
my_deque.pop()
my_deque.popleft()
print(my_deque)
# Output: deque([2, 3, 4])You can also remove a specific value from a deque using the remove() function. The function removes the first occurrence of the specified value from the deque.
Here’s an example:
import collections
#Create a deque with some elements
my_deque = collections.deque([1, 2, 1, 4, 5])
#Remove elements from the deque
my_deque.remove(1)
print(my_deque)
# Output: deque([2, 1, 4, 5])If the element is not found, Python will return a ValueError.
Removing All Elements From a Deque
To remove all the elements from a Deque and return it to an empty state, we can use the clear() function. Here’s how it works:
from collections import deque
#Create a deque with some elements
my_deque = deque([1, 2, 1, 4, 5])
#Remove all elements from the deque
my_deque.clear()
print(my_deque)
# Output:
deque([])Accessing Elements of a Deque
You can access elements of a Python deque using the indexing operator []. You can also use a negative value in the indexing operator to access the deque elements from the right.
The indexing starts from 0 for the leftmost element and -1 for the rightmost element. Here’s an example:
import collections
# Create a deque with some elements
my_deque = collections.deque([1, 2, 3, 4, 5])
# Access elements of the deque
print(my_deque[0])
# Output: 1
print(my_deque[-1])
# Output: 5 Modifying Elements of a Deque
You can modify elements of a Python deque using the indexing operator “[]” and the assignment operator “=“. Here’s an example:
from collections import deque
# Create a deque with some elements
my_deque = deque([1, 2, 3, 4, 5])
print(my_deque)
# Modify elements of the deque
my_deque[0] = 10
my_deque[-1] = 50
print(my_deque) In the above code, the indexing operator changes the first and last elements of the deque to 10 and 50 respectively.
These are the basic operations you can perform on a deque object in Python. With these operations, you can efficiently implement various data structures such as queues, stacks, and more.
How to Work with a Deque as a Queue
You can use a deque in Python to implement a queue data structure. A queue is an abstract data type that operates on a first in first out (FIFO) basis.
What this means is that you can append new items from one end of the queue and push out old items from the other end.
A good way to explain this is a line at a store. Typically, the first person to arrive will be at the head of the line and will be attended to first.
New arrivals will have to head to the back of the line and wait their turn. So, the first in will be the first answered, while the last in will be the last attended to.
Here’s how you can use a deque to implement queues.
Using append() and popleft() Methods
To use a deque as a queue, you can use the append() method to add elements to the right end of the deque. Additionally, you can use the popleft() method to remove elements from the left end of the deque.
This is a very efficient way to implement a queue in Python. Here is an example:
from collections import deque
queue = deque()
queue.append(1)
queue.append(2)
queue.append(3)
print(queue)
# Output: deque([1, 2, 3])
x = queue.popleft()
print(x)
# Output: 1
print(queue)
# Output: deque([2, 3]) As you can see, the append() method adds elements to the right end of the deque, and the popleft() method removes elements from the left end of the deque.
This is exactly what we need in a queue implementation.
Checking if a Deque Queue is Empty
To check if a deque is empty, you can use the not operator. Here is an example:
from collections import deque
queue = deque()
if not queue:
print("Queue is empty")
else:
print("Queue is not empty") This will output “Queue is empty” because the deque is empty. If you add elements to the deque, it will no longer be empty.
In conclusion, using a deque as a queue in Python is very efficient and easy to implement.
Working with Deque as a Stack
Just like queues, stacks are another example of abstract data types that you can use in organizing data. Unlike queues, stacks operate in a last in first out (LIFO) fashion.
This means the last element into the deque will be the first element out. Here’s how you can implement this using the underlying data structure.
Using append() and pop() Methods
When using Deque as a stack, you can add elements to the top of the stack using the append() method. This method adds the element to the right end of the deque.
Similarly, you can remove elements from the top of the stack using the pop() method. This method removes and returns the rightmost element of the deque.
For example, let’s say you have a deque called “my_stack” and you want to add an element to the top of the stack. You can use the following code:
my_stack.append(5) This will add the element 5 to the top of the stack.
If you want to remove the top element from the stack, you can use the pop() method: `
bal = my_stack.pop()
print(bal)
# Output: 5This will remove and return the rightmost element of the deque, which in this case is 5.
Checking for an Empty Deque Object
You can check if a deque stack is empty by using the boolean operator “not“. If the deque is empty, “not my_deque” will return True. Otherwise, it will return False.
For example, let’s say you have a deque stack called “my_deque” and you want to check if it is empty. You can use the following code:
if not my_deque:
print("The deque is empty")
else:
print("The deque is not empty") This will print “The deque is empty” if the deque is empty. If it is not empty, the output will be “The deque is not empty“.
When working with Deque as a stack, it is important to keep track of whether the stack is empty or not. If you try to pop an element from an empty stack, you will get an IndexError.
What is A Restricted Deque?
A restricted deque is a double-ended queue with some restrictions placed on data append and pop operations on either end of the deque. There are two main types of restricted deques; Input restricted deque and output restricted deques
Let’s look at them:
Input Restricted Deque
An input-restricted deque allows you to pop or delete data elements from both ends of the deque. However, you can only insert data elements from one end of the deque.
This is very useful in applications with memory constraints. You can use it to add data elements in chronological order while retaining the ability to discard data from any end of the deque.
Output Restricted Deque
An output-restricted deque allows you to insert data from both ends of the deque. However, you can only delete items from one end of the deque called the front end.
An output-restricted deque is very useful in cases where you need to implement a FIFO data structure, but still want the functionality to append data from both ends.
Let’s Wrap This UP
By now, you should have a good understanding of the deque module in Python and how it can be used to implement efficient queues and stacks.
Deques are a versatile data structure that offers many advantages over traditional lists. These advantages are apparent when it comes to memory-efficient append and pop operations.
They are also a great choice when you need to implement a stack or a double-ended queue. Some of the key benefits of using deques include:
Efficient O(1) append and pop operations from both ends of the deque
Fast O(1) access to the first and last elements of the deque
Built-in support for thread-safe, atomic operations
Flexible methods for inserting, removing, and rotating elements in the deque
Overall, the deque module is a powerful tool that can help you write more efficient and maintainable Python code. Whether you are working on a small script or a large-scale project, deques are definitely worth considering as an alternative to traditional lists or other data structures!
Ready to learn more about Python, checkout our playlist below
