Python

Python deque tutorial (Simple Examples)

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

In Python, Deque or Double-ended queue can add and remove elements from both rear and front ends.

 

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))

Output
This is an example of emptying a deque in Python.
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()

Output
This is an example of sharing a deque in Python.

Here we used the time module and the random module to get random sleep seconds.

 

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))

Output
This is an example of copying a deque into array in Python.

 

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))

Output
This is an example of sorting a deque in Python.
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)

Output
This is an example of removing element from a deque in Python.

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)

Output
This is an second example of removing element from a deque in Python.

 

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)

Output
This is an example of checking if a deque is empty in Python.
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)

Output
This is an example of removing deque objects in Python.
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:

deque_name.reverse()
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)

Output
This is an example of reversing the elements of a deque in Python.
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))

Output
This is an example of getting index of the elements of a deque in Python.

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)))

Output
This is an example of slicing a deque in Python.

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))

Output
This is an example of finding the length of a deque in Python.

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))

Output
This is an second example of finding the length of a deque in Python.

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))

Output
This is an example of finding an element of a deque in Python.

 

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))

Output
This is an example of finding the size of a deque in Python.

 

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 [0] 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[0])

# Here, we are accessing  the last element
print (demo[-1])

Output
This is an example of getting an element without deleting them from a deque in Python.

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)

Output
This is a second example of getting an element without deleting them from a deque in Python.

 

Deque vs. Queue in Python

CharacteristicsDequeQueue
Add & delete elementsIn 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 elementsProgrammers can easily access the elements of a deque using the iterators.In a queue, programmers cannot access elements using iterators.
NatureDeque 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 deletionIn 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 insertionIn 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 deletionIn 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 insertionThere 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.
ImplementationProgrammers 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

CharacteristicsStackDeque
NatureA 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 elementsProgrammers 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 mechanismsThe 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 elementsIn 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 MechanismThe 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.
PointerIn 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

CharacteristicsListDeque
ReallocationIn 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 operationsIn 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.
ProductivityWhen 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.
EfficiencyA 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.

 

Conclusion –

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.

Leave a Reply

Your email address will not be published.