Python Language
Deque-module
Zoeken…
Syntaxis
- dq = deque () # Maakt een lege deque
- dq = deque (iterable) # Maakt een deque met enkele elementen
- dq.append (object) # Voegt een object toe rechts van de deque
- dq.appendleft (object) # Voegt object links van de deque toe
- dq.pop () -> object # Verwijdert en retourneert het meest rechtse object
- dq.popleft () -> object # Verwijdert en retourneert het meest linkse object
- dq.extend (iterable) # Voegt enkele elementen rechts van de deque toe
- dq.extendleft (iterable) # Voegt enkele elementen links van de deque toe
parameters
| Parameter | Details |
|---|---|
iterable | Creëert de deque met initiële elementen gekopieerd van een andere iterabele. |
maxlen | Beperkt hoe groot de deque kan zijn, waarbij oude elementen als nieuwe worden verwijderd. |
Opmerkingen
Deze klasse is handig als u een object nodig hebt dat lijkt op een lijst waarmee u snel toevoegingen en pop-bewerkingen van beide kanten kunt uitvoeren (de naam deque staat voor " dubbele wachtrij ").
De aangeboden methoden lijken inderdaad erg op elkaar, behalve dat sommige zoals pop , append of extend kunnen worden toegevoegd met left . De deque datastructuur deque voorkeur boven een lijst als men regelmatig elementen aan beide uiteinden moet invoegen en verwijderen omdat dit het mogelijk maakt om dit in constante tijd O te doen (1).
Eenvoudig gebruik van deque
De belangrijkste methoden die nuttig zijn bij deze klasse zijn popleft en 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])
limiet deque grootte
Gebruik de parameter maxlen tijdens het maken van een deque om de grootte van de deque te beperken:
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)
Beschikbare methoden in deque
Een lege deque maken:
dl = deque() # deque([]) creating empty deque
Deque maken met enkele elementen:
dl = deque([1, 2, 3, 4]) # deque([1, 2, 3, 4])
Element toevoegen aan deque:
dl.append(5) # deque([1, 2, 3, 4, 5])
Element links van deque toevoegen:
dl.appendleft(0) # deque([0, 1, 2, 3, 4, 5])
Lijst met elementen toevoegen aan deque:
dl.extend([6, 7]) # deque([0, 1, 2, 3, 4, 5, 6, 7])
Lijst met elementen toevoegen aan de linkerkant:
dl.extendleft([-2, -1]) # deque([-1, -2, 0, 1, 2, 3, 4, 5, 6, 7])
Met het .pop() -element wordt een item natuurlijk aan de rechterkant verwijderd:
dl.pop() # 7 => deque([-1, -2, 0, 1, 2, 3, 4, 5, 6])
.popleft() gebruiken om een item vanaf de linkerkant te verwijderen:
dl.popleft() # -1 deque([-2, 0, 1, 2, 3, 4, 5, 6])
Verwijder element door zijn waarde:
dl.remove(1) # deque([-2, 0, 2, 3, 4, 5, 6])
De volgorde van de elementen in deque omkeren:
dl.reverse() # deque([6, 5, 4, 3, 2, 0, -2])
Breedte eerste zoekopdracht
De Deque is de enige datastructuur van Python met snelle wachtrijbewerkingen . (Opmerking queue.Queue is normaal gesproken niet geschikt, omdat het bedoeld is voor communicatie tussen threads.) Een basisgebruik van een wachtrij is de breedste eerste zoekopdracht .
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
Stel dat we een eenvoudige gerichte grafiek hebben:
graph = {1:[2,3], 2:[4], 3:[4,5], 4:[3,5], 5:[]}
We kunnen nu de afstanden vanaf een startpositie vinden:
>>> bfs(graph, 1)
{1: 0, 2: 1, 3: 1, 4: 2, 5: 2}
>>> bfs(graph, 3)
{3: 0, 4: 1, 5: 1}