Автор оригинала: 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 в алгоритмах из документации стандартной библиотеки.