Deque In Python - Tutorial con esempi

Se sei uno sviluppatore Python, probabilmente hai sentito parlare di una deque, o "coda a doppia estremità". È uno strumento potente che può aumentare l'efficienza della tua applicazione e velocizzarne le prestazioni.

Un deque è un tipo di dati contenitore specializzato che offre operazioni di accodamento e pop più rapide da entrambe le estremità del contenitore. Ciò lo rende uno strumento prezioso per l'implementazione di code e stack, che sono tipi di dati simili a elenchi comuni nell'informatica.

È una struttura dati di basso livello e altamente ottimizzata che è molto utile per una varietà di applicazioni. Come programmatore Python, una deque è uno strumento che vorrai avere nel tuo arsenale.

Continua a leggere per saperne di più su Deques e su come puoi implementarle nel tuo codice Python !

Sommario

• Che cos'è una Deque?
  • Caratteristiche di A Python Deque
  • Applicazioni di A Deque
• Come creare e inizializzare una Deque
  • Utilizzo della funzione deque()
  • Inizializzazione di una Deque con Elements
• Come eseguire operazioni comuni di deque
  • Aggiunta di elementi a una deque
  • Aggiunta di più elementi di dati a una deque
  • Rimozione di elementi da una deque
  • Rimozione di tutti gli elementi da una deque
  • Accesso agli elementi di una deque
  • Elementi di modifica di una Deque
• Come lavorare con una Deque come coda
  • Utilizzo dei metodi append() e popleft()
  • Verifica se una coda Deque è vuota
• Lavorare con Deque come Stack
  • Utilizzo dei metodi append() e pop()
  • Controllo di un oggetto Deque vuoto
• Cos'è una Deque ristretta?
  • • Input Ristretto Deque
    • Uscita Deque ristretta
• Concludiamo questo

Che cos'è una Deque?

Se non conosci Python o la programmazione di computer in generale, ti starai chiedendo cos'è una deque. Deque sta per " coda a doppia estremità " ed è una struttura di dati che consente di aggiungere e rimuovere elementi da entrambe le estremità della coda.

È simile a una normale coda ma con la flessibilità aggiuntiva di poter aggiungere e rimuovere elementi sia dalla parte anteriore che da quella posteriore della coda. Questo è possibile perché la deque di Python è implementata come una lista doppiamente collegata.

In Python, le deque sono implementate usando il modulo collections, che fornisce una classe deque. Questa classe fornisce una serie di metodi per aggiungere e rimuovere elementi dalla deque.

Fornisce anche funzioni per altre operazioni utili come ruotare la deque o cancellarla completamente.

Caratteristiche di A Python Deque

A differenza di un elenco normale, che ha una complessità temporale O(n) per le operazioni di accodamento e pop, una deque fornisce una complessità temporale O(1). Ciò lo rende significativamente più veloce ed efficiente in termini di memoria per queste operazioni di lettura e scrittura.

Ecco alcune altre funzionalità deque di Python che dovresti conoscere:

• È una struttura dati mutabile.

• Può memorizzare più tipi di dati, ad esempio numeri interi, tuple, array, ecc.

• Supporta l'indicizzazione, ma non le operazioni di slicing.

• Non supporta l'ordinamento sul posto

• Supporta funzioni e operazioni iterabili incorporate comuni come in , sorted() , len() , reverse() , ecc.

Applicazioni di A Deque

I deques sono utili per una serie di motivi. Ad esempio, possono essere utilizzati per implementare una coda o uno stack, entrambe strutture di dati comuni nell'informatica.

Possono anche essere utilizzati per elaborare in modo efficiente i dati in tempo reale, ad esempio nelle applicazioni di streaming o nei sistemi che richiedono un accesso rapido ai dati.

Oltre a essere utilizzate per code e stack, le deques possono essere utilizzate anche per implementare algoritmi di ricerca in ampiezza. Sono anche utili per mantenere una finestra scorrevole di elementi in una sequenza più ampia.

Come creare e inizializzare una Deque

Puoi creare una deque usando una funzione incorporata dal modulo collezioni. Diamo un'occhiata da vicino a come creare e riempire questa struttura di dati.

Utilizzo della funzione deque()

Per creare una deque in Python, puoi usare la funzione incorporata deque() dal modulo collections. Questa funzione restituisce un nuovo oggetto deque vuoto che è possibile utilizzare per implementare una coda a doppia estremità.

Ecco un esempio di come creare un oggetto deque vuoto:

from collections import deque 

my_deque = deque() 

Puoi anche creare una deque con elementi iniziali passando un iterabile (lista, tupla, ecc.) alla funzione deque() . La deque verrà inizializzata con gli elementi nell'iterabile, da sinistra a destra.

Ecco un esempio:

from collections import deque

my_list = [1, 2, 3, 4, 5] 
my_deque = deque(my_list)

Inizializzazione di una Deque con Elements

Puoi anche inizializzare una deque vuota con elementi usando vari metodi. Un modo per farlo è usare i metodi append() e appendleft() per aggiungere elementi alla deque rispettivamente dal lato destro e sinistro.

Ecco un esempio:

from collections import deque

#Initialize the empty deque
my_deque = deque()
print(my_deque)

#Add Values to the deque
my_deque.append(1) 
my_deque.append(2) 
my_deque.appendleft(3) 

print(my_deque)

Dopo aver eseguito questo codice, la deque conterrà gli elementi [3, 1, 2].

Un altro modo per inizializzare una deque con elementi è passare un elenco di elementi alla funzione deque() .

Ecco un esempio:

from collections import deque

my_deque = deque([1, 2, 3]) 

L'esecuzione di questo codice creerà un oggetto deque contenente gli elementi [1, 2, 3] .

Nel complesso, la creazione e l'inizializzazione di una deque in Python è semplice e può essere eseguita utilizzando la funzione incorporata deque() . Puoi anche farlo aggiungendo elementi a una deque vuota usando i metodi append() e appendleft() .

Come eseguire operazioni comuni di deque

Ci sono molte operazioni che puoi eseguire su oggetti deque in Python. Diamo un'occhiata ad alcuni dei più popolari.

Aggiunta di elementi a una deque

Puoi aggiungere elementi a una deque Python usando i metodi append() e appendleft() . Il metodo append() aggiunge un elemento all'estremità destra della deque mentre il metodo appendleft() aggiunge un elemento all'estremità sinistra della deque.

Ecco un esempio:

import collections 

# Create an empty deque 
my_deque = collections.deque() 

# Add elements to the deque 
my_deque.append(1) 
my_deque.appendleft(2) 
my_deque.append(3) 

print(my_deque) 

# Output: 
deque([2, 1, 3])

Aggiunta di più elementi di dati a una deque

Se non vuoi aggiungere elementi di dati a una deque uno per uno, puoi velocizzare il processo con le funzioni extend() o extendleft() . Queste funzioni accettano un iterabile e aggiungono rispettivamente il contenuto dell'iterabile alla fine o all'estremità sinistra della deque.

Ecco un esempio:

from collections import deque

my_list = [1, 2, 3, 4, 5] 
my_deque = deque(my_list)

#Creating a tuple and list
cont = (11, 12, 13, 14)
full = [10,20,30]

#Extending the deque from the right
my_deque.extend(cont)
print(my_deque)

#Extending the deque from the left
my_deque.extendleft(full)
print(my_deque)

Nel codice sopra la funzione extend() aggiunge i valori multipli nella cont tupla alla fine della deque. Successivamente, la funzione extendleft() aggiunge gli elementi di dati multipli nell'elenco completo all'estremità sinistra della deque.

Rimozione di elementi da una deque

Puoi rimuovere elementi da una deque Python usando i metodi pop() e popleft() . Il metodo pop() rimuove e restituisce l'elemento più a destra della deque mentre il metodo popleft() rimuove e restituisce l'elemento più a sinistra della deque.

Ecco un esempio:

import collections 

#Create a deque with some elements 
my_deque = collections.deque([1, 2, 3, 4, 5]) 

#Remove elements from the deque 
my_deque.pop() 
my_deque.popleft() 

print(my_deque) 

# Output: deque([2, 3, 4])

Puoi anche rimuovere un valore specifico da una deque usando la funzione remove() . La funzione rimuove la prima occorrenza del valore specificato dalla deque.

Ecco un esempio:

import collections 

#Create a deque with some elements 
my_deque = collections.deque([1, 2, 1, 4, 5]) 

#Remove elements from the deque 
my_deque.remove(1)

print(my_deque) 

# Output: deque([2, 1, 4, 5])

Se l'elemento non viene trovato, Python restituirà un ValueError .

Rimozione di tutti gli elementi da una deque

Per rimuovere tutti gli elementi da una Deque e riportarla a uno stato vuoto, possiamo usare la funzione clear() . Ecco come funziona:

from collections import deque 

#Create a deque with some elements 
my_deque = deque([1, 2, 1, 4, 5]) 

#Remove all elements from the deque 
my_deque.clear()

print(my_deque) 

# Output: 
deque([])

Accessing Elements of a Deque

You can access elements of a Python deque using the indexing operator []. You can also use a negative value in the indexing operator to access the deque elements from the right.

The indexing starts from 0 for the leftmost element and -1 for the rightmost element. Here’s an example:

import collections 

# Create a deque with some elements 
my_deque = collections.deque([1, 2, 3, 4, 5]) 

# Access elements of the deque 
print(my_deque[0]) 
# Output: 1 

print(my_deque[-1]) 
# Output: 5 

Modifying Elements of a Deque

You can modify elements of a Python deque using the indexing operator “[]” and the assignment operator “=“. Here’s an example:

from collections import deque

# Create a deque with some elements 
my_deque = deque([1, 2, 3, 4, 5]) 
print(my_deque)

# Modify elements of the deque 
my_deque[0] = 10 
my_deque[-1] = 50 

print(my_deque) 

In the above code, the indexing operator changes the first and last elements of the deque to 10 and 50 respectively.

These are the basic operations you can perform on a deque object in Python. With these operations, you can efficiently implement various data structures such as queues, stacks, and more.

How to Work with a Deque as a Queue

You can use a deque in Python to implement a queue data structure. A queue is an abstract data type that operates on a first in first out (FIFO) basis.

What this means is that you can append new items from one end of the queue and push out old items from the other end.

A good way to explain this is a line at a store. Typically, the first person to arrive will be at the head of the line and will be attended to first.

New arrivals will have to head to the back of the line and wait their turn. So, the first in will be the first answered, while the last in will be the last attended to.

Here’s how you can use a deque to implement queues.

Using append() and popleft() Methods

Per utilizzare una deque come coda, puoi utilizzare il metodo append() per aggiungere elementi all'estremità destra della deque. Inoltre, puoi utilizzare il metodo popleft() per rimuovere gli elementi dall'estremità sinistra della deque.

Questo è un modo molto efficiente per implementare una coda in Python. Ecco un esempio:

from collections import deque 

queue = deque() 
queue.append(1) 
queue.append(2) 
queue.append(3) 

print(queue) 
# Output: deque([1, 2, 3]) 

x = queue.popleft() 
print(x) 
# Output: 1 

print(queue) 
# Output: deque([2, 3]) 

Come puoi vedere, il metodo append() aggiunge elementi all'estremità destra della deque e il metodo popleft() rimuove elementi dall'estremità sinistra della deque.

Questo è esattamente ciò di cui abbiamo bisogno in un'implementazione della coda.

Verifica se una coda Deque è vuota

Per verificare se una deque è vuota, puoi usare l' operatore not . Ecco un esempio:

from collections import deque 

queue = deque() 
if not queue: 
   print("Queue is empty") 
else: 
   print("Queue is not empty") 

Questo produrrà " Queue is empty " perché la deque è vuota. Se aggiungi elementi alla deque, non sarà più vuota.

In conclusione, usare una deque come coda in Python è molto efficiente e facile da implementare.

Lavorare con Deque come Stack

Proprio come le code, gli stack sono un altro esempio di tipi di dati astratti che puoi usare per organizzare i dati. A differenza delle code, gli stack operano in modalità LIFO (Last In First Out).

Ciò significa che l'ultimo elemento nella deque sarà il primo elemento fuori. Ecco come puoi implementarlo utilizzando la struttura dei dati sottostante.

Utilizzo dei metodi append() e pop()

Quando si utilizza Deque come stack, è possibile aggiungere elementi in cima allo stack utilizzando il metodo append() . Questo metodo aggiunge l'elemento all'estremità destra della deque.

Allo stesso modo, puoi rimuovere gli elementi dalla parte superiore dello stack utilizzando il metodo pop() . Questo metodo rimuove e restituisce l'elemento più a destra della deque.

Ad esempio, supponiamo che tu abbia una deque chiamata " my_stack " e desideri aggiungere un elemento in cima allo stack. Puoi utilizzare il seguente codice:

 my_stack.append(5) 

Questo aggiungerà l'elemento 5 in cima alla pila.

Se vuoi rimuovere l'elemento in cima allo stack, puoi usare il metodo pop(): `

bal = my_stack.pop() 

print(bal)
# Output: 5

Questo rimuoverà e restituirà l'elemento più a destra della deque, che in questo caso è 5.

Controllo di un oggetto Deque vuoto

Puoi controllare se uno stack deque è vuoto usando l'operatore booleano " not ". Se la deque è vuota, " not my_deque " restituirà True . In caso contrario, restituirà False .

Per esempio, diciamo che hai uno stack deque chiamato " my_deque " e vuoi controllare se è vuoto. Puoi utilizzare il seguente codice:

if not my_deque: 
   print("The deque is empty") 

else: 
   print("The deque is not empty") 

Questo stamperà " La deque è vuota " se la deque è vuota. Se non è vuoto, l'output sarà " La deque non è vuota ".

Quando si lavora con Deque come stack, è importante tenere traccia del fatto che lo stack sia vuoto o meno. Se provi a estrarre un elemento da uno stack vuoto, otterrai un IndexError .

Cos'è una Deque ristretta?

Una deque ristretta è una coda a doppia estremità con alcune restrizioni poste sulle operazioni di accodamento dati e pop su entrambe le estremità della deque. Esistono due tipi principali di richieste limitate; Ingresso ristretto deque e uscita ristretto deque

Diamo un'occhiata a loro:

Input Ristretto Deque

Una deque limitata all'input consente di estrarre o eliminare elementi di dati da entrambe le estremità della deque. Tuttavia, è possibile inserire solo elementi di dati da un'estremità della deque.

Questo è molto utile nelle applicazioni con vincoli di memoria. Puoi usarlo per aggiungere elementi di dati in ordine cronologico mantenendo la possibilità di eliminare i dati da qualsiasi estremità della deque.

Uscita Deque ristretta

Una deque limitata all'output consente di inserire dati da entrambe le estremità della deque. Tuttavia, puoi eliminare gli elementi solo da un'estremità della deque chiamata front-end.

Una deque limitata all'output è molto utile nei casi in cui è necessario implementare una struttura di dati FIFO, ma si desidera comunque che la funzionalità accodi i dati da entrambe le estremità.

Concludiamo questo

A questo punto, dovresti avere una buona conoscenza del modulo deque in Python e di come può essere utilizzato per implementare code e stack efficienti.

Le deque sono una struttura dati versatile che offre molti vantaggi rispetto alle liste tradizionali. Questi vantaggi sono evidenti quando si tratta di operazioni di accodamento e pop efficienti in termini di memoria.

Sono anche un'ottima scelta quando è necessario implementare uno stack o una coda a doppia estremità. Alcuni dei principali vantaggi dell'utilizzo di deques includono:

• Efficienti operazioni O(1) append e pop da entrambe le estremità della deque

• Accesso rapido O(1) al primo e all'ultimo elemento della deque

• Supporto integrato per operazioni atomiche thread-safe

• Metodi flessibili per l'inserimento, la rimozione e la rotazione di elementi nella deque

Nel complesso, il modulo deque è uno strumento potente che può aiutarti a scrivere codice Python più efficiente e gestibile. Che tu stia lavorando su un piccolo script o su un progetto su larga scala, vale sicuramente la pena considerare le deques come alternativa alle liste tradizionali o ad altre strutture di dati!

Pronto per saperne di più su Python, dai un'occhiata alla nostra playlist qui sotto