deque – коллекция двухсторонней очереди, которая похожа на список, за исключением того, что добавлять и удалять элементы можно либо в начало (слева), либо в конец (справа). Можно использовать и как стек. Реализована через двусвязный список. Благодаря этому, операции добавления или удаления элемента с любого конца deque имеют сложность O(1). Доступ к произольному элементу – O(n).
Создание:
from collections import deque d1 = deque() # пустая d2 = deque([1, 2, 3]) # из любого iterable d3 = deque(maxlen=5) # максимальная длина
Методы
Метод append(x) – добавить элемент в конец.
Метод appendleft(x) – добавить элемент в начало.
Метод pop(x) – удалить и вернуть элемент с конца.
Метод popleft(x) – удалить и вернуть элемент с начала.
Метод clear() – очистить очередь.
Метод reverse() – развернуть очередь наоборот:
d = deque([1, 2, 3]) d.reverse() print(d) # deque([3, 2, 1])
Метод rotate(n) – последовательно переносит n элементов с конца в начало (если n отрицательно, то из начала в конец):
d = deque(range(8)) # deque([0, 1, 2, 3, 4, 5, 6, 7]) d.rotate(2) # deque([6, 7, 0, 1, 2, 3, 4, 5]) d.rotate(-1) # deque([7, 0, 1, 2, 3, 4, 5, 6])
Метод extend(iterable) – добавляет в конец все элементы iterable.
Метод extendleft(iterable) – добавляет в начало все элементы iterable (начиная с последнего элемента iterable):
d = deque() d.extend([1, 2, 3]) d.extendleft([10, 20, 30]) print(d) # deque([30, 20, 10, 1, 2, 3])
Метод insert(index, x) – вставить элемент x в индекс i (медленно).
d[index] – доступ к элементу по индексу (медленно).
len(d) – число элементов в очереди (тоже работает медленно).
Метод remove(value) – удаляет первое вхождение значения value (слева направо). Остальные элементы не трогаются.
Метод count(value) – количество элементов со значением value в очереди.
Максимальная длина
Если при создание deque задано maxlen, то длина очереди будет ограничена. Это значит, что если мы попытаемся вставить элемент в очередь длины (maxlen), то элемент с противоположного конца будет вытеснен, и длина очереди не изменится:
# максимальная длина 5 d = deque(maxlen=5) d.extend(range(10)) # deque([5, 6, 7, 8, 9], maxlen=5) # затерлись первые 5 элементов d.appendleft(100) # слева вставим 100, девятка вылетит справа # deque([100, 5, 6, 7, 8], maxlen=5) d.append(200) # справа вставим 200, сотня вылетит слева # deque([5, 6, 7, 8, 200], maxlen=5)
Резюме: deque хороша, когда частый доступ осуществляется только к концам коллекции. Подходит для очередей (например, задач), стэка, алгоритма round-robin, подсчета бегущих средних и прочего. А если нужен доступ к элементам по индексу – лучше брать list.
Специально для канала @pyway. Подписывайтесь на мой канал в Телеграм @pyway 👈