Deque or doubly ended queues are linear data structures with which we can perform last in first out (LIFO) operations as well as first in first out (FIFO) operations. Deques have many applications in real life such as implementing undo operation in softwares and in storing the browsing history in web browsers. In this article, we will study the underlying concepts behind deque and will implement them in python.
How to implement deque in python?
As described above, deques are linear data structures. Thus we can implement deque using the list in python. To implement deque using list, we will have to insert and delete elements from both sides of the list. We can also perform operations like checking the length of the deque or checking if the deque is empty. For this task, we will use a dequeSize method to keep the count of the number of elements in the deque. A deque can be implemented in python using the following class definition in which we define an empty list named dequeList to initialize the empty deque and initialize dequeSize to 0 as follows.
class Deque:
def __init__(self):
self.dequeList=list()
self.dequeSize=0
- How to Check if a List, Tuple or Dictionary is Empty in Python
- Python Programming – Python Lists
- How to Slice Custom Objects/Classes in Python
Insertion in a deque in python
We can insert an element at the front as well as rear of the deque. To insert an element at the front of the deque, we can simply insert the element at the start of the dequeList using insert() method. Then we will increment the dequeSize by 1. This can be done as follows.
def insertAtFront(self,data):
self.dequeList.insert(0,data)
self.dequeSize=self.dequeSize+1
To insert an element at the rear of the deque, we will append the element at the end of the dequeList using append() method and then we will increment the dequeSize by 1. This can be done as follows.
def insertAtRear(self,data):
self.dequeList.append(data)
self.dequeSize=self.dequeSize+1
Delete element from a deque in python
We can delete an element from the front as well as the rear of a deque. Before deleting an element first we will check if the deque is empty and will raise an exception using python try except that the deque is empty. Otherwise we will proceed to delete the element from the deque.
To delete an element from front of a deque, we will delete the first element of the dequeList using pop() method and then we will decrement the dequeSize by 1. This can be done as follows.
def deleteFromFront(self):
try:
if self.dequeSize==0:
raise Exception("Deque is Empty")
else:
self.dequeList.pop(0)
self.dequeSize=self.dequeSize-1
except Exception as e:
print(str(e))
To delete an element from the rear of the deque, we will delete the element at the last position of the dequeList and decrement the dequeSize by 1. This can be done as follows.
def deleteFromRear(self):
try:
if self.dequeSize==0:
raise Exception("Deque is Empty")
else:
self.dequeList.pop(-1)
self.dequeSize=self.dequeSize-1
except Exception as e:
print(str(e))
Check the length of deque
To check the length of deque, we just have to check the value in the dequeSize field of deque which keeps the length of the deque. We can implement the length() method to check the length of the deque in python as follows.
def dequeLength(self):
return self.dequeSize
Check if the deque is empty
To check if the deque is empty, we just have to check if the dequeSize field has a value 0 in it. We can implement a method isEmpty() to check if the deque is empty or not in python as follows.
def isEmpty(self):
if self.dequeSize==0:
return True
return False
Check front and rear elements
To check the front element of the deque, we can implement the front() method as follows.
def front(self):
try:
if self.dequeSize==0:
raise Exception("Deque is Empty")
else:
return self.dequeList[0]
except Exception as e:
print(str(e))
To check the rear element of the deque, we can implement the rear() method as follows.
def rear(self):
try:
if self.dequeSize==0:
raise Exception("Deque is Empty")
else:
return self.dequeList[-1]
except Exception as e:
print(str(e))
The complete implementation of deque using list in python is follows.
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Mon May 3 18:31:28 2021
@author: aditya1117
"""
class Deque:
def __init__(self):
self.dequeList=list()
self.dequeSize=0
def isEmpty(self):
if self.dequeSize==0:
return True
return False
def dequeLength(self):
return self.dequeSize
def insertAtFront(self,data):
self.dequeList.insert(0,data)
self.dequeSize=self.dequeSize+1
def insertAtRear(self,data):
self.dequeList.append(data)
self.dequeSize=self.dequeSize+1
def deleteFromFront(self):
try:
if self.dequeSize==0:
raise Exception("Deque is Empty")
else:
self.dequeList.pop(0)
self.dequeSize=self.dequeSize-1
except Exception as e:
print(str(e))
def deleteFromRear(self):
try:
if self.dequeSize==0:
raise Exception("Deque is Empty")
else:
self.dequeList.pop(-1)
self.dequeSize=self.dequeSize-1
except Exception as e:
print(str(e))
def front(self):
try:
if self.dequeSize==0:
raise Exception("Deque is Empty")
else:
return self.dequeList[0]
except Exception as e:
print(str(e))
def rear(self):
try:
if self.dequeSize==0:
raise Exception("Deque is Empty")
else:
return self.dequeList[-1]
except Exception as e:
print(str(e))
Conclusion
In this article, we have studied the concept behind deque and have implemented it using list in python. To gain more insight into it and understand how deque is different from inbuilt data structures like python dictionary, list and set , copy the full code given in the above example, paste it into your IDE and experiment with the deque operations. Stay tuned for more informative articles.