Double ended queue or Deque is a linear data structure in which we can insert or remove elements from both its ends i.e. It supports last in first out (LIFO) operations as well as first in first out (FIFO) operations. Deque module is a part of collections library in python and we can perform insertion, deletion or counting the number of elements in the deque using the inbuilt methods in the deque module. In this article, we will try to understand the deque module by implementing programs in python.
How to use the deque module in Python?
To use deque in python, we will first import the module using the import statement as follows.
from collections import deque
After importing the deque module, we can declare a deque object using deque() method. The deque() method takes an iterable object such as list or tuple as input argument, creates a deque object and returns a reference to the deque object. This can be implemented as follows.
from collections import deque
myDeque= deque([1,2,3,4,5])
print("The created deque is:")
print(myDeque)
Output:
The created deque is: deque([1, 2, 3, 4, 5])
- Advanced SQLite Usage in Python
- How to Pickle Unpickle Tutorial | Understanding Python Pickling & Unpickling with Example
- Python Programming – Python Modules
How to insert elements in a deque?
We can insert elements in a deque using several methods defined in collections.deque module.
To insert an element at the start of the deque, we can use the appendleft() method. The appendleft() method takes an element as input when it is invoked on a deque object and adds the element to the start of the deque. This can be seen in the following example.
print("Deque before insertion:")
print(myDeque)
myDeque.appendleft(0)
print("Deque after insertion of element 0 at start:")
print(myDeque)
Output:
Deque before insertion: deque([1, 2, 3, 4, 5]) Deque after insertion of element 0 at start: deque([0, 1, 2, 3, 4, 5])
To insert an element at the end of the deque, we can use the append() method. The append() method takes an element as input when it is invoked on a deque object and adds the element to the end of the deque. This can be seen in the following example.
print("Deque before insertion:")
print(myDeque)
myDeque.append(6)
print("Deque after insertion of element 6 at end:")
print(myDeque)
Output:
Deque before insertion: deque([0, 1, 2, 3, 4, 5]) Deque after insertion of element 6 at end: deque([0, 1, 2, 3, 4, 5, 6])
We can also insert multiple items at the same time into a deque. To insert multiple elements at the start of a deque, we can use extendleft() method. The extendleft() method takes an iterable such as list or tuple as input when it is invoked on a deque and adds the elements to the start of the deque in reversed order as that of passed in the input as follows.
print("Deque before insertion:")
print(myDeque)
myDeque.extendleft([-2,-3,-4])
print("Deque after insertion of multiple elements at start:")
print(myDeque)
Output:
Deque before insertion: deque([0, 1, -1, 2, 3, 4, 5, 6]) Deque after insertion of multiple elements at start: deque([-4, -3, -2, 0, 1, -1, 2, 3, 4, 5, 6])
To insert multiple elements at the end of a deque, we can use extend() method. The extend() method takes an iterable such as list or tuple as input when it is invoked on a deque and adds the elements to the end of the deque as follows.
print("Deque before insertion:")
print(myDeque)
myDeque.extend([-5,-6,-7])
print("Deque after insertion of multiple elements at end:")
print(myDeque)
Output:
Deque before insertion: deque([-4, -3, -2, 0, 1, -1, 2, 3, 4, 5, 6]) Deque after insertion of multiple elements at end: deque([-4, -3, -2, 0, 1, -1, 2, 3, 4, 5, 6, -5, -6, -7])
We can also insert an element at a specific position in a deque using insert() method. The insert() method when invoked on a deque, takes the index at which the element has to be inserted as first argument and the element itself as second argument and inserts the element at the specified index as follows.
print("Deque before insertion:")
print(myDeque)
myDeque.insert(2,-1)
print("Deque after insertion of element -1 at index 2:")
print(myDeque)
Output:
Deque before insertion: deque([0, 1, 2, 3, 4, 5, 6]) Deque after insertion of element -1 at index 2: deque([0, 1, -1, 2, 3, 4, 5, 6])
How to delete an element from a deque in Python?
We can remove an element from a deque from its start as well as from the end. To delete an element from the start of a deque, we use popleft() method. The popleft() method when invoked on a deque, deletes the first element in the deque and returns the value of the element. If the deque is empty, the popleft() method raises an exception named IndexError with a message “pop from an empty deque”. To handle this exception, we can use exception handling using python try except. This can be implemented as follows.
print("Deque before deletion of leftmost element:")
print(myDeque)
try:
myDeque.popleft()
except IndexError:
print("Deque is empty")
print("Deque after deletion of leftmost element:")
print(myDeque)
Output:
Deque before deletion of leftmost element: deque([-3, -2, 0, 1, -1, 2, 3, 4, 5, 6, -5, -6, -7]) Deque after deletion of leftmost element: deque([-2, 0, 1, -1, 2, 3, 4, 5, 6, -5, -6, -7])
To delete an element from the end of a deque, we can use pop() method. The pop() method when invoked on a deque, deletes the last element in the deque and returns the value of the element. If the deque is empty, the pop() method raises an exception named IndexError with a message “pop from an empty deque”. To handle this exception, we can use exception handling using python try except. This can be implemented as follows.
print("Deque before deletion of rightmost element:")
print(myDeque)
try:
myDeque.pop()
except IndexError:
print("Deque is empty")
print("Deque after deletion of rightmost element:")
print(myDeque)
Output:
Deque before deletion of rightmost element: deque([-2, 0, 1, -1, 2, 3, 4, 5, 6, -5, -6, -7]) Deque after deletion of rightmost element: deque([-2, 0, 1, -1, 2, 3, 4, 5, 6, -5, -6])
We can also delete any specific element from a deque using remove() method. The remove method takes the element as input when invoked on the deque and deletes the first occurrence of the element. When the element to be deleted is not present in the deque, the remove method raises a ValueError exception with a message “deque.remove(x): x not in deque” .To handle this exception, we can use exception handling using try except blocks in python. This can be implemented as follows.
print("Deque before deletion of element -1:")
print(myDeque)
try:
myDeque.remove(-1)
except ValueError:
print("Value is not present in deque")
print("Deque after deletion of element -1:")
print(myDeque)
Output:
Deque before deletion of element -1: deque([-2, 0, 1, -1, 2, 3, 4, 5, 6, -5, -6]) Deque after deletion of element -1: deque([-2, 0, 1, 2, 3, 4, 5, 6, -5, -6])
Count the occurrence of specific element in a deque
To count the number of times an element is present in a deque, we can use the count() method. The count() method when invoked on a deque takes the element as input returns the number of occurrences of the element in the deque. This can be seen in the following example.
print("Deque is:")
print(myDeque)
n=myDeque.count(2)
print("Number of occurrences element 2 in deque is:")
print(n)
Output:
Deque is: deque([-2, 0, 1, 2, 3, 4, 5, 6, -5, -6]) Number of occurrences element 2 in deque is: 1
Reverse the elements in a deque
We can reverse the elements in a deque using reverse() method. The reverse() method when invoked on a deque, reverses the order of the elements as follows.
print("Deque is:")
print(myDeque)
myDeque.reverse()
print("Reversed deque is:")
print(myDeque)
Output:
Deque is: deque([-2, 0, 1, 2, 3, 4, 5, 6, -5, -6]) Reversed deque is: deque([-6, -5, 6, 5, 4, 3, 2, 1, 0, -2])
Search an element in a deque
We can search an element in a deque using the index() method. The index() method when invoked on a deque takes the element, start index to begin search and end index to stop search as first ,second and third argument respectively and returns the first index where the element is present. When the element is not present. The index() method raises a ValueError with a message that element is not in deque. We can handle the exception using try except blocks and give proper output as follows.
print("Deque is:")
print(myDeque)
try:
n=myDeque.index(4,0,9)
print("Element 4 is at index")
print(n)
except ValueError:
print("Value is not present in deque")
Output:
Deque is: deque([-6, -5, 6, 5, 4, 3, 2, 1, 0, -2]) Element 4 is at index 4
How to rotate a deque in Python?
We can rotate a deque a specified number of steps rightwards using rotate() method. The rotate() method when invoked on a deque takes the number of steps the deque has to be rotated as input and rotates the array as follows.
print("Deque is:")
print(myDeque)
myDeque.rotate(3)
print("deque after rotationg three steps rightwards is:")
print(myDeque)
Output:
Deque is: deque([-6, -5, 6, 5, 4, 3, 2, 1, 0, -2]) deque after rotationg three steps rightwards is: deque([1, 0, -2, -6, -5, 6, 5, 4, 3, 2])
Conclusion
In this article, we have introduced the deque module and its methods in python. To gain more insight into it and understand how deque is different from other data structures like python dictionary, list and set , copy the code into your IDE and experiment with the deque operations. Stay tuned for more informative articles.