Python Language
Deque-modul
Sök…
Syntax
- dq = deque () # Skapar ett tomt vattenfönster
- dq = deque (iterable) # Skapar en deque med vissa element
- dq.append (object) # Lägger till objekt till höger om tullen
- dq.appendleft (object) # Lägger till objekt till vänster om turen
- dq.pop () -> objekt # Tar bort och returnerar det mest rätt objektet
- dq.popleft () -> objekt # Tar bort och returnerar det mest vänstra objektet
- dq.extend (iterable) # Lägger till några element till höger om turen
- dq.extendleft (iterable) # Lägger till några element till vänster om turen
parametrar
| Parameter | detaljer |
|---|---|
iterable | Skapar täcken med initiala element som kopierats från en annan iterable. |
maxlen | Begränsar hur stor täcken kan vara, och skjuta ut gamla element som nya läggs till. |
Anmärkningar
Den här klassen är användbar när du behöver ett objekt som liknar en lista som tillåter snabba tilläggs- och pop-operationer från endera sidan ( deque står för ” dubbelkön ”).
Metoderna som tillhandahålls är verkligen mycket lika, förutom att vissa som pop , append eller extend kan vara fixerade med left . deque bör föredras framför en lista om man ofta behöver infoga och radera element i båda ändarna eftersom den tillåter det i konstant tid O (1).
Grundläggande torkning med
De viktigaste metoderna som är användbara med den här klassen är popleft och 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])
begränsa täckningsstorleken
Använd maxlen parametern när du skapar en täck för att begränsa storleken på tecken:
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)
Tillgängliga metoder i färg
Skapa tomt skiva:
dl = deque() # deque([]) creating empty deque
Skapa skiva med några element:
dl = deque([1, 2, 3, 4]) # deque([1, 2, 3, 4])
Lägga till element i torkning:
dl.append(5) # deque([1, 2, 3, 4, 5])
Lägga till elementets vänstra sida av täcken:
dl.appendleft(0) # deque([0, 1, 2, 3, 4, 5])
Lägger till en lista med element till torkning:
dl.extend([6, 7]) # deque([0, 1, 2, 3, 4, 5, 6, 7])
Lägga till en lista över element till från vänster:
dl.extendleft([-2, -1]) # deque([-1, -2, 0, 1, 2, 3, 4, 5, 6, 7])
Att använda .pop() -elementet kommer naturligtvis att ta bort ett objekt från höger sida:
dl.pop() # 7 => deque([-1, -2, 0, 1, 2, 3, 4, 5, 6])
Använd .popleft() att ta bort ett objekt från vänster sida:
dl.popleft() # -1 deque([-2, 0, 1, 2, 3, 4, 5, 6])
Ta bort elementet med dess värde:
dl.remove(1) # deque([-2, 0, 2, 3, 4, 5, 6])
Omvänd ordning på elementen i täck:
dl.reverse() # deque([6, 5, 4, 3, 2, 0, -2])
Utöka första sökningen
Deque är den enda Python-datastrukturen med snabba köoperationer . (Notera queue.Queue är normalt inte lämpligt eftersom det är avsett för kommunikation mellan trådar.) Ett grundläggande användningsfall för en kö är breddens första sökning .
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
Säg att vi har en enkel riktad graf:
graph = {1:[2,3], 2:[4], 3:[4,5], 4:[3,5], 5:[]}
Vi kan nu hitta avstånden från någon utgångsposition:
>>> bfs(graph, 1)
{1: 0, 2: 1, 3: 1, 4: 2, 5: 2}
>>> bfs(graph, 3)
{3: 0, 4: 1, 5: 1}
