Урок 14: Двусторонняя очередь (deque) в Python.

Добро пожаловать на четырнадцатый урок нашего курса по программированию на Python! В предыдущем уроке мы познакомились с множествами (set) и узнали, как эффективно хранить и обрабатывать уникальные элементы. Сегодня мы рассмотрим ещё одну важную структуру данных — двустороннюю очередь (deque) из модуля collections. Она позволит вам эффективно добавлять и удалять элементы как с начала, так и с конца, а также упростит решение множества прикладных задач.

В данную статью добавлены ссылки на GitHub в каждом примере. Также общая ссылка на GitHub для данного урока:

Что такое deque?

Deque (Double-Ended Queue) — это двусторонняя очередь, реализованная в модуле collections. В отличие от обычного списка (list), где операции вставки и удаления элементов в начале списка могут приводить к значительным затратам ресурсов, deque оптимизирована для быстрого добавления и изъятия элементов как в начале, так и в конце очереди. Это делает deque незаменимым в задачах, требующих эффективной обработки данных с обоих концов.

Создание и инициализация.

Подключение модуля collections:

Чтобы использовать deque, необходимо импортировать его из модуля collections:

from collections import deque

Создание пустой двусторонней очереди:

Пример создания пустой deque.

from collections import deque

d = deque()
print(d) # deque([])

Создание deque из итерируемого объекта:

При создании deque вы можете сразу проинициализировать её элементами из любого итерируемого объекта (список, кортеж и т.д.):

Пример создания deque из list.

from collections import deque

numbers = [1, 2, 3, 4, 5]
d = deque(numbers)
print(d) # deque([1, 2, 3, 4, 5])

Основные операции deque.

Добавление элементов:

1. append(x): Добавляет элемент x в конец двусторонней очереди.
2. appendleft(x): Добавляет элемент x в начало двусторонней очереди.

Пример использования append и appendleft.

from collections import deque

d = deque([1, 2, 3])

#append(x)
d.append(4)
print(d) # deque([1, 2, 3, 4])

#appendleft(x)
d.appendleft(0)
print(d) # deque([0, 1, 2, 3, 4])

Изъятие элементов:

1. pop(): Удаляет и возвращает элемент с конца очереди.
2. popleft(): Удаляет и возвращает элемент с начала очереди.

Пример использования pop и popleft.

from collections import deque

d = deque([0, 1, 2, 3, 4])

#pop()
last = d.pop()
print(last) # 4
print(d) # deque([0, 1, 2, 3])

#popleft()
first = d.popleft()
print(first) # 0
print(d) # deque([1, 2, 3])

Доступ к элементам по индексу:

Хотя deque поддерживает индексацию, такие операции (например, d[i]) могут приводить к значительным затратам времени, поскольку deque не оптимизирована для произвольного доступа к элементам. Если вам важен быстрый доступ по индексу, лучше использовать список (list). Если же нужно эффективно добавлять и удалять элементы с обоих концов, deque будет отличным выбором.

Дополнительные методы deque.

extend() и extendleft():

• extend(iterable): Добавляет элементы из iterable в конец deque.
• extendleft(iterable): Добавляет элементы из iterable в начало deque.
  Обратите внимание, что элементы будут добавляться по одному, но в порядке, обратном порядку итерируемого объекта.

Пример использования extend и extendleft.

from collections import deque

d = deque([1, 2, 3])

#extend(iterable)
d.extend([4, 5])
print(d) # deque([1, 2, 3, 4, 5])

#extendleft(iterable)
d.extendleft([0, -1])
print(d) # deque([-1, 0, 1, 2, 3, 4, 5])

rotate():

Метод rotate(n) сдвигает элементы deque на n позиций вправо (если n > 0) или влево (если n < 0).

Пример использования rotate.

from collections import deque

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

reverse():

Метод reverse() разворачивает deque на месте (аналогично list.reverse()) и возвращает None.

Пример использования reverse.

from collections import deque

d = deque([1, 2, 3, 4, 5])
d.reverse()
print(d) # deque([5, 4, 3, 2, 1])

Практические примеры.

Пример 1. Реализация очереди задач.

Пример реализации очереди задач.

from collections import deque

tasks = deque()

# Добавляем задачи в очередь tasks.append("task1")
tasks.append("task2")
tasks.append("task3")

# Обработка задач в порядке FIFO while tasks:
current_task = tasks.popleft()
print(f"Выполняется: {current_task}")

Пример 2. Буфер ограниченного размера.

С помощью deque можно организовать кольцевой буфер, если задать maxlen — максимальную длину deque. При достижении максимальной длины старые элементы будут удаляться.

from collections import deque

buffer = deque(maxlen=3)
buffer.append(1)
buffer.append(2)
buffer.append(3)
print(buffer) # deque([1, 2, 3], maxlen=3)
buffer.append(4)
print(buffer) # deque([2, 3, 4], maxlen=3) - элемент 1 был удалён

Пример 3. Лабиринт и BFS.

Алгоритм поиска в ширину (BFS) часто реализуют с помощью очереди, так как нужно последовательно обрабатывать вершины в порядке их обнаружения.

Пример реализации алгоритма поиска в ширину.

from collections import deque

def bfs(start, graph):
visited = set()
queue = deque([start])
visited.add(start)

while queue:
vertex = queue.popleft()
print(vertex, end=" ")

for neighbor in graph[vertex]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)

# Пример графа в виде словаря
graph = {
"A": ["B", "C"],
"B": ["A", "D", "E"],
"C": ["A", "F"],
"D": ["B"],
"E": ["B", "F"],
"F": ["C", "E"]
}

bfs("A", graph) # A B C D E F

Заключение четырнадцатого урока.

Сегодня мы:

1. Познакомились с deque (двусторонней очередью) из модуля collections.
2. Узнали о ключевых операциях append(), appendleft(), pop(), popleft(), а также о методах rotate() и reverse().
3. Рассмотрели, как эффективно использовать deque для различных задач: реализация очередей, стеков, кольцевых буферов.
4. Увидели, что deque позволяет работать с элементами с обоих концов за амортизированное O(1)O(1)O(1) время.

deque — мощная структура данных, которая отлично подходит, когда требуется эффективное добавление и удаление элементов в начале и конце последовательности. Понимание её возможностей даёт дополнительную гибкость при решении многих алгоритмических задач.

Домашняя работа.

Задание 1: Стек на базе deque.

1. Создайте пустой deque, который будет имитировать работу стека (LIFO).
2. Добавьте несколько элементов с помощью append().
3. Извлеките все элементы с помощью pop() и выведите их в порядке извлечения.

Задание 2: Кольцевой буфер.

1. Создайте deque с maxlen = 5.
2. Считайте в цикле 7 чисел (например, введённых пользователем или просто заданных в коде) и добавляйте их в deque.
3. После каждого добавления числа выводите текущее состояние deque.

Задание 3*: Сдвиг очереди задач.

Реализуйте программу, которая:

1. Поддерживает очередь задач (строки) с помощью deque.
2. Реализует команду rotate(n), которая сдвигает очередь на n позиций вправо (при n > 0) или влево (при n < 0).
3. Позволяет добавлять и извлекать задачи, выводя текущее состояние очереди после каждой операции.

Вопросы для самопроверки.

1. Что такое deque и чем он отличается от списка?
2. Как добавить элемент в начало и конец deque?
3. Для чего нужен параметр maxlen при создании deque?
4. Какие преимущества даёт deque при реализации очереди или стека?
5. Чем метод rotate() отличается от обычной сортировки или разворота?

Свои домашние работы отправляйте на почтовый ящик homework@kuzinobit.com.

Поздравляю с успешным освоением четырнадцатого урока! Теперь вы умеете использовать двустороннюю очередь для более эффективного управления элементами в ваших программах. В следующих уроках мы продолжим знакомиться с новыми возможностями Python, которые помогут вам ещё глубже погрузиться в мир программирования и создавать более сложные и гибкие решения.

Друзья, ставьте свои лайки и подписывайтесь на канал. Дальше будет только интереснее! До новых встреч!