Python suggest change

deque module

Deque (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.

Namedescription
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() -> objectRemoves and returns the right most object
dq.popleft() -> objectRemoves 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])

Feedback about page:

Feedback:
Optional: your email if you want me to get back to you:


Table Of Contents
32 Set
46 Enum
73 deque module
105 Stack
119 Mixins
121 ArcPy
127 Arrays
139 Neo4j
141 Curses
146 heapq
155 Audio
156 pyglet
158 ijson
161 Flask
164 pygame
167 Gzip
168 ctypes
187 shelve
  ↑ ↓ to navigate     ↵ to select     Esc to close