Intro to a double-ended queue
Speaking of linear data structures, we can think of the list, stack, queue, and linked list. These linear data structures are convenient in adding/removing elements from a collection. However, there’s a common problem: it’s not easy to access elements from the front or end of the collection. In this post, I’ll introduce another linear data structure that solves this problem — deque.
Intro
Deque is the abbreviation of the double-ended queue. As it sounds like, it generalizes a queue, for which elements can be added to or removed from either the front (head) or back (tail). Different from the queue, which follows the rule of FIFO(First In First Out), meaning that element can only go in and out in one direction, deque can form a two-ended collection.
Deque can be implemented by other linear data structures such as queue, stack, list, and linked list. Since deque has a better performance in adding/removing elements to the front of a linear data structure, the deque is frequently applied to such an environment as work stealing algorithm.
Deque in Python and its functions
In order to use deque in Python, we need to import it from the collections library first, then we can create an empty deque d = deque . Following is the function we can apply to a deque:
Let’s first create an empty deque named d :
import collections
from collections import dequed = deque()
append
The function append will add one element to the end of the deque:
d.append(1)=> d = [1]
appendleft
The function appendleft will add one element to the front of the deque:
d.appendleft(0)=> d = [0, 1]
pop
The function pop will remove one element from the end of the deque:
d.pop()=> d = [0]
popleft
The function popleft will remove one element from the front of the deque:
d.popleft()=> d = []
clear
The function clear will remove all elements from the deque, remain an empty deque:
d.clear()=> d = []
extend
The function extend will take an iterable argument like a list or a string, then add it to the end of the deque:
d.extend('abc')=> d = ['a', 'b', 'c']d.extend([1, 2, 3])=> d = ['a', 'b', 'c', 1, 2, 3]
extendleft
The function extend will take an iterable argument like a list or a string, then add it to the front of the deque:
d.extendleft('python')=> d = ['n', 'o', 'h', 't', 'y', 'p', 'a', 'b', 'c', 1, 2, 3]
rotate
The function roate will take an integer argument, it could be a positive or negative integer. A positive integer will rotate all elements in a deque by that amount to the right, otherwise to the left.
d.rotate(-1)=> d = ['o', 'h', 't', 'y', 'p', 'a', 'b', 'c', 1, 2, 3, 'n'] d.rotate(2)=> d = [3, 'n', 'o', 'h', 't', 'y', 'p', 'a', 'b', 'c', 1, 2]
maxlen
The function maxlen is used in initialization. It takes an integer as the fixed length of the deque. And the maxlen can not be modified once initialized.
d1 = deque('abc', maxlen=5)
=> d1 = ['a', 'b', 'c']d1.extend('def')
#since the max length is 5, when length exceeds, it automatically remove elements from the beginning
=> d1 = ['b', 'c', 'd', 'e', 'f'] d1.maxlen
=> 5d1.maxlen = 6
=> error, can't change the maxlen of a deque
Deque has many applications due to its performance in adding/removing elements in two ways.
