Поиск…


Синтаксис

  • dq = deque () # Создает пустой deque
  • dq = deque (iterable) # Создает deque с некоторыми элементами
  • dq.append (объект) # Добавляет объект справа от deque
  • dq.appendleft (object) # Добавляет объект слева от deque
  • dq.pop () -> object # Удаляет и возвращает правый объект
  • dq.popleft () -> object # Удаляет и возвращает левый самый объект
  • dq.extend (iterable) # Добавляет некоторые элементы справа от deque
  • dq.extendleft (iterable) # Добавляет некоторые элементы слева от deque

параметры

параметр подробности
iterable Создает deque с исходными элементами, скопированными из другого итерабельного.
maxlen Ограничивает, насколько большой может быть дека, выталкивая старые элементы как новые.

замечания

Этот класс полезен, когда вам нужен объект, похожий на список, который позволяет быстро добавлять и удалять операции с обеих сторон (имя deque означает « двойная очередь »).

Предоставленные методы действительно очень похожи, за исключением того, что некоторые из них, такие как pop , append или extend могут быть добавлены left . Структура данных deque должна быть предпочтительнее списка, если нужно часто вставлять и удалять элементы на обоих концах, потому что это позволяет делать это в постоянное время O (1).

Использование базового deque

Основными методами, которые полезны для этого класса, являются popleft и 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])

ограничение размера deque

Используйте параметр maxlen , создавая deque для ограничения размера 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)

Доступные методы в deque

Создание пустого deque:

dl = deque()  # deque([]) creating empty deque

Создание deque с некоторыми элементами:

dl = deque([1, 2, 3, 4])  # deque([1, 2, 3, 4])

Добавление элемента в deque:

dl.append(5)  # deque([1, 2, 3, 4, 5])

Добавление элемента левой стороны deque:

dl.appendleft(0)  # deque([0, 1, 2, 3, 4, 5])

Добавление списка элементов в deque:

dl.extend([6, 7])  # deque([0, 1, 2, 3, 4, 5, 6, 7])

Добавление списка элементов с левой стороны:

dl.extendleft([-2, -1])  # deque([-1, -2, 0, 1, 2, 3, 4, 5, 6, 7])

Использование .pop() естественно удалит элемент с правой стороны:

dl.pop()  # 7 => deque([-1, -2, 0, 1, 2, 3, 4, 5, 6])

Использование .popleft() для удаления элемента с левой стороны:

dl.popleft()  # -1 deque([-2, 0, 1, 2, 3, 4, 5, 6])

Удалить элемент по его значению:

dl.remove(1)  # deque([-2, 0, 2, 3, 4, 5, 6])

Обратный порядок элементов в deque:

dl.reverse()  # deque([6, 5, 4, 3, 2, 0, -2])

Поиск в ширину

Deque - единственная структура данных Python с быстрыми операциями очереди . (Note queue.Queue обычно не подходит, поскольку он предназначен для связи между потоками.) Основной пример использования очереди - это поиск по ширине .

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

Скажем, у нас есть простой ориентированный граф:

graph = {1:[2,3], 2:[4], 3:[4,5], 4:[3,5], 5:[]}

Теперь мы можем найти расстояния от некоторой исходной позиции:

>>> bfs(graph, 1)
{1: 0, 2: 1, 3: 1, 4: 2, 5: 2}

>>> bfs(graph, 3)
{3: 0, 4: 1, 5: 1}


Modified text is an extract of the original Stack Overflow Documentation
Лицензировано согласно CC BY-SA 3.0
Не связан с Stack Overflow