deque — Cola doblemente terminada

Una cola doblemente terminada, o deque, admite agregar y eliminar elementos de cualquier extremo de la cola. Las pilas y colas más comunes son formas degeneradas de deques, donde las entradas y salidas están restringida a un solo extremo.

collections_deque.py
import collections

d = collections.deque('abcdefg')
print('Deque:', d)
print('Length:', len(d))
print('Left end:', d[0])
print('Right end:', d[-1])

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

Como las deques son un tipo de contenedor de secuencia, admiten algunas de las mismas operaciones que list, como examinar los contenidos con __getitem__(), determinando la longitud y eliminando elementos desde el medio de la cola al hacer coincidir la identidad.

$ python3 collections_deque.py

Deque: deque(['a', 'b', 'c', 'd', 'e', 'f', 'g'])
Length: 7
Left end: a
Right end: g
remove(c): deque(['a', 'b', 'd', 'e', 'f', 'g'])

Populando

Se puede llenar una deque desde cualquier extremo, denominado «izquierda» y «derecha» en la implementación de Python.

collections_deque_populating.py
import collections

# Add to the right
d1 = collections.deque()
d1.extend('abcdefg')
print('extend    :', d1)
d1.append('h')
print('append    :', d1)

# Add to the left
d2 = collections.deque()
d2.extendleft(range(6))
print('extendleft:', d2)
d2.appendleft(6)
print('appendleft:', d2)

La función extendleft() itera sobre su entrada y realiza el equivalente de un appendleft() para cada elemento. El resultado final es que la deque contiene la secuencia de entrada en orden 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])

Consumiendo

Del mismo modo, los elementos del deque pueden ser consumidos desde ambos extremos o cualquiera de los extremos, dependiendo del algoritmo que se aplica.

collections_deque_consuming.py
import collections

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

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

Utiliza pop() para eliminar un elemento del extremo «derecho» de deque y popleft() para tomar un elemento del extremo «izquierdo».

$ python3 collections_deque_consuming.py

From the right:
gfedcba

From the left:
012345

Como las deques son seguras para hilos, el contenido puede incluso consumirse desde ambos extremos al mismo tiempo desde hilos separados.

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} done'.format(direction))
    return


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

left.start()
right.start()

left.join()
right.join()

Los hilos en este ejemplo se alternan entre cada extremo, eliminando elementos hasta que deque esté vacía.

 $ python3 collections_deque_both_ends.py

 Left: 0
Right: 4
Right: 3
 Left: 1
Right: 2
 Left done
Right done

Rotando

Otro aspecto útil de la deque es la capacidad de rotarla en cualquier dirección, como para omitir algunos elementos.

collections_deque_rotate.py
import collections

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

d = collections.deque(range(10))
d.rotate(2)
print('Right rotation:', d)

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

Rotando la deque a la derecha (usando una rotación positiva) toma elementos del extremo derecho y los mueve hacia la extremos izquierdo. Rotando a la izquierda (con un valor negativo) toma elementos del extremo izquierdo y los mueve al extremo derecho. Puede ayudar a visualizarlos elementos en la deque están grabados a lo largo del borde de un dial.

$ python3 collections_deque_rotate.py

Normal        : deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
Right rotation: deque([8, 9, 0, 1, 2, 3, 4, 5, 6, 7])
Left rotation : deque([2, 3, 4, 5, 6, 7, 8, 9, 0, 1])

Limitando el tamaño de la cola

Una instancia de deque se puede configurar con una longitud máxima, por lo que nunca crece más allá de ese tamaño. Cuando la cola llega a la longitud especificada, los elementos existentes se descartan a medida que se crean nuevos. Este comportamiento es útil para encontrar los últimos n elementos en un corriente de longitud indeterminada.

collections_deque_maxlen.py
import collections
import random

# Set the random seed so we see the same output each time
# the script is run.
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 longitud de la deque se mantiene sin importar a qué final son añadidos los elementos.

$ 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)

Ver también