Do you think IIT Guwahati certified course can help you in your career?
No
Introduction
In Python programming, efficient data handling and manipulation are key to building optimized applications. One versatile data structure that often goes overlooked is the deque, which stands for "double-ended queue." Available in Python's collections module, a deque provides a more flexible alternative to traditional lists by allowing quick addition and removal of elements from both ends. This feature makes deque an ideal choice for tasks that require frequent access to both the front and back of a sequence, such as implementing stacks, queues, and other complex data structures.
In this article, we will discuss an important Data Structure called a Deque. We are also going to the implementation of Deque() in Python.
What is Deque in Python?
A Deque can be called a special case of Queue. It is also called a Double ended Queue. In a Deque data structure, elements can be added from both ends of the list. With that, the elements can also be removed from both ends.
Adding elements to a Deque() in Python is like adding elements to a list either at the beginning or end. Same with removing the elements from a deque. Both the addition and removal operations take constant time, making the time complexity O(1).
Let us take a look at the implementation of deque in python.
Deque() in python can be implemented like a Queue in Python using a list.
Following is the implementation of Deque() in python using a list
A deque is a data structure that allows you to insert and remove elements from both ends. But in a restricted deque input, there are some limitations on the type of operations that you can do.
There are two types of restricted deque input:
Input-restricted deque: In this type of deque, you can only add elements to one end (the back end). But you can remove elements from both ends. It's like a queue where you can only add to the back of the line, but anyone can leave from the front or the back.
Output-restricted deque: In this type of deque, you can only remove elements from one end (the front end). But you can add elements to both ends. It's like a stack where you can only take things off the top, but you can add things to the top or the bottom.
Both input and output-restricted deques have their own specific uses, depending on what you need to do with the data.
Operations on Python deque()
Operation
Description
createDeque()
Creates a new, empty deque.
addFront(item)
Adds the specified item to the front of the deque.
addRear(item)
Adds the specified item to the rear of the deque.
removeFront()
Removes and returns the item at the front of the deque.
removeRear()
Removes and returns the item at the rear of the deque.
peekFront()
Returns the item at the front of the deque without removing it.
peekRear()
Returns the item at the rear of the deque without removing it.
isEmpty()
Returns True if the deque is empty. False otherwise.
The Queue is:
[3, 1, 2]
The element popped from the queue is
3
Updated Queue
[1, 2]
The element popped from the queue is
1
Updated Queue
[2]
Python also has an inbuilt module, which helps implement deque in python. Thus, it must be imported from the python collections to utilize that module. The module is called deque. The implementation of deque in python from collections can be done as follows:
Deque In Python Using Collections
Let us look at some of the functions obtained for deque() in python from collections:
Now let us take a look at it's implementation:
Python
Python
# Implementation of deque() in python from collections
from collections import deque
original_queue = [] n = int(input("Enter the Number of Elements in the Queue: ")) print("Enter the Numbers: ")
for i in range(n): temp = int(input()) original_queue.append(temp) dq = deque(original_queue)
# Insert element at the left of the deque dq.appendleft(1) dq.appendleft(2)
# Insert elements at the right of the deque dq.append(3) dq.append(4)
print("The data in the Deque is as follows:") print(dq)
# Removing data from the left print("Popped Element from the Left:") print(dq.popleft()) print("Updated Deque") print(dq)
# Removing data from the right print("popped Element from the Right:") print(dq.pop()) print("Updated Deque") print(dq)
You can also try this code with Online Python Compiler
Enter the Number of Elements in the Queue: 5
Enter the Numbers:
11
13
12
15
16
The data in the Deque is as follows:
deque([2, 1, 11, 13, 12, 15, 16, 3, 4])
Popped Element from the Left:
2
Updated Deque
deque([1, 11, 13, 12, 15, 16, 3, 4])
Popped Element from the Right:
4
Updated Deque
deque([1, 11, 13, 12, 15, 16, 3])
Apart from the major functions of enqueuing and dequeuing elements, deque() in python offers some extra functionality as well, such as:
Function
Description
index(element, begin, end)
This function returns the index of the element’s first occurrence between the begin and the end index.
insert(element, i)
This function is utilized to insert an element at an index ‘i’ in the deque.
remove(element)
This function removes the first occurrence of the element specified in its parameters.
count(element)
This counts the number of occurrences of the element provided as its parameter.
extend(iterable_elemet)
This function is used to insert multiple elements to the right at once provided to it as a parameter.
extendleft(iterable_elemet)
This function is used to insert multiple elements to the left at once provided to it as a parameter.
reverse()
This function is used to reverse the element’s order in the deque.
rotate(value)
This function is used to rotate the elements of the deque. If the value provided in the parameters is positive, the rotation occurs to the right; else, the rotation occurs to the left.
Let us take a look at the implementation of the above-mentioned functions:
Additional Features For Deque In Python Using Collections
Python
Python
# Implementation of deque() in python from collections
from collections import deque
dq = deque([1,2,3,3,3,4,5,5,6,7])
print("The Deque is:") print(dq) print("\n")
# Insert element at the left of the deque dq.appendleft(1) dq.appendleft(2)
# Insert elements at the right of the deque dq.append(3) dq.append(4)
print("The data in the Deque is as follows:") print(dq) print("\n")
# Removing data from the left print("Popped Element from the Left:") print(dq.popleft()) print("Updated Deque") print(dq) print("\n")
# Removing data from the right print("popped Element from the Right:") print(dq.pop()) print("Updated Deque") print(dq) print("\n")
print("The first occurrence of element at 3 between the index 1 and 6 is at:") print(dq.index(3,1,6)) print("\n")
print("Inserting 10 at index 2:") dq.insert(2,10) print("Updated Deque:") print(dq) print("\n")
print("Removing first occurrence of 5") dq.remove(5) print("Updated Deque:") print(dq) print("\n")
print("The Number of occurrences of the element 3 are: ") print(dq.count(3)) print("\n")
print("Adding the list [0,-1,-2] to the right of the deque") dq.extend([0,-1,-2]) print("Updated Deque") print(dq) print("\n")
print("Adding the list [10,11,12] to the left of the deque") dq.extendleft([10,11,12]) print("Updated Deque") print(dq) print("\n")
print("Reversing the Deque") dq.reverse() print("Updated Deque") print(dq) print("\n")
print("Rotating the Deque to the left by 3") dq.rotate(3) print("Updated Deque") print(dq) print("\n")
You can also try this code with Online Python Compiler
The Deque is:
deque([1, 2, 3, 3, 3, 4, 5, 5, 6, 7])
The data in the Deque is as follows:
deque([2, 1, 1, 2, 3, 3, 3, 4, 5, 5, 6, 7, 3, 4])
Popped Element from the Left:
2
Updated Deque
deque([1, 1, 2, 3, 3, 3, 4, 5, 5, 6, 7, 3, 4])
popped Element from the Right:
4
Updated Deque
deque([1, 1, 2, 3, 3, 3, 4, 5, 5, 6, 7, 3])
The first occurrence of element at 3 between the index 1 and 6 is at:
3
Inserting 10 at index 2:
Updated Deque:
deque([1, 1, 10, 2, 3, 3, 3, 4, 5, 5, 6, 7, 3])
Removing first occurrence of 5
Updated Deque:
deque([1, 1, 10, 2, 3, 3, 3, 4, 5, 6, 7, 3])
The Number of occurrences of the element 3 are:
4
Adding the list [0,-1,-2] to the right of the deque
Updated Deque
deque([1, 1, 10, 2, 3, 3, 3, 4, 5, 6, 7, 3, 0, -1, -2])
Adding the list [10,11,12] to the left of the deque
Updated Deque
deque([12, 11, 10, 1, 1, 10, 2, 3, 3, 3, 4, 5, 6, 7, 3, 0, -1, -2])
Reversing the Deque
Updated Deque
deque([-2, -1, 0, 3, 7, 6, 5, 4, 3, 3, 3, 2, 10, 1, 1, 10, 11, 12])
Rotating the Deque to the left by 3
Updated Deque
deque([10, 11, 12, -2, -1, 0, 3, 7, 6, 5, 4, 3, 3, 3, 2, 10, 1, 1])
Building Efficient Queues With deque() in Python
We will understand this concept with a short example:
from collections import deque
queue = deque()
queue.append('apple')
queue.popleft()
This creates an empty queue using deque(), adds an element 'apple' to the queue using append(), and removes the first element from the queue using popleft(). The append() and popleft() methods have O(1) time complexity, making deque an efficient choice for implementing queues.
Deque is implemented as a doubly-linked list in Python. Each element in the deque holds a reference to the preceding and following items, allowing for constant time operations to add or remove elements from both ends of the deque.
Is deque better than queue in Python?
Yes, deque is often better than queue in Python for many tasks because it allows fast appends and pops from both ends. This makes deque versatile and faster for managing sequences, unlike queue, which is typically limited to FIFO operations.
Why is deque faster than list in Python?
deque is faster than a list for insertions and deletions at both ends due to its doubly-linked list structure. Unlike lists, which require shifting elements when modified at the start, deque can quickly access and adjust either end.
What is the difference between stack and deque?
A stack is a data structure with LIFO (last-in, first-out) behavior, typically allowing operations only at one end. In contrast, a deque supports fast insertions and deletions at both ends, making it suitable for both stack and queue operations.
Conclusion
In this article, we discussed Deque() in Python. The deque in Python is a powerful and flexible data structure that offers efficient appends and pops from both ends, making it ideal for a variety of use cases like implementing stacks, queues, and double-ended queues. With its optimized performance for front and back operations, deque is a go-to choice for scenarios requiring quick data manipulation at both ends of a sequence.