Double-ended Queue in Python

A double-ended queue is a type of queue in which elements can be added and removed from both ends of the queue. This allows for flexibility in quickly inserting and removing elements from either the front or the back. It is more versatile than a regular queue, where elements are strictly added at one end and removed from the other.

A double-ended queue is usually shortened as "deque", pronounced as "deck" to avoid confusion with "dequeue",  a queue operation (which is pronounced as "dee-kew")

The Deque abstract data type

An abstract data type is a higher-level, language-agnostic description of a data structure.  In this section we will look at the operations that an implementation of a deque should support without being concerned with how those operations are actually implemented.

A deque data structure supports the following operations:

The collections.deque class

The collections module in the standard library provides an efficient implementation of a double ended queue through the deque class. We only need to import the class in our program to use it.

from collections import deque
print(deque)

The deque class implements the following basic methods:

Add elements to a deque

To populate a deque we use append() and  appendleft() methods. append() adds a single element at the back, while appendleft() adds a single element at the front.

#import the deque class
from collections import deque

d = deque()

#add at the back
d.append(10)
d.append(20)
d.append(30)

#add at the front
d.appendleft(100)
d.appendleft(200)
d.appendleft(300)

#display the deque
print(d)

Remove elements  

To consume deque elements, we use pop() and popleft() methods; pop() removes an item from the back, while popleft() removes an element from the front.

#import deque class
from collections import deque

d = deque() 

#add elements 
d.append(10)
d.append(20)
d.append(30)
d.appendleft(100)
d.appendleft(200)
d.appendleft(300)

#display the deque
print(d)

#remove elements
print("pop: ", d.pop())
print("popleft: ", d.popleft())
print("pop: ", d.pop())
print("popleft: ", d.popleft())
print("pop: ", d.pop())
print("popleft: ", d.popleft())

print("\nAfter: ", d)

Other deque operations 

Apart from basic methods for insertion and deletion methods that we have looked at, the deque class supports more operations. Most of the operations are similar to those of the built-in list data type. 

In this part, we will look at the various operations.

Check the number of elements in the deque

We can use the builtin len() method to get the size of a deque.

from collections import deque

d = deque()

d.append("Python")
d.append("Javascript")
d.appendleft("Ruby")
d.append("C++")

print(d)
#get the size
print("Size: ", len(d))

print("pop: ", d.pop())
print("popleft: ", d.popleft())

print(d)
print("Size: ", len(d))

Extend the deque with an iterable

The extend() and the extendleft() methods can be used to extend a deque with elements from an iterable object such as list, tuple, etc. This allows us to add multiple elements at once at either the front or the back of the deque. extend() adds the elements at the back, while extendleft() adds the elements at the front.

from collections import deque

iterable1 = ["three", "two", "one"]
iterable2 = ["eight", "nine", "ten"]

d = deque()

d.extendleft(iterable1)
d.extend(iterable2)

print(d)

Insert an element at an arbitrary position in the deque.

The insert() method inserts an item at the specified position. It has the following syntax:

insert(i, e)

It inserts element e at position i. If the given position is larger than the index of the last element, the incoming element will be inserted as the last element, and if the index is smaller than the negative index of the first element, the element will be inserted as the first element.

from collections import deque

d = deque()
d.appendleft("one")
d.append("three")

#insert an element
d.insert(1, "two")
print(d)

#use a larger index
d.insert(20, "four")
#use a smaller index
d.insert(-10, "zero")

#display d
print(d) 

Count element occurrence

The count() method returns the number of times that an element occurs.

from collections import deque

d = deque()

d.append(10)
d.append(20)
d.append(10)
d.append(10)

print(d.count(10))

Reverse the deque

To reverse the elements in a deque in-place, we can use the reverse() methods. 

from collections import deque

d = deque()

d.append("Python")
d.append("Ruby")
d.append("HTMl")
d.append("PHP")

print("Before: ", d)

#reverse the deque
d.reverse()
print("After: ", d)

Remove all elements from the deque

The clear() method empties the deque by removing all elements.

from collections import deque

d = deque()

#add elements
d.extend(range(10))
print(d)

#empty the deque
d.clear()

print(d)