Python Language
Moduł Deque
Szukaj…
Składnia
- dq = deque () # Tworzy pusty deque
- dq = deque (iterable) # Tworzy deque z niektórymi elementami
- dq.append (object) # Dodaje obiekt po prawej stronie deque
- dq.appendleft (object) # Dodaje obiekt po lewej stronie deque
- dq.pop () -> obiekt # Usuwa i zwraca najbardziej prawy obiekt
- dq.popleft () -> obiekt # Usuwa i zwraca obiekt znajdujący się najbardziej po lewej stronie
- dq.extend (iterable) # Dodaje niektóre elementy po prawej stronie deque
- dq.extendleft (iterable) # Dodaje niektóre elementy po lewej stronie deque
Parametry
| Parametr | Detale |
|---|---|
iterable | Tworzy deque z elementami początkowymi skopiowanymi z innej iterowalnej. |
maxlen | Ogranicza wielkość deque, wypychając stare elementy jak nowe są dodawane. |
Uwagi
Ta klasa jest przydatna, gdy potrzebujesz obiektu podobnego do listy, który umożliwia szybkie dodawanie i pop operacji z każdej strony (nazwa deque oznacza „ kolejkę podwójnie zakończoną ”).
Podane metody są rzeczywiście bardzo podobne, z tym wyjątkiem, że niektóre takie jak pop , append lub extend mogą być poprzedzone left . deque danych deque powinna być preferowana w stosunku do listy, jeśli trzeba często wstawiać i usuwać elementy na obu końcach, ponieważ pozwala to robić w stałym czasie O (1).
Podstawowe użycie deque
Główne metody przydatne w tej klasie to popleft i 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])
ogranicz wielkość deque
Użyj parametru maxlen podczas tworzenia deque, aby ograniczyć rozmiar 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)
Dostępne metody w deque
Tworzenie pustego deque:
dl = deque() # deque([]) creating empty deque
Tworzenie deque z niektórymi elementami:
dl = deque([1, 2, 3, 4]) # deque([1, 2, 3, 4])
Dodawanie elementu do deque:
dl.append(5) # deque([1, 2, 3, 4, 5])
Dodawanie elementu po lewej stronie deque:
dl.appendleft(0) # deque([0, 1, 2, 3, 4, 5])
Dodawanie listy elementów do deque:
dl.extend([6, 7]) # deque([0, 1, 2, 3, 4, 5, 6, 7])
Dodawanie listy elementów do z lewej strony:
dl.extendleft([-2, -1]) # deque([-1, -2, 0, 1, 2, 3, 4, 5, 6, 7])
Użycie elementu .pop() naturalnie usunie element z prawej strony:
dl.pop() # 7 => deque([-1, -2, 0, 1, 2, 3, 4, 5, 6])
Użycie elementu .popleft() do usunięcia elementu z lewej strony:
dl.popleft() # -1 deque([-2, 0, 1, 2, 3, 4, 5, 6])
Usuń element według jego wartości:
dl.remove(1) # deque([-2, 0, 2, 3, 4, 5, 6])
Odwróć kolejność elementów w deque:
dl.reverse() # deque([6, 5, 4, 3, 2, 0, -2])
Szerokość Pierwsze wyszukiwanie
Deque to jedyna struktura danych w języku Python z szybkimi operacjami kolejkowania . (Uwaga queue.Queue zwykle nie jest odpowiednia, ponieważ jest przeznaczona do komunikacji między wątkami). Podstawowym przypadkiem użycia kolejki jest pierwsze wyszukiwanie szerokości .
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
Powiedzmy, że mamy prosty skierowany wykres:
graph = {1:[2,3], 2:[4], 3:[4,5], 4:[3,5], 5:[]}
Możemy teraz znaleźć odległości od pozycji początkowej:
>>> bfs(graph, 1)
{1: 0, 2: 1, 3: 1, 4: 2, 5: 2}
>>> bfs(graph, 3)
{3: 0, 4: 1, 5: 1}