Метка: очередь

​​collections.deque – очередь Python

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) – удалить и вернуть элемент с начала.

Схема методов deque

Метод 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 👈 

Куча и очередь с приоритетом

Порядок обхода кучи

Очередь с приоритетом – это такая коллекция, которая поддерживает обязательно две следующие операции: вставка элемента с некоторым приоритетом (это может быть число или другой сравнимый объект) и извлечение элемента с наибольшим (или наименьшим приоритетом).