Un deque significa cua de dos extrems. És un tipus especial d'estructura de dades que us permet afegir i eliminar elements d'ambdós extrems de manera eficient.

A diferència de les cues normals (que solen seguir First In First Out), un deque admet operacions tant FIFO com LIFO. Això fa que sigui molt flexible i útil en aplicacions del món real, com ara problemes de finestres lliscants de programació de tasques i processament de dades en temps real.

Exemple:

from collections import deque # Declaring deque  de = deque(['name''age''DOB']) print(de) 

deque(['name' 'age' 'DOB']) 

Per què necessitem deque

• Admet el temps O(1) per afegir/eliminar elements dels dos extrems.
• És més eficient que les llistes per a operacions frontals.
• Pot funcionar tant com a cua (FIFO) com com a pila (LIFO).
• Ideal per programar problemes de finestres corredisses i processament de dades en temps real.
• Ofereix mètodes integrats potents com apèndixesquerra() popleft() i girar ().

Tipus d'entrada de Deque restringida

• Entrada restringida Deque : L'entrada està limitada a un extrem mentre que la supressió està permesa als dos extrems.
• Sortida Restringida Deque : la sortida està limitada a un extrem però es permet la inserció als dos extrems.

Operacions sobre deque 

Aquí hi ha una taula que enumera les operacions integrades d'un deque a Python amb descripcions i les seves corresponents complexitats temporals:

quantes ciutats EUA

Afegir i suprimir elements de la cua

• adjuntar (x): Afegeix x a l'extrem dret del deque.
• apèndixesquerra(x): Afegeix x a l'extrem esquerre del deque.
• estendre (iterable): Afegeix tots els elements de l'iterable a l'extrem dret.
• estendre a l'esquerra (iterable): Afegeix tots els elements de l'iterable a l'extrem esquerre (en ordre invers).
• eliminar (valor): Elimina la primera ocurrència del valor especificat del deque. Si no es troba el valor, genera un ValueError.
• pop(): Elimina i torna un element de l'extrem dret.
• popleft(): Elimina i torna un element de l'extrem esquerre.
• clar (): Elimina tots els elements del deque.

from collections import deque dq = deque([10 20 30]) # Add elements to the right dq.append(40) # Add elements to the left dq.appendleft(5) # extend(iterable) dq.extend([50 60 70]) print('After extend([50 60 70]):' dq) # extendleft(iterable) dq.extendleft([0 5]) print('After extendleft([0 5]):' dq) # remove method dq.remove(20) print('After remove(20):' dq) # Remove elements from the right dq.pop() # Remove elements from the left dq.popleft() print('After pop and popleft:' dq) # clear() - Removes all elements from the deque dq.clear() # deque: [] print('After clear():' dq) 

Sortida:

After extend([50 60 70]): deque([5 10 20 30 40 50 60 70])  
After extendleft([0 5]): deque([5 0 5 10 20 30 40 50 60 70])  
After remove(20): deque([5 0 5 10 30 40 50 60 70])  
After pop and popleft: deque([0 5 10 30 40 50 60])  
After clear(): deque([])

Accés a l'element i la durada del deque

• Indexació: Accediu als elements per posició mitjançant índexs positius o negatius.
• només (): Retorna el nombre d'elements del deque.

import collections dq = collections.deque([1 2 3 3 4 2 4]) # Accessing elements by index print(dq[0]) print(dq[-1]) # Finding the length of the deque print(len(dq)) 

1 4 7 

Recompte Rotació i inversió d'un deque

• recompte (valor): Aquest mètode compta el nombre d'ocurrències d'un element específic al deque.
• girar (n): Aquest mètode gira el deque en n passos. La n positiva gira cap a la dreta i la n negativa gira cap a l'esquerra.
• revés (): Aquest mètode inverteix l'ordre dels elements en el deque.

from collections import deque # Create a deque dq = deque([10 20 30 40 50 20 30 20]) # 1. Counting occurrences of a value print(dq.count(20)) # Occurrences of 20 print(dq.count(30)) # Occurrences of 30 # 2. Rotating the deque dq.rotate(2) # Rotate the deque 2 steps to the right print(dq) dq.rotate(-3) # Rotate the deque 3 steps to the left print(dq) # 3. Reversing the deque dq.reverse() # Reverse the deque print(dq) 

3 2 deque([30 20 10 20 30 40 50 20]) deque([20 30 40 50 20 30 20 10]) deque([10 20 30 20 50 40 30 20])