Coda a due estremità in Python

Deque è una generalizzazione delle strutture di stack e coda, inizializzata da sinistra a destra. Utilizza oggetti list per creare una coda a due estremità, offrendo una complessità temporale O(1) per l'espulsione e l'aggiunta.

Deque è una classe della libreria standard, situatacollectionsmodulo.

Per prima cosa, dobbiamo importare il modulo standard delle collection.

import collections

In questa sezione, vedremo alcune funzionalità della classe Deque

Le funzionalità di aggiunta della coda a due estremità

Ci sono due tipi diversi di aggiunta. Ilappend()Il metodo serve per aggiungere un elemento alla destra della coda, ilappendleft()Il metodo serve per aggiungere un elemento alla sinistra della coda.

Esempio di codice

import collections as col
#Inserisci alcuni elementi nella coda all'inizio
my_deque = col.deque('124dfre')
　　　print('Dequeue: ' + str(my_deque))
　　　　　　#inserisci x a destra e B a sinistra
　　　　　　my_deque.append('x')
　　　　　　my_deque.appendleft('B')
　　　print('Coda a due estremità dopo l'aggiunta: ' + str(my_deque))

Risultato di output

Coda a due estremità: deque(['1', '2', '4', 'd', 'f', 'r', 'e'])
Coda a due estremità dopo l'aggiunta: deque(['B', '1', '2', '4', 'd', 'f', 'r', 'e', 'x'])

Funzione di rimozione della coda a due estremità

Come l'aggiunta, ci sono due tipi diversi di funzioni di rimozione. Ilpop()Il metodo viene utilizzato per rimuovere e restituire l'elemento più a destra dalla coda, ilpopleft()Il metodo viene utilizzato per rimuovere e restituire l'elemento più a sinistra dalla coda.

Esempio di codice

import collections as col
#Inserisci alcuni elementi nella coda all'inizio
my_deque = col.deque('124dfre')
　　　print('Dequeue: ' + str(my_deque))
　　　　　　#Elimina l'elemento da destra e sinistra
　　　　　　item = my_deque.pop()
　　　print('Elemento rimosso: ' + str(item))
　　　　　　item = my_deque.popleft()
　　　print('Elemento rimosso: ' + str(item))
print('Coda a due estremità dopo le operazioni di rimozione: ' + str(my_deque))

Risultato di output

Coda a due estremità: deque(['1', '2', '4', 'd', 'f', 'r', 'e'])
Elemento rimosso: e
Elemento rimosso: 1
Coda a due estremità dopo le operazioni di rimozione: deque(['2', '4', 'd', 'f', 'r'])

Funzioni relative agli elementi nella coda a due estremità

Alcune funzioni specifiche della coda a due estremità vengono utilizzate per ottenere informazioni relative agli elementi. Ci sono alcune funzioni, comeindex(),count()Eccetera. Il metodo index viene utilizzato per ottenere l'indice della prima occorrenza dell'elemento. Se non viene passato alcun parametro all'elemento, esso seleziona l'intera lista, e dopo aver specificato una limitazione, verifica l'indice entro quella limitazione. D'altra parte, ilcount()Il metodo calcola la frequenza degli elementi nella coda a due estremità.

Esempio di codice

import collections as col
#Inserisci alcuni elementi nella coda all'inizio
my_deque = col.deque('AABCDDEFD')
　　　print('Dequeue: ' + str(my_deque))
　　　　　　#Trova l'indice di D
　　　print('Indice di D: ' + str(my_deque.index('D')))
print('Indice di D nel range 5 a 8 è: ' + str(my_deque.index('D', 5, 8)))
#Calcolare il numero di occorrenze
　　　print('Occorrenze di A: ' + str(my_deque.count('A')))
print('Occorrenze di D: ' + str(my_deque.count('D')))

Risultato di output

Dequeue: deque(['A', 'A', 'B', 'C', 'D', 'D', 'E', 'F', 'D'])
Indice di D: 4
Indice di D nel range 5 a 8 è: 5
Occorrenze di A: 2
Occorrenze di D: 3

Nella Dequeinsert()Eremove()Il metodo

Abbiamo visto i funzioni append e pop nella Deque, rispettivamente per l'inserimento e la rimozione di elementi. Ci sono anche due metodi relativi all'inserimento e alla rimozione. Ilinsert()Il metodo viene utilizzato per inserire un numero. In questo caso, possiamo fornire l'indice di inserimento. Pertanto, possiamo inserire il progetto nella posizione specificata. E ilremove()Il metodo viene utilizzato per eliminare la prima occorrenza di un elemento.

Esempio di codice

import collections as col
#Inserisci alcuni elementi nella coda all'inizio
my_deque = col.deque('AABCDDEFD')
print('Dequeue: ' + str(my_deque))
#Inserisci la lettera G e H nelle posizioni 5, 7 rispettivamente
my_deque.insert(5, 'G')
my_deque.insert(7, 'H')
print('Deque dopo l'inserimento: ' + str(my_deque))
#Elimina la prima occorrenza della lettera D
my_deque.remove('D')
print('Deque dopo la rimozione: ' + str(my_deque))

Risultato di output

Dequeue: deque(['A', 'A', 'B', 'C', 'D', 'D', 'E', 'F', 'D'])
Deque dopo l'inserimento: deque(['A', 'A', 'B', 'C', 'D', 'G', 'D', 'H', 'E', 'F', 'D'])
Deque dopo la rimozione: deque(['A', 'A', 'B', 'C', 'G', 'D', 'H', 'E', 'F', 'D'])

Funzione di estensione nella Deque

La funzione di estensione viene utilizzata per aggiungere più elementi a una Deque. Possiamo utilizzare liste, tuple e altri insiemi per fornire più valori. Ci sono due funzioni di estensione. Ilextend()Il metodo viene utilizzato per aggiungere elementi alla destra, simile a una ripetizioneappend()Il metodo. E ilextendleft()Il metodo viene utilizzato per aggiungere elementi alla sinistra, simile a una ripetizioneappendleft()Metodo.

Esempio di codice

import collections as col
#Inserisci alcuni elementi nella coda all'inizio
my_deque = col.deque('AABCDDEFD')
print('Dequeue: ' + str(my_deque))
#Estendi aggiungendo 1, 3, 5, 7 alla destra e x, y, z alla sinistra
my_deque.extend([1, 3, 5, 7])
my_deque.extendleft(['x', 'y', 'z'])
print('Deque dopo l'estensione: ' + str(my_deque))

Risultato di output

Dequeue: deque(['A', 'A', 'B', 'C', 'D', 'D', 'E', 'F', 'D'])
Deque dopo l'estensione: deque(['z', 'y', 'x', 'A', 'A', 'B', 'C', 'D', 'D', 'E', 'F', 'D', 1, 3, 5, 7])

Le funzioni di inversione e rotazione della coda a due estremità

Possiamo usare questoreverse()Il metodo inverso cambia l'ordine della coda. C'è un altro metodorotate()Utilizzando il metodo rotate, la coda a due estremità può essere ruotata con un numero specificato come parametro. Se il parametro è positivo, ruota a destra, se è negativo, ruota a sinistra.

Esempio di codice

import collections as col
#Inserisci alcuni elementi nella coda all'inizio
my_deque = col.deque('AABCDDEFD')
print('Dequeue: ' + str(my_deque))
my_deque.reverse()
print('Deque dopo il rovesciamento:' + str(my_deque))
#Rotta a destra, 3 elementi
my_deque.rotate(3)
print('Deque dopo la rotazione:' + str(my_deque))

Risultato di output

Dequeue: deque(['A', 'A', 'B', 'C', 'D', 'D', 'E', 'F', 'D'])
Deque dopo il rovesciamento: deque(['D', 'F', 'E', 'D', 'D', 'C', 'B', 'A', 'A'])
Deque dopo la rotazione: deque(['B', 'A', 'A', 'D', 'F', 'E', 'D', 'D', 'C'])