Online Tutorials & Training Materials | STechies.com
Register Login
Advertisement

Deque in Python

|| 0

Deque in Python
Stechies

What is Deque?

A deque is a double-ended queue that has the functionality of adding and deleting elements from both ends. In python, deque can be implemented using the Deque module that is within the collections library. The methods for addition and deletion of nodes can be invoked using arguments. A deque is considered better than simple Python lists when the elements need to be added and removed quickly.

For these operations, deque has O(1) time complexity where lists have O(n) complexity. It has a number of important operations like append(), pop(), appendleft(), popleft(), index(i,a), index(ele, beg,end), count(), remove(), extendleft(iterable), extend(iterable), rotate(), reverse().

As deque assume many of the characteristics of stacks and queues but it does not require LIFO and FIFO ordering, as adding and removing of data element can be done from front and rear end.

Deque Operations:

  1. append() : function is used to insert value argument to the right end of deque.
  2. appendleft() : function append on left in list of deque.
  3. pop() : function is used to delete a value from the right side of deque.
  4. popleft() : function is used to delete an argument from the left of deque.
  5. index(ele, beg, end) : function returns the first index of the value mentioned in arguments list, starting elements from beg till end of index.
  6. insert(i, a) : This function inserts the value at a defined position as mentioned in the  arguments list.
  7. remove() : function removes the first occurrence (in case of duplicate otherwise first one) of value mentioned in arguments.
  8. count() : function counts the number of occurrences of value mentioned in arguments.
  9. extend(iterable) : Is used to add multiple values at the right end of deque. The argument passed is iterable.
  10. extendleft(iterable) : Is used to add multiple values at the left end of the deque. The argument passed is iterable. Order is reversed as a result of left appends.
  11. reverse() : is used to reverse order of deque elements.
  12. rotate() : It rotates the deque by the number specified in arguments. If the number specified is negative, rotation occurs to left. Else rotation is to right.

Example program to show deque along with all operations implementation.

# demonstrate working of
# append(), appendleft(), pop(), and popleft()
# importing "collections" for deque operations
import collections
# initializing deque
deqe = collections.deque([1,2,3])
# using append() to insert 4 element at right end
deqe.append(5)
# print modified deque
print ("The deque after appending at right is : ")
print (deqe)
# using appendleft() to insert element at right end
# inserts 4 at the beginning of deque
deqe.appendleft(4)
# Disply modified deque
print ("The deque after appending at left is : ")
print (deqe)
# using pop() to delete element from right end
# deletes 4 from the right end of deque
deqe.pop()
# print modified deque
print ("The deque after deleting from right is : ")
print (deqe)
# using popleft() to delete element from left end
# deletes 5 from the left end of deque
deqe.popleft()
# print modified deque
print ("The deque after deleting from left is : ")
print (deqe)

Output of Program

$python main.py
The deque after appending at right is :
deque([1, 2, 3, 5])
The deque after appending at left is :
deque([4, 1, 2, 3, 5])
The deque after deleting from right is :
deque([4, 1, 2, 3])
The deque after deleting from left is :
deque([1, 2, 3])

Example 2

# to demonstrate working of
# extend(), extendleft(), rotate(), reverse()
# importing "collections" for deque operations
import collections
# initializing deque
deqe = collections.deque([1, 2, 3,])
# using extend() to add numbers to right end
# adds 4,5,6 to right end
deqe.extend([5,6,7])
# print modified deque
print ("The deque after extending deque at end is : ")
print (deqe)
# using extendleft() to add numbers to left end
# adds 7,8,9 to right end
deqe.extendleft([7,8,9])
# print modified deque
print ("The deque after extending deque at beginning is : ")
print (deqe)
# using rotate() to rotate the deque
# rotates by 3 to left
deqe.rotate(-3)
# printing modified deque
print ("The deque after rotating deque is : ")
print (deqe)
# using reverse() to reverse the deque
deqe.reverse()
# printing modified deque
print ("The deque after reversing deque is : ")
print (deqe)


Output

$python main.py
The deque after extending deque at end is :
deque([1, 2, 3, 5, 6, 7])
The deque after extending deque at beginning is :
deque([9, 8, 7, 1, 2, 3, 5, 6, 7])
The deque after rotating deque is :
deque([1, 2, 3, 5, 6, 7, 9, 8, 7])
The deque after reversing deque is :
deque([7, 8, 9, 7, 6, 5, 3, 2, 1])

 


Advertisement
Advertisement
Advertisement