все Python 3collectionsпонятие

collections.deque

deque

Двусторонняя очередь. O(1) вставка/удаление с обоих концов. Поддерживает maxlen (скользящее окно).

Синтаксис

from collections import deque
deque(iterable=(), maxlen=None)
.appendleft(x) / .popleft() / .rotate(n)

Быстрые концы оплачены медленной серединой: обращение по индексу где-то в центре стоит O(n), а срезы deque вообще не поддерживает — если нужен произвольный доступ, берите list. Когда задан maxlen, очередь при переполнении молча выбрасывает элемент с противоположного конца, и это не ошибка, а весь смысл скользящего окна. Отдельный бонус — append и popleft атомарны, поэтому deque годится как очередь между потоками без блокировок.

Примеры

from collections import deque
d = deque([1, 2, 3])
d.append(4)
d.appendleft(0)
print(d)  # → deque([0, 1, 2, 3, 4])
print(d.pop(), d.popleft())  # → 4 0
print(d)  # → deque([1, 2, 3])

from collections import deque
d = deque([1, 2, 3, 4, 5])
d.rotate(2)
print(d)  # → deque([4, 5, 1, 2, 3])
d.rotate(-1)
print(d)  # → deque([5, 1, 2, 3, 4])

# maxlen — скользящее окно
from collections import deque
last3 = deque(maxlen=3)
for x in range(6):
    last3.append(x)
print(list(last3))  # → [3, 4, 5]

# Очередь (FIFO) и стек (LIFO)
from collections import deque
queue = deque(['a', 'b', 'c'])
print(queue.popleft())  # → a
stack = deque([1, 2, 3])
print(stack.pop())  # → 3

from collections import deque
d = deque([1, 2, 3])
d.extend([4, 5])
d.extendleft([0, -1])
print(d)  # → deque([-1, 0, 1, 2, 3, 4, 5]) — extendleft разворачивает порядок

См. также

Открыть в полном глоссарииdocs.python.orgСообщить о неточности