Data structures play a significant role in arranging data in a specific format or order. Deque is a data structure that has a wide range of real-life applications.
In general, the deque is a queue-like data structure that can add and remove elements from either end. Deque is a sub-category of queue we can implement in a job scheduling algorithm, browser history management, stock or money control app, etc.
Also, you might know that while working with Python lists, they do not execute efficiently while performing item pop or appending operations on their left end. That is where deque can work best.
We can write various other Python code to perform various Deque operations.
This tutorial will give you a quick walkthrough of the different Deque operations we can accomplish using Python. This tutorial will also highlight the differences between deque and other well-known data structures.
What is a deque?
A double-ended queue (Deque) is a Python module that comes as a segment of the collection library. It has the quality to insert and delete data from both ends of the queue.
We can directly invoke adding and removing data elements from this data structure by passing parameters to its various built-in functions. Some of the operations we can perform through Deque are:
- Inserting element
- Extending data
- Popping element
- Removing element
- Reversing all elements
Create an empty deque
Creating an empty deque is easy & straightforward in Python. Programmers use the collection.deque() method to declare an empty deque.
But before that programmers have to import the collection library and then call the collection.deque() method within it. Let us take a sample code snippet to show you.
import collections # creating an empty deque dq = collections.deque() print(type(dq))
Here we have imported the collection library and then called the collection.deque() method within it. Finally, we use the type() within the print() function to show you the type of object “dq” has turned into.
Create a shared deque
We can share data between threads using a shared deque. Python’s deque also helps in developing multithreaded applications.
Raymond Hettinger, a core Python developer & creator of the deque and the collections library, showed how deque works well with multithreaded applications. Let us take a sample code snippet to show you how we can implement the shared deque with multithreading.
import logging import time import random from collections import deque import threading logging.basicConfig(level = logging.INFO, format = "%(message)s") def wait_sec(minn, maxx): time.sleep(minn + random.random() * (maxx - minn)) def produce(qu, size): while True: if len(qu) < size: value = random.randint(0, 9) qu.append(value) logging.info("Generating: %d -> %s", value, str(qu)) else: logging.info(" Queue is saturated ") wait_sec(0.1, 0.4) def consume_val(qu): while True: try: value = qu.popleft() except IndexError: logging.info(" Queue is empty ") else: logging.info(" Consumed: %d -> %s ", value, str(qu)) wait_sec(0.2, 0.7) logging.info(" Initiating Threads... \n ") logging.info(" Press Space bar to interrupt the normal execution flow \n ") shared_dequeue = deque() threading.Thread(target = produce, args = (shared_dequeue, 5)).start() threading.Thread(target=consume_val, args = (shared_dequeue,)).start()
Copy deque into array
Arrays are a collection of similar items that remain stored in consecutive memory locations. It holds a fixed number of items and is homogenous in nature.
Arrays are prominent in older languages like C, C++, Java, etc. Because of the homogeneity, it became easy to use and fast compared to lists and other ndarrays of NumPy.
The Array is a concept of storing numerous data elements of the same type together, making it easier to compute the position of each element by adding an offset to its base value/index.
To copy a deque to an array, we have to create a deque object and assign it to an array object by converting it to a Python array.
import collections from array import array # initializing array with a value a = array('i') de = collections.deque([1, 2, 3, 4, 5, 6]) print(de) a = array('i', de) print(a) print(type(a))
Sort a deque
Ordering values in Python is possible using the sorted() function. It has the potential to sort both string and numeric data. The sorted() helps sort any sequence or collection.
It just takes the sequence or collection object as a parameter inside it and returns a sorted output. Here is a code snippet of how to sort a Deque using the built-in sorted() function.
import collections de = collections.deque([2, 12, 1, 4, 8, 16]) print(sorted(de))
Here, we can see some of the characteristics of the sorted() function:
- Since it is a built-in function, it remains available under the standard Python installation. Hence it is efficient.
- By default, the sorted() function sorts the data in ascending order, which means smallest to largest.
- Also, programmers can notice that the original numbers or elements in the deque object will remain unchanged because sorted() function returns a sorted output and does not alter the original values/elements.
Remove an element
Method 1: It is possible to remove elements from a deque using the remove(specific_value) method. This method will remove the first occurrence of the value from the deque collection as determined by the value parameter.
If the deque does not contain any element within it that gets passed as parameter, the function will raise an exception of type ValueError.
Here is a code snippet showing how to use it:
import collections g = ("I", "Karlos", "Ray", "is", "a", "coder") statementDeque = collections.deque(g) removeVal = "Ray" print("Displaying deque entries before using remove() method:") print(statementDeque) statementDeque.remove(removeVal) print(" Displaying deque after removing the entry: %s" %(removeVal)) print(statementDeque)
Method 2: As we know in Deque, we can remove elements from both ends. We can use the pop() and popleft() methods to remove elements from a deque.
- pop(): This method removes an element from the right end of the deque.
- popleft():This method removes an element from the left end of the deque.
Here is a code snippet showing how to use them:
import collections g = ("I", "Karlos", "Ray", "is", "a", "coder") statementDeque = collections.deque(g) removeVal = "Ray" print("Displaying deque entries before using remove() method:") print(statementDeque) statementDeque.pop() print(" Displaying deque after removing the entry: %s" %(removeVal)) print(statementDeque) statementDeque.popleft() print(" Displaying deque after removing the entry: %s" %(removeVal)) print(statementDeque)
Check if a deque is empty
Often we need to check whether a deque is empty or not using the if statement. Here is a code snippet showing how to check it:
from collections import deque de = deque('i') print(True) if len(de) == 0 else print(False)
Now, if you remove that single element from the deque and run the code again, you will see the output as True.
Remove the deque object
It is easy to remove the entire object from the deque using the “del” keyword followed by the collection object name. Here is a code snippet showing how to use it:
import collections g = ("I", "Karlos", "Ray", "is", "a", "coder") statementDeque = collections.deque(g) del statementDeque print(" Displaying deque after removing the entire object") print(statementDeque)
Note:Since we have deleted the Deque object from the memory, it will show an error message that the Deque with the name statementDeque is not defined.
Reverse a deque
Programmers often use this operation in Python to reverse the order of the deque elements. Programmers use the in-built collections module (a container that stores data) in Python.
This ‘collections’ provides other data structures for collections of data. The syntax of using the collections in Python is –
variable_name2 = collections.deque (variable_name1)
, where variable_name2 declares the deque collections on the elements assigned to the first variable (variable_name1).
Programmers declare the elements of a queue assigned to a variable (say ‘deq’). Lastly, programmers use the reverse operation to reverse the order of the deque elements. The syntax of the reverse operation is:
import collections deq = (2, 4, 6, 8, "Python", "Programming", 12, 14, 16, 18, 20) deqObject = collections.deque (deq) print ("Deque object before reversal:") print(deqObject) retVal = deqObject.reverse() print ("Deque object after reversal:") print (deqObject)
According to the above explanation, the deq is the variable_name1, and deqObject is the variable_name2.
How much memory does deque use?
Often, we create a Deque using any other sequence or complex data types like lists or ndarrays. These objects can take heterogeneous and homogenous data, respectively.
Thus, depending on the type and the number of primary data these objects hold, the size gets determined accordingly.
Get the index of the element in deque
In Python, index() searches for the elements in a deque. This index() method allows programmers to find the index position of the elements or an item in a deque or a list of elements.
So first, programmers need to declare the elements of the deque assigned to a variable. Deque indexing in Python is zero-based. The first element of the deque has 0 as an index.
The successive elements have 1, 2, and so forth. The index() will return the first index of the elements declared in the parameter and starts searching from the beg to end index.
The index() method returns the index at which the interpreter founds the element in the python deque. The syntax of the index() method is:
variable_name.index (element_to_be_found, beginningIndex, endIndex)
import collections x = collections.deque(("Apple", "is", "a", "fruit", "let", "us", "Python", "a", "b", 12, 30, "in", "programming", 1)) beg = 3 end = 8 find = "let" position = x.index(find, beg, end) print("The word '%s' is found at index:%d"%(find, position))
Explanation – In the above code snippet, x is the variable to which we have assigned the list of deque elements. Then, we declare the beg and the end index of the deque with the element we want to find.
Lastly, we use the index() method assigned to a variable (position) and print it.
Slice a deque
The slice() function returns a portion of a slice object depending on the slice range in Python. Programmers use the slice object to define how to slice a deque.
They can also specify where the slicing will start and end. In addition to these steps, programmers can determine the steps that help them to slice only each item one by one.
import collections import itertools deque1 = collections.deque ((10, 6, 4, 9, 8, 2, 5, 3)) print (list (itertools.islice(deque1, 3, 6)))
Explanation – In the above code snippet, we are using the collections and itertools to slice a portion of the elements of the Python deque.
The collections and itertools are inbuilt modules that help programmers to manage the iterators efficiently.
Here, the islice() is a function that allows programmers to loop through an iterable using a start and stop.
Check the length of deque
Method 1 – The len() method renders the most widely used and easy way to check the length of a deque in Python.
import collections import itertools deque1 = collections.deque ((10, 6, 4, 9, 8, 2, 5, 3)) print (len(deque1))
Method 2 – Another method of getting the length of a deque in Python is as follows:
The code snippet is:
import collections import itertools deque1 = collections.deque ((10, 6, 4, 9, 8, 2, 5, 3)) # Printing deque1 print ("The deque is : " + str(deque1)) # here, we are checking the length of the deque # using loop # and initializing the counter counter = 0 for i in deque1: # incrementing counter counter = counter + 1 # Printing length of list print ("Length of deque using naive method is : " + str(counter))
Here, we are using the native method to find the length of the deque.
Find an element in a deque
Programmers can use the index() function to find. If programmers provide the start and stop parameters with the function, it restricts finding the elements within the defined indexes start and stop. The syntax is:
index (demo [start, [stop]])
import collections deq = collections.deque(("Apple", "is", "a", "fruit", "let", "us", "Python", "a", "b", 12, 30, "in", "programming", 1)) start = 3 stop = 8 demo = "let" position = deq.index(demo, start, stop) print("The word '%s' is found at index:%d"%(demo, position))
Check the size of deque
In Python, to check the deque size, programmers can use the built-in function len().
import collections import itertools deque1 = collections.deque ((10, 6, "Python", 9, "a", 2, 5)) print (len(deque1))
Get elements of a deque without deleting them
There are two methods of accessing elements of a deque. These are as follows:
Method 1 – Programmers can get similar results by obtaining the deque elements with square brackets, though the deque data structure from the ‘collections’ module does not contain the peek() method.
Programmers can access the first element using  and the last element using [-1].
from collections import deque # we create a deque demo = deque(['a', 'b', 'c', 'd', 'e', 'f']) # We display the deque using print print(demo) # Here, we are accessing the first element print (demo) # Here, we are accessing the last element print (demo[-1])
Method 2 – With the popleft() and pop() method – Programmers can use the popleft() to access the first element or the left-most element from the deque.
Also, they use the pop() method to access the last element or the right-most element from deque.
from collections import deque # we create a deque demo = deque(['a', 'b', 'c', 'd', 'e', 'f']) # We display the deque using print print(demo) # Here, we are accessing the last element print(demo.pop()) # Here, we are accessing the first element print(demo.popleft()) print (demo)
Deque vs. Queue in Python
|Add & delete elements||In deque, programmers can add and delete elements from both sides, i.e., from both front and rear.||In the queue, programmers can add and delete elements from only one end, i.e., either from the rear or front.|
|Accessing the elements||Programmers can easily access the elements of a deque using the iterators.||In a queue, programmers cannot access elements using iterators.|
|Nature||Deque is a hybrid data structure having the properties of both stack and queue in a single data structure.||A queue is a single data structure having properties of only a queue data structure.|
|Efficiency while deletion||In deque, we can delete elements more easily as deque has the property of deletion from both sides, front and, rear. Thus, the deletion of deque elements is more efficient.||The deletion is less efficient in a queue because there is only one end to delete elements, i.e., from the front.|
|Efficiency while insertion||In deque, we can insert elements more easily as deque has the property of insertion from both sides, front and, rear. Thus, the insertion of deque elements is more efficient.||The insertion is less efficient in a queue because there is only one end to insert elements, i.e., from the rear.|
|Functions for deletion||In deque, programmers have two functions to for the deletion of elements, i.e., pop_back() and pop_front(). The pop_back() will delete the element and the pop_front() will remove the elements from the deque from front end.||In a queue, it has only one function that allows programmers to remove elements, i.e., the pop(). When programmers use the function, it automatically removes the queue element from the front end.|
|Functions for insertion||There are two functions for insertion of the elements in deque, i.e., push_front() and push_back(). The push_front() will insert the elements at the front, while the push_back() will insert elements from the rear.||In a queue, programmers can use only the push() function to insert elements. The insertion takes place at the rear of the queue.|
|Implementation||Programmers can implement deque as dynamic arrays in the program since deque has the property of expansion and contraction from both sides (ends).||Programmers can implement queues as container adaptors since insertion and deletion cannot happen from both ends.|
Stack vs. Deque in Python
|Nature||A stack is a linear data structure and abstract data type.||A deque is a hybrid data structure having the properties of both stack and queue in a single data structure.|
|Insertion of elements||Programmers can insert elements from only one end in a stack.||In deque, programmers can insert elements from both sides, i.e., from both front and rear.|
|Insertion mechanisms||The insert operation in a stack is known as a Push operation, and programmers can add elements using the push() operation.||There are five functions in deque, i.e., append(), appendleft(), insert(index, value), extend(list) and extendleft(list) to add elements.|
|Deletion of elements||In a stack, there is one and only one end. Programmers can delete elements from only one end.||In deque, programmers can delete elements from both sides, i.e., from both front and rear.|
|Deletion Mechanism||The delete operation in a stack is known as a Pop operation, and programmers can remove elements using the pop() operation.||There are three functions in deque, i.e., pop(), popleft() and remove(value) to remove elements.|
|Pointer||In the stack data structure, there is one and only one pointer that points to the top element.||But, in deque, it requires two pointers to point to the rear and front ends, respectively.|
List vs. Deque in Python
|Reallocation||In the list, the property of reallocation allows programmers to access its elements directly by indexation.||Whereas, in deque, it does not allow a programmer to execute reallocation and find an element by indexation.|
|Append and pop operations||In a Python list, programmers cannot append or pop elements from both sides. It allows fast pop and appends operation but only at the end.||But, deques provide the benefit of popping and appending from both the left and right sides of the deque. Thus, programmers implement them as a double-ended data structure.|
|Productivity||When a programmer brings changes to a list, it triggers the reallocation process. But it takes extra time on its own.||While in deque, when programmers perform the pop and append operations, these are consistent.|
|Efficiency||A list is less efficient than a deque since programmers can insert and delete from only one end.||But, in deque, programmers can append and pop elements from both ends, i.e., rear and front. Thus, this property makes it more efficient.|
We hope this article has given you a comprehensive idea of what deque is and how to deal with Python Deque through the “collections” module. This piece also chalks out a detailed set of code snippets with output on handling deque elements in Python code.
Gaurav is a Full-stack (Sr.) Tech Content Engineer (6.5 years exp.) & has a sumptuous passion for curating articles, blogs, e-books, tutorials, infographics, and other web content. Apart from that, he is into security research and found bugs for many govt. & private firms across the globe. He has authored two books and contributed to more than 500+ articles and blogs. He is a Computer Science trainer and loves to spend time with efficient programming, data science, Information privacy, and SEO. Apart from writing, he loves to play foosball, read novels, and dance.