all Python 3collectionsterm

collections.deque

deque

A double-ended queue. O(1) insertion and removal at both ends. Supports maxlen (a sliding window).

Syntax

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

Fast ends come at the cost of a slow middle: indexing somewhere in the center is O(n), and deque supports no slicing at all — if you need random access, use a list. With maxlen set, a full deque silently discards an item from the opposite end; that is not a bug but the whole point of a sliding window. A bonus: append and popleft are atomic, so a deque works as a lock-free queue between threads.

Examples

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 разворачивает порядок

collections.deque

Syntax

Examples

See also