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:
add_front(e) |
Add element e at the front of the deque. |
add_back(e) |
Add element e at the back of the deque. |
remove_front() |
Remove and return the first element in the deque. |
remove_back() |
Remove and return the last element in the deque. |
first() |
Return a reference to the first element in the deque without removing it. |
last() |
Return a reference to the last element in the deque without removing it |
is_empty() |
Check whether the deque is empty. True if so, False otherwise. |
len() |
Return the number of elements in the deque. |
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:
append(e) |
Add an element at the back of the deque. |
appendleft(e) |
Add an element at the front of the deque. |
pop() |
Remove the element at the back. Raises an IndexError exception if the deque is empty |
popleft() |
Remove the element at the front. Raises an IndexError exception if the deque is empty |
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.
Use append() and appendleft() methods to populate a deque
#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.
Consume deque elements
#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.
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.
use extend() and extendleft() methods
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.
Use insert() method
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.
remove all elements
from collections import deque
d = deque()
#add elements
d.extend(range(10))
print(d)
#empty the deque
d.clear()
print(d)