Deque in Python




Deque (Doubly Ended Queue) in Python is implemented using the module “collections“.
Deque is preferred over a list in the cases where we need quicker append and pop operations
from both the ends of the container, as deque provides an O(1) time complexity for append and
pop operations as compared to a list that provides O(n) time complexity.

Types of Restricted Deque Input

 Input Restricted Deque: Input is limited at one end while deletion is permitted at both
ends.
 Output Restricted Deque: output is limited at one end but insertion is permitted at both
ends.
Example: Python code to demonstrate deque
 Python3

from collections import deque

# Declaring deque

queue = deque(['name','age','DOB'])

print(queue)

Output
deque(['name', 'age', 'DOB'])
 Operations on deque
Example 1: Appending Items Efficiently
 append():- This function is used to insert the value in its argument to the right end of the
deque.
 appendleft():- This function is used to insert the value in its argument to the left end of the
deque.
 Python3

# importing "collections" for deque operations

import collections

# initializing deque

de = collections.deque([1, 2, 3])

print("deque: ", de)

# using append() to insert element at right end

# inserts 4 at the end of deque

de.append(4)

# printing modified deque

print("\nThe deque after appending at right is : ")

print(de)

# using appendleft() to insert element at left end

# inserts 6 at the beginning of deque

de.appendleft(6)

# printing modified deque

print("\nThe deque after appending at left is : ")

print(de)
 Output
deque: deque([1, 2, 3])

The deque after appending at right is :

deque([1, 2, 3, 4])

The deque after appending at left is :

deque([6, 1, 2, 3, 4])

Example 2: Popping Items Efficiently

 pop():- This function is used to delete an argument from the right end of the deque.
 popleft():- This function is used to delete an argument from the left end of the deque.
 Python3

# importing "collections" for deque operations

import collections

# initializing deque

de = collections.deque([6, 1, 2, 3, 4])

print("deque: ", de)

# using pop() to delete element from right end

# deletes 4 from the right end of deque

de.pop()

# printing modified deque

print("\nThe deque after deleting from right is : ")

print(de)

# using popleft() to delete element from left end

 # deletes 6 from the left end of deque

de.popleft()

# printing modified deque

print("\nThe deque after deleting from left is : ")

print(de)

Output
deque: deque([6, 1, 2, 3, 4])

The deque after deleting from right is :

deque([6, 1, 2, 3])

The deque after deleting from left is :

deque([1, 2, 3])

Example 3: Accessing Items in a deque

 index(ele, beg, end):- This function returns the first index of the value mentioned in
arguments, starting searching from beg till end index.
 insert(i, a) :- This function inserts the value mentioned in arguments(a) at index(i) specified
in arguments.
 remove():- This function removes the first occurrence of the value mentioned in arguments.
 count():- This function counts the number of occurrences of value mentioned in arguments.
 Python3

# Python code to demonstrate working of

# insert(), index(), remove(), count()

# importing "collections" for deque operations

import collections
 # initializing deque

de = collections.deque([1, 2, 3, 3, 4, 2, 4])

# using index() to print the first occurrence of 4

print ("The number 4 first occurs at a position : ")

print (de.index(4,2,5))

# using insert() to insert the value 3 at 5th position

de.insert(4,3)

# printing modified deque

print ("The deque after inserting 3 at 5th position is : ")

print (de)

# using count() to count the occurrences of 3

print ("The count of 3 in deque is : ")

print (de.count(3))

# using remove() to remove the first occurrence of 3

de.remove(3)

# printing modified deque

print ("The deque after deleting first occurrence of 3 is : ")

print (de)

Output
The number 4 first occurs at a position :
4
The deque after inserting 3 at 5th position is :
deque([1, 2, 3, 3, 3, 4, 2, 4])
The count of 3 in deque is :
 3
The deque after deleting first occurrence of 3 is :
deque([1, 2, 3, 3, 4, 2, 4])

Example 4: Size of a deque

 len(dequeue):- Return the current size of the dequeue.

 Python3

# Python Program to demonstrate

# how to find size of a Dequeue

from collections import deque

# initializing deque

de = deque([1, 2, 3, 4, 5, 6])

print("Current Deque: ", de)

# printing current size of deque

print(f"Size of Deque: {len(de)}")

# using pop() to delete element from right end

# deletes 6 from the right end of deque

de.pop()

# printing modified deque

print("\nThe deque after deleting from right is: ", end = '')

print(de)

# printing current size of deque

print(f"Size of Deque: {len(de)}")

Output
 Current Deque: deque([1, 2, 3, 4, 5, 6])
Size of Deque: 6

The deque after deleting from right is: deque([1, 2, 3, 4, 5])

Size of Deque: 5

Example 5: Front and Back of a deque

 Deque[0] :- We can access the front element of the deque using indexing with de[0].
 Deque[-1] :- We can access the back element of the deque using indexing with de[-1].
 Python3

# Python Program to demonstrate

# accessing the front and back of a Deque

from collections import deque

# initializing deque

de = deque([1, 2, 3, 4, 5, 6])

print("Current Deque: ", de)

# Accessing the front element of the deque

print("Front element of the deque:", de[0])

# Accessing the back element of the deque

print("Back element of the deque:", de[-1])

Output
Current Deque: deque([1, 2, 3, 4, 5, 6])
Front element of the deque: 1
Back element of the deque: 6

Example 6: Different operations on deque

  extend(iterable):- This function is used to add multiple values at the right end of the deque.
The argument passed is iterable.
 extendleft(iterable):- This function 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.
 reverse():- This function is used to reverse the order of deque elements.
 rotate():- This function rotates the deque by the number specified in arguments. If the
number specified is negative, rotation occurs to the left. Else rotation is to right.
 Python3

# Python code to demonstrate working of

# extend(), extendleft(), rotate(), reverse()

# importing "collections" for deque operations

import collections

# initializing deque

de = collections.deque([1, 2, 3,])

# using extend() to add numbers to right end

# adds 4,5,6 to right end

de.extend([4,5,6])

# printing modified deque

print ("The deque after extending deque at end is : ")

print (de)

# using extendleft() to add numbers to left end

# adds 7,8,9 to left end

de.extendleft([7,8,9])

# printing modified deque

print ("The deque after extending deque at beginning is : ")

 print (de)

# using rotate() to rotate the deque

# rotates by 3 to left

de.rotate(-3)

# printing modified deque

print ("The deque after rotating deque is : ")

print (de)

# using reverse() to reverse the deque

de.reverse()

# printing modified deque

print ("The deque after reversing deque is : ")

print (de)

Output
The deque after extending deque at end is :
deque([1, 2, 3, 4, 5, 6])
The deque after extending deque at beginning is :
deque([9, 8, 7, 1, 2, 3, 4, 5, 6])
The deque after rotating deque is :
deque([1, 2, 3, 4, 5, 6, 9, 8, 7])
The deque after reversing deque is :
deque([7, 8, 9, 6, 5, 4, 3, 2, 1])