Python collections deque

from collections import deque

#create a deque from an iterable
d = deque([1, 2, 3, 4, 5])

print(d)

#add element at the left end
d.appendleft(0)
print(d)

#add element at the right end
d.append(6)

print(d)

A queue is a data structure that follows a First-In-First-Out (FIFO) ordering for inserting and removing elements. A deque is a type of queue that also follows a Last-In-First-Out (LIFO) ordering for insertions and retrievals. The name "deque", pronounced as  "deck",  is short for "double-ended queue" and reflects the fact that elements can be added or removed from either end of the structure.

The collections module in the standard library implements the deque data structure. The implementation provides O(1) time complexity for appending and popping from both ends of the deque.

Instantiate deque objects

The most straightforward way to instantiate a deque object is to create an empty deque. To do so, you will need to import the collections module and use the deque constructor without any argument.

from collections import deque 

queue = deque()

print(queue)

Another way to instantiate a deque is with an iterable object. This could be any type of sequence or collection such as a list, set,  tuple, range, etc. The deque constructor takes the iterable as an argument and creates a deque from the elements.   

from collections import deque 

# creating deque from list 
queue1 = deque(['Mon', 'Tue', 'Wed']) 

#Creating deque from tuple 
queue2 = deque(('Thur', 'Fri', 'Sat')) 

# Creating deque from range
queue3 = deque(range(10))

print(queue1)
print(queue2)
print(queue3)

Populate the deque

Populating the deque refers to adding elements to the deque at any of its ends after it has been created. This is accomplished using various methods  defined by the deque class.

Inserting single element to the deque

Single insertions are achieved primarily using two methods i.e append() and appendleft() methods. The append() method adds a single item to the right/back end of the deque.

append(item)

from collections import deque

d = deque()

d.append(0)
d.append(1)
d.append(2)
d.append(3)
d.append(4)
d.append(5)

print(d)

The appendleft() method adds a single item to the left/front end of the deque.

appendleft(item)

from collections import deque

d = deque()

d.appendleft(0)
d.appendleft(1)
d.appendleft(2)
d.appendleft(3)
d.appendleft(4)
d.appendleft(5)

print(d)

Insert multiple elements at once

The deque also supports multiple element insertion through the extend() and extendleft() methods. The two methods takes in an iterable containing the elements to be inserted and inserts the at the respective ends. The extend() method inserts all the elements of the iterable at the right/back end of the deque, while the extendleft() method inserts all the elements of the iterable at the left/front end of the deque.

from collections import deque

d = deque([1, 2, 3, 4, 5])
print('before: ', d)

items = (6, 7, 8, 9)

#use the extend method
d.extend(items)

print('after: ', d)

from collections import deque

d = deque([6, 7, 8, 9])
print('before: ', d)

items = (5, 4, 3, 2, 1, 0)

#use the extend method
d.extendleft(items)

print('after: ', d)

Retrieve items from the deque

deque objects similarly contain methods for retrieving items from either ends. This is achieved primarily through the pop() and the popleft() methods. The pop() method is used to retrieve an item from the right side of the deque, while the popleft() method is used to retrieve an item from the left side of the deque. Both methods remove the item from the deque  after it has been retrieved. If the deque is empty, both methods will raise an IndexError exception.

from collections import deque

d = deque(range(10))
print('before: ', d)

try: 

    #consume elements from right side
    print('from right: ')
    print(d.pop(), end = ' ')
    print(d.pop(), end = ' ')
    print(d.pop(), end = ' ')
    print(d.pop(), end = '\n')

    #consume elements from left
    print('from left: ')
    print(d.popleft(), end = ' ')
    print(d.popleft(), end = ' ')
    print(d.popleft(), end = ' ')
    print(d.popleft(), end = '\n')

except IndexError as e:
    print('done')

print('after: ', d)

Remember that an IndexError will be raised if the deque is empty, you should therefore either handle the exception in advance or ensure  that the deque is not empty before attempting to retrieve elements.

deques and thread safety

deque objects are thread-safe which means that multiple threads can simultaneously read and write from a deque object without any corruption of its items. Thread safety ensures that simultaneous threads can access a shared data structure( or code) without affecting the integrity of the data. 

Rotating deque elements

Rotating the deque means taking elements from the front of the deque to the back and vice verse. We us the rotate() method to perform the rotation. With a negative integer as the argument,  it rotates the deque to the right meaning that elements are taken from back to front. With a positive integer as the argument, it rotates the deque to the left.

from collections import deque

d = deque(range(10))

print('before: ', d)
d.rotate(-5)

print('after: ', d)

from collections import deque

d = deque(range(10))

print('before: ', d)
d.rotate(5)

print('after: ', d)

Deque methods

The methods of deque objects can be summarized as:

from collections import deque

d = deque(range(10))

print('before: ', d)
d.reverse()

print('after: ', d)