Python Language
Módulo Deque
Buscar..
Sintaxis
- dq = deque () # Crea un deque vacío
- dq = deque (iterable) # Crea un deque con algunos elementos
- dq.append (objeto) # Agrega un objeto a la derecha del deque
- dq.appendleft (objeto) # Agrega un objeto a la izquierda del deque
- dq.pop () -> object # Elimina y devuelve el objeto más a la derecha
- dq.popleft () -> object # Elimina y devuelve el objeto más a la izquierda
- dq.extend (iterable) # Agrega algunos elementos a la derecha del deque
- dq.extendleft (iterable) # Agrega algunos elementos a la izquierda del deque
Parámetros
| Parámetro | Detalles |
|---|---|
iterable | Crea el deque con elementos iniciales copiados de otro iterable. |
maxlen | Limita qué tan grande puede ser el deque, eliminando elementos antiguos a medida que se agregan nuevos. |
Observaciones
Esta clase es útil cuando necesita un objeto similar a una lista que permita operaciones rápidas de agregar y abrir desde cualquier lado (el nombre deque significa " cola de doble extremo ").
Los métodos proporcionados son, de hecho, muy similares, excepto que algunos como el pop , el append o la extend pueden incluir con el sufijo left . La estructura de datos de deque debería ser preferible a una lista si uno necesita insertar y eliminar elementos con frecuencia en ambos extremos porque permite hacerlo en tiempo constante O (1).
Uso básico deque
Los principales métodos que son útiles con esta clase son popleft y 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])
límite de tamaño de salida
Use el parámetro maxlen mientras crea un deque para limitar el tamaño del 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)
Métodos disponibles en deque.
Creando deque vacío:
dl = deque() # deque([]) creating empty deque
Creando deque con algunos elementos:
dl = deque([1, 2, 3, 4]) # deque([1, 2, 3, 4])
Añadiendo elemento a deque:
dl.append(5) # deque([1, 2, 3, 4, 5])
Añadiendo elemento del lado izquierdo del deque:
dl.appendleft(0) # deque([0, 1, 2, 3, 4, 5])
Añadiendo lista de elementos a deque:
dl.extend([6, 7]) # deque([0, 1, 2, 3, 4, 5, 6, 7])
Añadiendo lista de elementos desde el lado izquierdo:
dl.extendleft([-2, -1]) # deque([-1, -2, 0, 1, 2, 3, 4, 5, 6, 7])
El uso del elemento .pop() eliminará naturalmente un elemento del lado derecho:
dl.pop() # 7 => deque([-1, -2, 0, 1, 2, 3, 4, 5, 6])
Usando el elemento .popleft() para eliminar un elemento del lado izquierdo:
dl.popleft() # -1 deque([-2, 0, 1, 2, 3, 4, 5, 6])
Eliminar elemento por su valor:
dl.remove(1) # deque([-2, 0, 2, 3, 4, 5, 6])
Invertir el orden de los elementos en deque:
dl.reverse() # deque([6, 5, 4, 3, 2, 0, -2])
Amplia primera búsqueda
Deque es la única estructura de datos de Python con operaciones rápidas de cola . (Tenga en cuenta queue.Queue normalmente no es adecuado, ya que está destinado a la comunicación entre subprocesos). Un caso de uso básico de una cola es la primera búsqueda de amplitud .
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
Digamos que tenemos un gráfico dirigido simple:
graph = {1:[2,3], 2:[4], 3:[4,5], 4:[3,5], 5:[]}
Ahora podemos encontrar las distancias desde alguna posición inicial:
>>> bfs(graph, 1)
{1: 0, 2: 1, 3: 1, 4: 2, 5: 2}
>>> bfs(graph, 3)
{3: 0, 4: 1, 5: 1}
