collections.
Kolejka dwustronna: szybkie dodawanie i usuwanie elementów z obu końców, opcjonalnie z limitem długości.
- Zwraca
- Obiekt
deque.
Przykład
#from collections import deque
queue = deque(["Ania", "Kuba"])
queue.append("Ola")
queue.appendleft("Iga")
print(queue)
print(queue.popleft())
print(queue.pop())
print(queue, len(queue))Definicja i zastosowanie
#Klasa deque (od „double-ended queue”, czyli kolejka dwustronna) z modułu collections działa jak lista zoptymalizowana pod operacje na obu końcach. Metody append() i pop() działają na prawym końcu, a appendleft() i popleft() na lewym. Każda z nich wykonuje się w stałym czasie, niezależnie od długości kolejki.
Zwykła lista też ma pop(0) i insert(0, x), ale te operacje przesuwają wszystkie pozostałe elementy, więc przy dużych listach są wolne. Dlatego kolejki zadań, przeszukiwanie grafu wszerz (BFS) czy bufor ostatnich zdarzeń buduje się na deque.
Parametr maxlen ogranicza długość: gdy kolejka jest pełna, dodanie elementu z jednej strony usuwa element z przeciwnego końca. To gotowy sposób na przechowywanie np. kilku ostatnich wyników. Metoda rotate(n) przesuwa elementy w kółko o n pozycji. Dostęp przez indeks działa, ale w środku długiej kolejki jest wolniejszy niż w liście, a wycinki nie są obsługiwane.
Składnia
#from collections import deque
deque(iterable, maxlen=None)
kolejka.append(x)
kolejka.appendleft(x)
kolejka.pop()
kolejka.popleft()
kolejka.rotate(n)Parametry
#iterable
kolekcja, opcjonalna
Początkowe elementy kolejki.maxlen
int lub None, domyślnie None
Maksymalna długość. Po jej przekroczeniu elementy z przeciwnego końca są usuwane.
Więcej przykładów
#from collections import deque
recent = deque(maxlen=3)
for score in [72, 95, 64, 88, 91]:
recent.append(score)
print(list(recent))
print(recent)
print(sum(recent) / len(recent))from collections import deque
tasks = deque(["1_1", "1_2", "1_3"])
while tasks:
task = tasks.popleft()
print("Sprawdzam", task)
players = deque(["Ania", "Kuba", "Ola"])
players.rotate(1)
print(players)
players.rotate(-2)
print(players)from collections import deque
paths = {
"Egipt": ["Kosmos", "Rzym"],
"Kosmos": ["Park Jurajski"],
"Rzym": ["Safari"],
"Park Jurajski": ["Safari"],
"Safari": [],
}
def shortest(start, goal):
queue = deque([[start]])
seen = {start}
while queue:
route = queue.popleft()
if route[-1] == goal:
return route
for neighbor in paths[route[-1]]:
if neighbor not in seen:
seen.add(neighbor)
queue.append(route + [neighbor])
return None
print(shortest("Egipt", "Safari"))Dobre praktyki
#- Gdy często usuwasz elementy z początku listy przez
pop(0), zamień ją nadequei używajpopleft(). dequenie obsługuje wycinków, np.kolejka[1:3]. Jeśli ich potrzebujesz, zamień kolejkę na listę albo użyjitertools.islice().- Pusta kolejka jest fałszywa w warunkach, więc pętla
while queue:działa, dopóki zostały w niej elementy.
Powiązane hasła
#- list.pop()Usuwa element o podanym indeksie (domyślnie ostatni) i go zwraca.
- list.append()Dodaje jeden element na koniec listy.
- list.insert()Wstawia element w wybrane miejsce listy.
- collections.CounterSłownik do zliczania: dla każdego elementu przechowuje liczbę jego wystąpień.
- itertoolsNarzędzia do pracy z iteratorami: łączenie, grupowanie, kombinacje i nieskończone ciągi.
Widzisz błąd albo brakuje przykładu? Napisz do nas.