Una coda a doppia entrata (deque) supporta l'inserimento e la rimozione di elementi da ambo le estremità. I più comuni stack e code sono forme degenerate di deque, laddove le entrate e le uscite sono limitate ad un singolo estremo.

# collections_deque.py

import collections

d = collections.deque('abcdefg')
print ('Deque:', d)
print ('Lunghezza:', len(d))
print ('Estremo sx:', d[0])
print ('Estremo dx:', d[-1])

d.remove('c')
print ('rimuovo(c):', d)

Visto che le deque sono un tipo di contenitore di sequenze, supportano alcune delle operazioni che supportano le liste, come ad esempio l'esaminare i contenuti con __getitem__(), il determinare la lunghezza, e la rimozione di elementi all'interno confrontandone l'identità .

$ python3 collections_deque.py

Deque: deque(['a', 'b', 'c', 'd', 'e', 'f', 'g'])
Lunghezza: 7
Estremo sx: a
Estremo dx: g
rimuovo(c): deque(['a', 'b', 'd', 'e', 'f', 'g'])

Inserire Elementi

Una deque può essere popolare da entrambi gli estremi, chiamati "left" e "right" rispettivamente per sinistra e destra nell'implementazione Python.

# collections_deque_populating.py

import collections

# Si aggiunge da destra
d1 = collections.deque()
d1.extend('abcdefg')
print('extend    :', d1)
d1.append('h')
print('append    :', d1)

# Si aggiunge da sinistra
d2 = collections.deque()
d2.extendleft(range(6))
print('extendleft:', d2)
d2.appendleft(6)
print('appendleft:', d2)

La funzione extendleft() itera attraverso gli elementi in entrata ed esegue l'equivalente di appendleft() per ogni elemento. Ne risulta che la deque contiene la sequenza di input in ordine inverso.

$ python3 collections_deque_populating.py

extend    : deque(['a', 'b', 'c', 'd', 'e', 'f', 'g'])
append    : deque(['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'])
extendleft: deque([5, 4, 3, 2, 1, 0])
appendleft: deque([6, 5, 4, 3, 2, 1, 0])

Consumare gli Elementi

Gli elementi della deque possono essere consumati da entrambi i lati, a seconda dell'algoritmo che viene applicato.

# collections_deque_consuming.py

import collections

print('Da destra:')
d = collections.deque('abcdefg')
while True:
    try:
        print(d.pop(), end='')
    except IndexError:
        break
print

print('\nDa sinistra:')
d = collections.deque(range(6))
while True:
    try:
        print(d.popleft(), end='')
    except IndexError:
        break
print

Si utilizza pop() per rimuovere un elemento dall'estremità destra della coda, popleft() per toglierlo dall'estremità sinistra.

$ python3 collections_deque_consuming.py

Da destra:
gfedcba
Da sinistra:
012345

Visto che le deque sono thread-safe gli elementi possono essere consumati da entrambi gli estremi allo stesso tempo da thread separati.

# collections_deque_both_ends.py

import collections
import threading
import time

candle = collections.deque(range(5))


def burn(direction, nextSource):
    while True:
        try:
            next = nextSource()
        except IndexError:
            break
        else:
            print('{:>8}: {}'.format(direction, next))
            time.sleep(0.1)
    print('{:>8} finito'.format(direction))
    return

left = threading.Thread(target=burn,
                        args=('Sinistra', candle.popleft))
right = threading.Thread(target=burn,
                         args=('Destra', candle.pop))

left.start()
right.start()

left.join()
right.join()

I thread in questo esempio si alternano tra gli estremi, eliminando elementi fino allo svuotamento della deque.

$ python3 collections_deque_both_ends.py

Sinistra: 0
  Destra: 4
Sinistra: 1
  Destra: 3
Sinistra: 2
  Destra finito
Sinistra finito

Rotazione

Un'altra utile capacità della deque è quella di ruotare in ciascuna direzione, per saltare alcuni elementi.

# collections_deque_rotate.py

import collections

d = collections.deque(range(10))
print('Normale       :', d)

d = collections.deque(range(10))
d.rotate(2)
print('Rotazione destra:', d)

d = collections.deque(range(10))
d.rotate(-2)
print('Rotazione sinistra:', d)

La rotazione verso destra della deque (rotazione con valore positivo) prende gli elementi dall'estremità destra e li sposta verso quella sinistra. La rotazione verso sinistra (rotazione con valore negativo) prende gli elementi dall'estremità sinistra e li sposta verso quella destra. Può essere di aiuto visualizzare gli elementi in una deque come la disposizione dei numeri nel disco rotatorio di un vecchio telefono.

$ python3 collections_deque_rotate.py

Normale       : deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
Rotazione destra: deque([8, 9, 0, 1, 2, 3, 4, 5, 6, 7])
Rotazione sinistra: deque([2, 3, 4, 5, 6, 7, 8, 9, 0, 1])

Limitare la Dimensione della Coda

Una istanza di deque può essere configurata con una lunghezza massima, in modo che non cresca mai oltre il limite prestabilito. Quando detto limite viene raggiunto, gli elementi esistenti vengono scaricati ed i nuovi aggiunti. Questo comportamento è utile per trova gli ultimi n elementi in un flusso di lunghezza non determinata.

# collections_deque_maxlen.py

import collections
import random

# Imposta il parametro di random seed in modo da vedere lo stesso
# risultato ogni volta che viene eseguito lo script
random.seed(1)

d1 = collections.deque(maxlen=3)
d2 = collections.deque(maxlen=3)

for i in range(5):
    n = random.randint(0, 100)
    print('n =', n)
    d1.append(n)
    d2.appendleft(n)
    print('D1:', d1)
    print('D2:', d2)

La lunghezza della deque viene mantenuta a prescindere da quale estremità vengono aggiunti gli elementi.

$ python3 collections_deque_maxlen.py

n = 17
D1: deque([17], maxlen=3)
D2: deque([17], maxlen=3)
n = 72
D1: deque([17, 72], maxlen=3)
D2: deque([72, 17], maxlen=3)
n = 97
D1: deque([17, 72, 97], maxlen=3)
D2: deque([97, 72, 17], maxlen=3)
n = 8
D1: deque([72, 97, 8], maxlen=3)
D2: deque([8, 97, 72], maxlen=3)
n = 32
D1: deque([97, 8, 32], maxlen=3)
D2: deque([32, 8, 97], maxlen=3)