Python’s “collections” module is used to implement the Deque (Doubly Ended Queue). When we need faster append and pop operations from both ends of the container, the deque is favored over lists because deque offers an O(1) time complexity for append and pop operations. In contrast, lists offer an O(n) time complexity.
A deque is a data structure that is a double-ended queue that allows users to add elements from either end and remove elements from either end. This module is used to implement this module, which is from the collections library. In situations where we require a quicker mechanism to perform append operations, it is often preferred over a list. Both container ends are used for insertions and removals. The values in the deque can be added or removed from both sides by the user. Even the entire deque can be reversed. For the benefit of the users, the tutorial will cover all potential use cases and include detailed examples. Deque, or a double-ended queue, is a queue in which elements can be added to or removed from it from either the front or the back. As a result, it disregards the FIFO rule (First In, First Out).
The most recent version of Python, Python x3.8, is the one we recommend using for implementation. It will produce comparable outcomes. However, if someone does not have the most recent version, they can still use an older version.
# code for demonstrating the deque from collections import deque # Declaration of the deque clubs_queue = deque(['Liverpool','Manchester','Chelsea']) print(clubs_queue)
The user can use Deque functionality thanks to Python. Deque, which stands for the double-ended queue, can be implemented in Python using a collection module. In essence, it is a component of the collection library; with deque, we perform append and pop operations, which allow us to add and delete elements from both ends. Each appending operation in a deque offers a 0(1) tie complexity and a 0(n) time complexity for each pop operation. Python employs its built-in techniques for deque implementation instead of requiring the use of any classes.
The syntax is as follows:
from collections import deque var_name=deque(['string1', 'string2', 'string3']) print(var_name)
In the syntax above, we implement the deque using a built-in method; however, we must first import the deque from the collection data structure. Then, using the syntax above, we define the list with the deque keywords. The list comprises the distinct strings string1, string2, and string3.
How does Deque operate in Python?
Let’s now have a look at how deque functions in Python.
Python’s collections module provides access to deque execution. A deque is a component with two ends and allows for both insertion and deletion of components. The latter is from either the left or right end of the queue. The deque is implemented as follows using the parameters listed below.
Deque types
- Restricted Deque Input -In this deque, input is limited at one end, while deletion is permitted at both ends.
- Restricted Deque Output -In this deque, the output is limited at one end, but insertion is permitted at both ends.
Check out some of the Operations on deque:
- append(): This function adds a value to the right end of the deque by inserting it there.
- appendleft() : The value in its argument is appended to the left end of the deque using the appendleft() function.
- pop() : Using the pop() function, an argument is removed from the deque’s right end.
- popleft(): Using the popleft() function, one can remove an argument from the deque’s left end.
- index(ele, beg, end): The function index(ele, beg, end) returns the first index of the value specified in the arguments, commencing the search from beg to end index.
- insert(i, a): The function insert(i, a) inserts the value indicated by argument(a) at the index(i) defined by argument(s).
- remove(): Removes the first instance of the value mentioned in arguments using the method remove().
- count(): counts the instances of each value stated in an argument.
- extend(iterable): Using the function extend(iterable), you can add more than one value to the right end of the deque. Iterable arguments were passed.
- extendleft(iterable): The function extendleft(iterable) expands the left end of the deque by adding numerous values. Iterable arguments were passed. Left appends cause the order to be flipped.
- reverse(): Reversing the order of deque elements is possible with the function reverse().
- rotate(): rotates the deque by the amount indicated in the parameters. If the provided integer is negative, the rotation is to the left. Rotation is to the right if not.
Activities of deque
In deque(), various operations are carried out. We shall demonstrate all conceivable procedures that the users will find beneficial in this part. We will first examine the collection import option that is offered. Below is another illustration of importing collections:
import collections double_ended_queue = collections.deque(["Jan,"Feb","Match"]) print (double_ended_queue)
Add value to the right
The following input value will be used to add the value to the right side. On the line’s right side, we will add Thursday. On the right side of the list, the value is added.
print("Month addition to the right: ") double_ended_queue.append("April") print (double_ended_queue)
The value is added to the list on the right side in the example above.
Place a value after the left
The following input value will be used to append any value in a deque to the left side. On the list’s left side, the value is inserted. On the line’s left side, we will add Sunday.
print("Appending to the left: ") double_ended_queue.append("Dec") print (double_ended_queue)
The value is added to the list on the left in this example.
Get rid of the right value
Users can remove the deque to remove the value from the deque’s right side. The appropriate values in the deque on the right side are removed by choosing this option. Use the code snippets below:
print("Taking away from the right: ") double_ended_queue.pop() print (double_ended_queue)
In this situation, the value that was previously on the right side of the deque—in our case, April—will be eliminated.
Delete the left value
Users must use the following lines of code to delete the value from the deque’s left side:
print("Value being removed from the left: ") double_ended_queue.popleft() print (double_ended_queue)
Here, Dec is replaced with the value originally on the deque’s left side.
Reversing the whole deque
Use the following code to reverse the entire deque:
print("The entire deque is reversed:. ") double_ended_queue.reverse() print (double_ended_queue)
Comparison between List and Deque
Listings are quicker when adding and removing items from the midst of the list. In a list, users can add items to lists using the index and values; in a deque, we can append it to either the left or the right side. The addition at the deque’s beginning and end make it faster.
Deques resemble queues and stacks more. They are memory-efficient and support thread-safeness. Pops from each side of the deque have the same value, or O(1). Lists have been streamlined for quick operations. Operating on the list of objects is supported.
A double link list called a deque has much more memory than a list. In place of one, it supports two pointers per node. In Deque, users can pop up and append on both ends. Overall, this distinction is disregarded.
Here is an example of importing a deque that is used. Users can choose this sample when they want to import a deque since it is a simple example of code that can be used to import collections. The collections import the deque, and in the following step, we declare the deque. To check the value of our output, we print it last.
from collections import deque language_queue = deque(['Python','JavaScript','Java']) print(language_queue)
Example: Code for demonstrating the working of append(), appendleft(), pop(), and popleft()
# importing "collections" for deque operations import collections # initialization of the deque new_deque = collections.deque([1,4,5]) # 9 is added to the end of the deque when an element is added at the right end using append(). new_deque.append(9) # modifying deque and printing print ("The phrase after the appending at right is: ") print (new_deque) # 3 is inserted at the start of the deque by using appendleft() to insert the element at the left end. new_deque.appendleft(3) # modifying deque and printing print ("The deque following adding at the left is: ") print (new_deque) # 9 are removed from the right end of the deque by using pop() to eliminate the element from the right end. new_deque.pop() # modifying deque and printing print ("The deque is to the right of the deletion: ") print (new_deque) # deleting element from left end using popleft() removes 3 from the left end of the deque new_deque.popleft() # modifying deque and printing print ("After deleting from the left, the queue is: ") print (new_deque)
Example: Code demonstrating the working of insert(), index(), remove(), count()
# importing "collections" responsible for the operations in the deque import collections # initialization of the deque new_deque = collections.deque([1, 2, 3,2, 3, 4, 2, 4]) # printing the first occurrence of 2 using index() print ("The spot where the number 2 first appears is: ") print (new_deque.index(4,2,5)) # insert() is used to place the number 9 in the fifth slot. new_deque.insert(4,9) # modifying deque and printing print ("After placing 9 in the fifth place, the deque is: ") print (new_deque) # counting the occurrences of 9 using count() print ("The number nine in a deque is : ") print (new_deque .count(9)) # removing the first occurrence of 4 with remove() new_deque.remove(4) # generating the updated deque print (" After removing the first instance of 4, the deque is: ") print (new_deque)
Example: Code to demonstrate working of extend(), extendleft(), rotate(), reverse()
# for deque operations, import "collections." import collections # initialization of the deque new_deque = collections.deque([1, 2, 3,]) # When adding numbers to the right end using extend(), the results are 4,5,6. new_deque.extend([4,5,6]) # modifying deque and printing print ("The deque is extended towards the end and is: ") print (new_deque) # When adding integers to the left end with extendleft(), 7,8,9 are added. new_deque.extendleft([7,8,9]) # modifying deque and printing print ("the deque following the initial extension of the deque is: ") print (new_deque) # The deque rotates by 3 to the left when rotate() is used. new_deque.rotate(-3) # modifying deque and printing print ("Following the revolving deque is the deque: ") print (new_deque) # reversing the deque using reverse() new_deque.reverse() # modifying deque and printing print ("The resultant deque after reversing is: ") print (new_deque)
Example: Deque Manipulation in Python
import collections # Create a deque double_ended_queue = collections.deque(["Jan","Feb","Match"]) print (double_ended_queue) # Appending on the right print("Adding to the right: ") double_ended_queue.append("April") print (double_ended_queue) # add on the left print("To the left, add: ") double_ended_queue.appendleft("Dec") print (double_ended_queue) #Get rid of from the right print("Taking away from the right:") double_ended_queue.pop() print (double_ended_queue) # From the left, remove print("Taking away from the left: ") double_ended_queue.popleft() print (double_ended_queue) # the dequeue in reverse print("The deque is reversed:") double_ended_queue.reverse() print (double_ended_queue)
Example: Deque implementation in python
class code_deque: def __init__(self): self.items = [] def is_empty(self): return self.items == [] def add_rear(self, item): self.items.append(item) def add_front(self, item): self.items.insert(0, item) def remove_front(self): return self.items.pop(0) def remove_rear(self): return self.items.pop() def size(self): return len(self.items) new_deque = Deque() print(new_deque.is_empty()) new_deque.add_rear(8) new_deque.add_rear(5) new_deque.add_front(7) new_deque.add_front(10) print(new_deque.size()) print(new_deque.is_empty()) new_deque.add_rear(11) print(new_deque.remove_rear()) print(new_deque.remove_front()) new_deque.add_front(55) new_deque.add_rear(45) print(new_deque.items)
Conclusion
A double-ended queue, also known as a deque, allows users to add and remove items from either end. A component of the collections library is the Deque module. It provides methods used directly with arguments for adding and removing items. We use the built-in implement these methods without the requirement for any class. Further, we import the collections module and define a deque in the sample programs used.