deque - Двусторонняя очередь

Автор оригинала: Doug Hellmann.

Двусторонняя очередь, или deque , поддерживает добавление и удаление элементов с любого конца очереди. Наиболее часто используемые стеки и очереди представляют собой вырожденные формы двухсторонних дек, в которых входы и выходы ограничены одним концом.

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)

Поскольку deques являются типом контейнера последовательности, они поддерживают некоторые из тех же операций, что и list , например, проверка содержимого с помощью __getitem __ () , определение длины и удаление элементов из середина очереди по соответствию личности.

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

Заполнение

Двусторонняя очередь может быть заполнена с любого конца, называемого «левым» и «правым» в реализации 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)

Функция extendleft () выполняет итерацию по входу и выполняет эквивалент appendleft () для каждого элемента. Конечным результатом является то, что deque содержит входную последовательность в обратном порядке.

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

Потребление

Точно так же элементы deque могут использоваться с обоих концов или с любого конца, в зависимости от применяемого алгоритма.

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

Используйте pop () , чтобы удалить элемент с «правого» конца deque и popleft () , чтобы взять элемент с «левого» ” конец.

$ python3 collections_deque_consuming.py

From the right:
gfedcba

From the left:
012345

Поскольку deques являются потокобезопасными, их содержимое можно использовать с обоих концов одновременно из отдельных потоков.

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(targetburn,
                        args('Left', candle.popleft))
right  threading.Thread(targetburn,
                         args('Right', candle.pop))

left.start()
right.start()

left.join()
right.join()

В этом примере потоки чередуются с каждого конца, удаляя элементы, пока deque не станет пустым.

$ python3 collections_deque_both_ends.py

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

Вращающийся

Еще один полезный аспект deque – возможность вращать его в любом направлении, чтобы пропускать некоторые элементы.

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)

При повороте deque вправо (с использованием положительного поворота) элементы перемещаются с правого конца в левый. Вращение влево (с отрицательным значением) берет элементы с левого края и перемещает их в правый конец. Это может помочь визуализировать предметы в деке, выгравированные по краю циферблата.

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

Ограничение размера очереди

Экземпляр deque можно настроить с максимальной длиной, чтобы он никогда не превышал этот размер. Когда очередь достигает указанной длины, существующие элементы отбрасываются по мере добавления новых. Это поведение полезно для поиска последних n элементов в потоке неопределенной длины.

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(maxlen3)
d2  collections.deque(maxlen3)

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)

Длина двухсторонней очереди сохраняется независимо от того, в какой конец добавляются элементы.

$ python3 collections_deque_maxlen.py

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

Смотрите также

Википедия: Deque – обсуждение структуры данных deque.
Deque Recipes – примеры использования deques в алгоритмах из документации стандартной библиотеки.