The deque data structure is unique in comparison to other linear data structures. To begin, a deque stands for double-ended queue where we take the D, the E, and the first three letters of queue and put them all together to create this new word called deque. It is pronounced like Deck. It’s an abstract data type that resembles both a stack and a queue. Deques can hold a collection of items and order is semi preserved in a deque. In a deque, you can add items both to the front and to the back and you can remove items from the front and back as well. The deque can be implemented with a Python list, just like we have seen with the stack and queue. This goes to show just how flexible the list data type is in Python.
Deque Functions
Since it is possible to add and remove items on both sides of a deque, we need to use method names that specify which end of the deque the operation is happening on. So we’ll use add_front() and add_rear() as well as remove_front() and remove_rear() to make that distinction. Just like other containers we need to be able to see if the deque is empty or how many items are in it. When we are looking at a deque vs a queue, a queue uses a first-in-first-out or FIFO model and a stack uses a last-in-first-out or LIFO model. The deque class is interesting in that it can use either of those models or both of those models at the same time since you can add and remove items from both ends. Any data type that can be stored in a list can be stored in a deque. The deque is a limited access data structure because we can only access the data from either end.
A Deque Class And Its Methods
The following is a stubbed-out deque class. The class is defined with the name Deque and a list is used under the hood to represent the deque. Then we have the __init__ method which has an items variable initialized to an empty list. The following methods after this represent the basic functionality of the deque, which is adding items to it and removing items from it. With a deque, you can add to either side and remove from either side. This means we have to specify the location of the deque that we want to be adding or removing from. The add_front() method is passed in self and the item that we want to add to the deque. The add_rear() method is also passed in an item to add. Next are the removal methods. These are remove_front() and remove_rear(). You don’t need to specify which index to remove, because the list’s built-in pop method takes care of that for us. For peeking, we’ll need two methods of peek_front() and peek_rear(). The size() and is_empty() methods are pretty straightforward and basically the same as with stacks and queues. Because of its flexibility, the deque class has more methods than a stack or a queue class would and that’s because we need to always specify which end of the deque we’re working with.
class Deque:
def __init__(self):
self.items = []
def add_front(self, item):
pass
def add_rear(self, item):
pass
def remove_front(self):
pass
def remove_rear(self):
pass
def peek_front(self):
pass
def peek_rear(self):
passadd_front()
Takes an item as a parameter and inserts it into the 0th index of the list that is representing the Deque. The runtime is linear, or O(n), because every time you insert into the front of a list, all the other items in the list need to shift one position to the right.
class Deque:
def __init__(self):
self.items = []
def add_front(self, item):
self.items.insert(0, item)
def add_rear(self, item):
pass
def remove_front(self):
pass
def remove_rear(self):
pass
def peek_front(self):
pass
def peek_rear(self):
pass
def size(self):
pass
def is_empty(self):
passHere we test out the add_front method and add two items. Notice that when we add the Second Item, it appears to the left of the First Item. This is the expected behavior.
add_rear()
Takes in an item as a parameter and appends that item to the end of the list that is representing the Deque. The runtime is constant because appending to the end of a list happens in constant time.
class Deque:
def __init__(self):
self.items = []
def add_front(self, item):
self.items.insert(0, item)
def add_rear(self, item):
self.items.append(item)
def remove_front(self):
pass
def remove_rear(self):
pass
def peek_front(self):
pass
def peek_rear(self):
pass
def size(self):
pass
def is_empty(self):
passNow we can test out the add_rear() method. In the example below we add four items. We start by adding two items with the add_front() method and then add two additional items using the add_rear() method. When inspecting the items, we can see the order in which items were added to the deque.
remove_front()
Removes and returns the item in the 0th index of the list, which represents the front of the Deque. The runtime is linear, or O(n), because when we remove an item from the 0th index, all the other items have to shift one index to the left.
class Deque:
def __init__(self):
self.items = []
def add_front(self, item):
self.items.insert(0, item)
def add_rear(self, item):
self.items.append(item)
def remove_front(self):
if self.items:
return self.items.pop(0)
return None
def remove_rear(self):
pass
def peek_front(self):
pass
def peek_rear(self):
pass
def size(self):
pass
def is_empty(self):
passNow let’s test out the remove_front() method. When we call that method, the string ‘add front 2’ is removed. So we can see that when calling remove_front() it is removing items from the left of the deque.
remove_rear()
Removes and returns the last item of the list, which represents the rear of the Deque. The runtime is constant because all we’re doing is indexing to the end of a list.
class Deque:
def __init__(self):
self.items = []
def add_front(self, item):
self.items.insert(0, item)
def add_rear(self, item):
self.items.append(item)
def remove_front(self):
if self.items:
return self.items.pop(0)
return None
def remove_rear(self):
if self.items:
return self.items.pop()
return None
def peek_front(self):
pass
def peek_rear(self):
pass
def size(self):
pass
def is_empty(self):
passFor the remove_rear() method, we can see that it removes the right-most item from the deque.
peek_front()
Returns the value found at the 0th index of the list, which represents the front of the Deque. The runtime is constant because all we’re doing is indexing into a list.
class Deque:
def __init__(self):
self.items = []
def add_front(self, item):
self.items.insert(0, item)
def add_rear(self, item):
self.items.append(item)
def remove_front(self):
if self.items:
return self.items.pop(0)
return None
def remove_rear(self):
if self.items:
return self.items.pop()
return None
def peek_front(self):
if self.items:
return self.items[0]
return None
def peek_rear(self):
pass
def size(self):
pass
def is_empty(self):
passpeek_front() works like remove_front() but it is only looking at the item and not removing it.
peek_rear()
Returns the value found at the -1st, or last, index. The runtime is constant because all we’re doing is indexing into a list.
class Deque:
def __init__(self):
self.items = []
def add_front(self, item):
self.items.insert(0, item)
def add_rear(self, item):
self.items.append(item)
def remove_front(self):
if self.items:
return self.items.pop(0)
return None
def remove_rear(self):
if self.items:
return self.items.pop()
return None
def peek_front(self):
if self.items:
return self.items[0]
return None
def peek_rear(self):
if self.items:
return self.items[-1]
return None
def size(self):
pass
def is_empty(self):
passpeek_rear() works like remove_rear() but again any peek only displays the item, it does not remove it from the deque.
size()
Returns the length of the list, which is representing the Deque. The runtime will be constant because all we’re doing is finding the length of a list and returning that value.
class Deque:
def __init__(self):
self.items = []
def add_front(self, item):
self.items.insert(0, item)
def add_rear(self, item):
self.items.append(item)
def remove_front(self):
if self.items:
return self.items.pop(0)
return None
def remove_rear(self):
if self.items:
return self.items.pop()
return None
def peek_front(self):
if self.items:
return self.items[0]
return None
def peek_rear(self):
if self.items:
return self.items[-1]
return None
def size(self):
return len(self.items)
def is_empty(self):
passsize() works just like we would expect it to.
is_empty()
Checks to see if the list representing our Deque is empty. Returns True if it is, or False if it isn’t. The runtime is constant because all we’re doing is comparing two values.
class Deque:
def __init__(self):
self.items = []
def add_front(self, item):
self.items.insert(0, item)
def add_rear(self, item):
self.items.append(item)
def remove_front(self):
if self.items:
return self.items.pop(0)
return None
def remove_rear(self):
if self.items:
return self.items.pop()
return None
def peek_front(self):
if self.items:
return self.items[0]
return None
def peek_rear(self):
if self.items:
return self.items[-1]
return None
def size(self):
return len(self.items)
def is_empty(self):
return self.items == []is_empty() is correctly finding if the deque is empty or not.
Using A Deque To Check For Palindrome
The code below uses a new function check_palindrome(). It takes a parameter called input_str and that’s the string we want to check if it’s a palindrome. A deque object is used to store the characters of a string as it is iterated over. In the while loop, the front character is compared to the rear character while the size of the deque is greater than or equal to 2. If the front and rear do not match, it is not a palindrome. If they do match, it is a palindrome. We then test the function on three strings. Three of the strings are a palindrome and one is not.
class Deque:
def __init__(self):
self.items = []
def add_front(self, item):
self.items.insert(0, item)
def add_rear(self, item):
self.items.append(item)
def remove_front(self):
if self.items:
return self.items.pop(0)
return None
def remove_rear(self):
if self.items:
return self.items.pop()
return None
def peek_front(self):
if self.items:
return self.items[0]
return None
def peek_rear(self):
if self.items:
return self.items[-1]
return None
def size(self):
return len(self.items)
def is_empty(self):
return self.items == []
def check_palindrome(input_str):
deque = Deque()
for char in input_str:
deque.add_rear(char)
while deque.size() >= 2:
front_item = deque.remove_front()
rear_item = deque.remove_rear()
if front_item != rear_item:
return False
return True
print(check_palindrome('mom'))
print(check_palindrome('dad'))
print(check_palindrome('racecar'))
print(check_palindrome('slowcar'))True True True False
Python Deque Summary
In this tutorial, we learned about the Deque, or double ended queue data structure in Python. Deques are a generalization of stacks and queues and make it possible to work on both ends of the data structure. The code above is a manual implementation of a Deque, however, you may also want to check out the official python deque implementation which is a part of the collections module.
