A Double-Ended Queue is a data structure that is used to store a collection of items that are meant to be in a queue. It is an extension of the queue data structure with some additional features.
Pre-Requisite: Queue
A queue is a data structure that is used to store a collection of items in the manner of a real-life queue. In a real queue, people usually enter from the back and exit from the front after they move through the queue. This is called a First-In-First-Out procedure.
A queue data structure is a similarly implemented list, in which all data is entered at the end of the list and all data is removed at the start of the list.
Recommended read – Doubly Circular Linked Lists in Python
Implementing a Double-Ended Queue in Python
In a double-ended queue, as the name suggests, data can be added and removed from the front as well as from the back, but data cannot be added or removed in the middle of the queue. Double-ended queues are also called deques.
We will now see its implementation in python. We will not be using the inbuilt collections
package, instead, we will implement it ourselves.
Class: Deque
class Deque:
def __init__(self):
self.queue = []
self.count = 0
def __repr__(self):
str = ""
if self.count == 0:
str += "Double Ended Queue Empty."
return str
str += "Double Ended Queue:\n" + self.queue.__repr__()
return str
def insert_start(self, data):
if self.count == 0:
self.queue = [data,]
self.count = 1
return
self.queue.insert(0, data)
self.count += 1
return
def insert_end(self, data):
if self.count == 0:
self.queue = [data,]
self.count = 1
return
self.queue.append(data)
self.count += 1
return
def remove_start(self):
if self.count == 0:
raise ValueError("Invalid Operation")
x = self.queue.pop(0)
self.count -= 1
return x
def remove_end(self):
if self.count == 0:
raise ValueError("Invalid Operation")
x = self.queue.pop()
self.count -= 1
return x
def get(self, index):
if index >= self.count | index < 0:
raise ValueError("Index out of range.")
return self.queue[index]
def size(self):
return self.count
def display(self):
print(self)
return
This is the code for a double-ended queue. There’s many methods, let us discuss them one by one.
1. The __init__
and __repr__
methods
In the __init__
method, we declare a list named queue
that will contain the deque, and a counter to count the number of items in the list.
In the __repr__
method, we create the string that will be used to print the double-ended queue.
2. The insert_start
and insert_end
methods
In the insert_start
method, we simply insert the new element at index 0
of the list queue
, and we increment the count of items in the list.
In the insert_end
method, we simply append the new item in the list queue
, and we increment the count of items in the list.
3. The remove_start
and remove_end
methods
In the remove_start
method, we check if the list is empty, and if so, then we raise a ValueError
. After that, we pop the item at index 0
, decrement the count
, and return the popped item.
In the remove_end
method too, we check if the list is empty, and if so, then we raise a ValueError
. After that, we pop the item at the end of the list, decrement the count
, and return the popped item.
4. The get
, size
, and display
methods
In the get
method, we return the item at a specified index. If the specified index is out of range, then we raise a ValueError
.
In the size
method, we simply return the count
that contains the number of items in the list.
And in the display
method, we print the deque.
The Output
Let us see the output of the code:

Conclusion
In this tutorial, we saw how to create a double ended queue, we implemented it in python, and we saw it’s output. Hope you had fun learning, and see you in the next tutorial.