Python Language
Модуль Deque
Поиск…
Синтаксис
- 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}