Deque: что это такое и как использовать в своих проектах
Deque (Double-ended queue) - это структура данных, которая представляет собой коллекцию элементов, аналогичную очереди и стеку. Элементы в deque хранятся в виде последовательности и могут быть добавлены и удалены с двух концов.
Для работы с deque в Python используется модуль collections. В данном модуле доступен класс deque, который предоставляет реализацию deque на Python.
Пример создания объекта deque:
python
from collections import deque
d = deque()
Методы добавления элементов:
- append(x) - добавляет элемент x в конец deque
- appendleft(x) - добавляет элемент x в начало deque
- extend(iterable) - добавляет элементы из iterable в конец deque
- extendleft(iterable) - добавляет элементы из iterable в начало deque (обратный порядок)
python
d = deque()
d.append(1) # [1]
d.appendleft(2) # [2, 1]
d.extend([3, 4]) # [2, 1, 3, 4]
d.extendleft([5, 6])# [6, 5, 2, 1, 3, 4]
Методы удаления элементов:
- pop() - удаляет и возвращает последний элемент в deque
- popleft() - удаляет и возвращает первый элемент в deque
- remove(x) - удаляет первый встреченный элемент x
python
d = deque([1, 2, 3, 4, 5])
d.pop() # 5, d=[1, 2, 3, 4]
d.popleft() # 1, d=[2, 3, 4]
d.remove(3) # d=[2, 4]
Некоторые методы доступа к элементам:
- count(x) - возвращает количество вхождений элемента x в deque
- index(x) - возвращает индекс первого вхождение элемента x в deque
python
d = deque([1, 2, 3, 4, 2, 5])
d.count(2) # 2
d.index(2) # 1
Deque можно использовать для реализации алгоритмов, которые требуют быстрого доступа к элементам в начале и конце структуры данных, например, алгоритма BFS (поиск в ширину) в графах. Также deque может быть полезен в решении задач, где необходимы операции добавления и удаления элементов в начале или конце последовательности.