deque module
suggest changeDeque (double-ended queue) is a list that allows fast adding and removing an item from both the beginning and the end of the list. In a traditional list only adding/removing at the end is fast.
Name | description |
---|---|
dq = deque() | Creates an empty deque |
dq = deque(iterable) | Creates a deque with some elements |
dq.append(object) | Adds object to the right of the deque |
dq.appendleft(object) | Adds object to the left of the deque |
dq.pop() -> object | Removes and returns the right most object |
dq.popleft() -> object | Removes and returns the left most object |
dq.extend(iterable) | Adds some elements to the right of the deque |
dq.extendleft(iterable) | Adds some elements to the left of the deque |
Basic use
The main methods that are useful with this class are popleft
and appendleft
from collections import deque
d = deque([1, 2, 3])
p = d.popleft() # p = 1, d = deque([2, 3])
d.appendleft(5) # d = deque([5, 2, 3])
Limit deque size
Use the maxlen
parameter while creating a deque to limit the size of the deque:
from collections import deque
d = deque(maxlen=3) # only holds 3 items
d.append(1) # deque([1])
d.append(2) # deque([1, 2])
d.append(3) # deque([1, 2, 3])
d.append(4) # deque([2, 3, 4]) (1 is removed because its maxlen is 3)
Breadth First Search
A basic use case of a Queue is the breadth first search:
from collections import deque
def bfs(graph, root):
distances = {}
distances[root] = 0
q = deque([root])
while q:
# The oldest seen (but not yet visited) node will be the left most one.
current = q.popleft()
for neighbor in graph[current]:
if neighbor not in distances:
distances[neighbor] = distances[current] + 1
# When we see a new node, we add it to the right side of the queue.
q.append(neighbor)
return distances
Say we have a simple directed graph:
graph = {1:[2,3], 2:[4], 3:[4,5], 4:[3,5], 5:[]}
We can now find the distances from some starting position:
>>> bfs(graph, 1)
{1: 0, 2: 1, 3: 1, 4: 2, 5: 2}
>>> bfs(graph, 3)
{3: 0, 4: 1, 5: 1}
Available methods in deque
Creating empty deque:
dl = deque() # deque([]) creating empty deque
Creating deque with some elements:
dl = deque([1, 2, 3, 4]) # deque([1, 2, 3, 4])
Adding element to deque:
dl.append(5) # deque([1, 2, 3, 4, 5])
Adding element left side of deque:
dl.appendleft(0) # deque([0, 1, 2, 3, 4, 5])
Adding list of elements to deque:
dl.extend([6, 7]) # deque([0, 1, 2, 3, 4, 5, 6, 7])
Adding list of elements to from the left side:
dl.extendleft([-2, -1]) # deque([-1, -2, 0, 1, 2, 3, 4, 5, 6, 7])
Using .pop()
element will naturally remove an item from the right side:
dl.pop() # 7 => deque([-1, -2, 0, 1, 2, 3, 4, 5, 6])
Using .popleft()
element to remove an item from the left side:
dl.popleft() # -1 deque([-2, 0, 1, 2, 3, 4, 5, 6])
Remove element by its value:
dl.remove(1) # deque([-2, 0, 2, 3, 4, 5, 6])
Reverse the order of the elements in deque:
dl.reverse() # deque([6, 5, 4, 3, 2, 0, -2])