Deque, or Double Ended Queue, is a queue in which pieces can be added and removed from the front or back. As a result, it does not adhere to the FIFO principle (First In, First Out).
Python deques are helpful for storing collections of objects in memory. They’re also very fast because they use less space than linked lists. A deque is a doubly-linked list where each element is stored at both ends of the list. It means that when you remove elements from the middle of the list, they will move to the beginning and the end of the list.
The Python package “collections” is used to implement Deque (Double Ended Queue). When we need faster append and pop operations from both ends of the container, the deque is chosen over a list because the deque has an O(1) time complexity for append and pop operations. In contrast, the list has an O(n) time complexity.
The two kinds of Python Deques
- Deque with restricted Input – In this deque, input is limited at one end, while deletion is allowed at both ends.
- Deque with restricted Output – This deque restricts output to a single end while allowing insertion at both ends.
The following is a comparison of Deque and List
Deque is faster when the addition is used at the beginning and conclusion of the deque. Lists are faster when it comes to adding and removing elements from the middle of a list. Users in the list can insert lists using index and values, whereas, in the deque, we can append it on either the left or right side.
Queues and stacks are more like deques. They also include thread-safe support and are memory-efficient. Pops are the same on both sides of the deque, i.e., O(1) in either direction. List-objects support operations. Lists have been optimized to make operations go considerably faster.
A deque is a double-linked list with significantly more memory than a list. Instead of one pointer per node, it supports two. In general, this distinction can be overlooked. In Deque, users can append and pop up on both ends.
Here’s an example of importing deque in action. The code is a simple example used to import collections, and users can use it when they need to import a deque. The deque is imported into the collections, and the deque is declared in the next step. Finally, we print it to verify the value of our output.
<div class="wp-block-codemirror-blocks-code-block code-block"> <pre>from collections import deque d_queue = deque(['code','python','scored']) print(d_queue) </pre> </div>
Deque operations
In deque(), a variety of operations are carried out. In this section, we’ll show you how to perform all of the processes that will be valuable to you. We’ll start by looking at the various import options for importing the collection.
<div class="wp-block-codemirror-blocks-code-block code-block"> <pre>import collections</pre> </div>
Here’s another example of importing collections:
<div class="wp-block-codemirror-blocks-code-block code-block"> <pre>import collections compDeque = collections.deque(["Chrome Book","Lenovo","Toshiba","Apple"]) print (compDeque)</pre> </div>
Let’s look at several deque operations:
- append() is a function that adds the value in its argument to the right end of a deque.
- appendleft() inserts the value in its argument to the left end of the deque.
- pop() is a function that removes an argument from the deque’s right end.
- popleft() is a function that removes an argument from the deque’s left end.
- index(ele, beg, end): This method returns the first index of the value specified in parameters, starting at beg and continuing until the end index is found.
- insert(i, a): This function inserts the value from arguments(a) at the specified index(i) in arguments.
- remove(): This function eliminates the first instance of value in arguments.
- count() is a function that counts the number of times a value is specified in an argument.
- extend(iterable): This function adds multiple values to the deque at the right end. The passed argument is iterable.
- extendleft(iterable): Use this function to add several values to the deque’s left end. The passed argument is iterable. As a result of the left appends, the order is reversed.
- reverse(): Reverse the order of deque elements with this function.
- rotate(): This function rotates the deque by the number of arguments supplied. If the supplied integer is negative, the rotation will be to the left. Otherwise, the rotation will be to the right.
Appending a new value to the right
We’ll now utilize the following input value to append the value to the right side. On the right side of the queue, we’ll add IBM. On the right side of the list, the value is added.
<div class="wp-block-codemirror-blocks-code-block code-block">
<pre>print("Appending a new computer company to the right: ")
compDeque.append("IBM")
print (compDeque)</pre>
</div>
Append a new value to the left
We’ll use the following input value to append any value in deque to the left side. On the left side of the queue, we’ll add Microsoft. The value is added to the list on the left side.
<div class="wp-block-codemirror-blocks-code-block code-block">
<pre>print("Appending a new company to the left: ")
compDeque.appendleft("Microsoft")
print (compDeque)</pre>
</div>
Take away the value from the right
The value from the right side of the deque is removed by removing the deque. This option allows users to remove pertinent values from the deque on the right side. Use the lines of code below:
<div class="wp-block-codemirror-blocks-code-block code-block">
<pre>print("Taking away the value from the right: ")
compDeque.pop()
print(compDeque)</pre>
</div>
The value previously on the right side of the deque, in this case, IBM, will be deleted from the deque.
Removing the value from the left
Users must use the following lines of code to remove the value from the left side of the deque:
<div class="wp-block-codemirror-blocks-code-block code-block">
<pre>print("Removing the value present in the leftmost side of the deque ")
compDeque.popleft()
print(compDeque)</pre>
</div>
The value of Microsoft, which was previously on the deque’s left side, will be deleted from the deque.
Completely reversing the deque
Use the following code to reverse the entire deque:
<div class="wp-block-codemirror-blocks-code-block code-block">
<pre>print("Reversal of the computer companies deque in entirety: ")
compDeque.reverse()
print(compDeque)</pre>
</div>
Example: Implementation of a Deque in Python
<div class="wp-block-codemirror-blocks-code-block code-block">
<pre>class CodeDeque:
def __init__(self):
self.deque_items = []
def is_deque_empty(self):
return self.deque_items == []
def add_deque_rear(self, deque_item):
self.deque_items.append(deque_item)
def add_deque_front(self, deque_item):
self.deque_items.insert(0, deque_items)
def remove_deque_front(self):
return self.deque_items.pop(0)
def remove_deque_rear(self):
return self.deque_items.pop()
def deque_size(self):
return len(self.deque_items )
code_deque = CodeDeque()
print(code_deque.is_deque_empty())
code_deque.add_deque_rear(8)
code_deque.add_deque_rear(5)
code_deque.add_deque_front(7)
code_deque.add_deque_ront(10)
print(code_deque.deque_size())
print(code_deque.is_deque_empty())
code_deque.add_deque_rear(11)
print(code_deque.remove_deque_rear())
print(code_deque.remove_deque_front())
code_deque.add_deque_front(55)
code_deque.add_deque_rear(45)
print(code_deque.deque_items)
</pre>
</div>
Example: Demonstrating use of extend(), extendleft(), rotate(), reverse()
<div class="wp-block-codemirror-blocks-code-block code-block">
<pre># first, import "collections" for operations in the deque
import collections
# initializing numDeque
numDeque = collections.deque([31, 32, 33,])
# using extend() to append new numbers to right end
# adds 34,35,36 to right end
numDeque.extend([34,35,36])
# printing the modified numDeque
print ("The deque after extending deque at the end is: ")
print (numDeque)
# using extendleft() to add new numbers to left end of the numDeque
# adds 37,38,39 to left end
numDeque.extendleft([37,38,39])
# printing the modified numDeque
print ("The deque after extending deque at the beginning is: ")
print (numDeque)
# using rotate() to rotate the numDeque
# rotates by 4 to left
numDeque.rotate(-4)
# printing modified numDeque
print ("The deque after rotating deque is: ")
print (numDeque)
# using reverse() to reverse the numDeque
numDeque.reverse()
# printing modified numDeque
print ("The deque after")
print (numDeque)</pre>
</div>
Example: Illustrating the working of insert(), index(), remove(), count()
<div class="wp-block-codemirror-blocks-code-block code-block">
<pre># first, import "collections" for the given operations in the deque
import collections
# numDeque initialization
numDeque = collections.deque([31, 32, 33, 33, 34, 32, 34])
# using index() to print the first occurrence of 34
print ("The number 34 first occurs at a position : ")
print (numDeque.index(34,2,5))
# using insert() to insert the value 33 at 5th position
numDeque.insert(4,33)
# printing modified numDeque
print ("The numDeque after inserting 33 at 5th position is: ")
print (numDeque)
# using count() to count the occurrences of 33
print ("The count of 33 in numDeque is : ")
print (numDeque.count(33))
# using remove() to remove the first occurrence of 33 in numDeque
numDeque.remove(33)
# printing modified numDeque
print ("The numDeque after deleting the first occurrence of 33 is: ")
print (numDeque)
</pre>
</div>
Example: Demonstrating the working of append(), appendleft(), pop(), and popleft()
<div class="wp-block-codemirror-blocks-code-block code-block">
<pre># initially, import the "collections" for operations in the deque
import collections
# initialization of numDeque
numDeque= collections.deque([31,32,33])
# using append() to insert element at right end
# inserts 34 at the end of numDeque
numDeque.append(34)
# printing modified numDeque
print ("The numDeque after appending at right is: ")
print (numDeque)
# using appendleft() to insert the element at left end
# inserts 39 at the beginning of deque
numDeque.appendleft(39)
# printing modified deque
print ("The deque after appending at left is: ")
print (numDeque)
# using pop() to delete element from right end
# deletes 34 from the right end of deque
numDeque.pop()
# printing modified numDeque
print ("The numDeque after deleting from right is: ")
print (numDeque)
# using popleft() to delete element from left end
# deletes 39 from the left end of deque
numDeque.popleft()
# printing modified numDeque
print ("The deque after deleting from left is: ")
print (numDeque)</pre>
</div>
Conclusion
A deque is a double-ended queue that allows users to add elements from either end and remove elements from either end. This module is derived from the collections library and is used to implement it. When we require a faster technique to append operations, it is often preferred over the list. Both ends of the container are used to add and remove items. Users can add or remove values from both sides of the deque. They are even capable of reversing the entire deque.
For your convenience, the tutorial has covered all conceivable use scenarios with detailed examples.
