Использование deque в Python

Обзор абстрактного типа данных двухсторонней очереди, которая служит в качестве коллекции элементов и реализована с помощью модуля deque. В окружении программистов обычно называют «стеком».

Введение

Стек — это структура данных, в которой элементы хранится в порядке LIFO (Last-In/First-Out). В стек добавляются и удаляются элементы только с конца. Операции вставки и удаления часто называют push и pop.

Применение

• Команда отменить используемая в текстовых редактора и IDE использует стеки для возврата к предыдущему состоянию.
• Если вы вызываете функцию внутри другой функции, то управление происходит с помощью стеков.
• Кнопка назад в веб-браузере запоминает посещаемые страницы в стеке.

Реализация

Самый простой вариант реализовать двухстороннюю очередь это написать класс содержащий методы вставки и удаления элементов. В качестве хранилища можно использовать список, но такой вариант затратный для памяти, на каждое изменение списка Python будет выделять отдельную копию измененного списка.

Чтобы избежать этих проблем в модуле коллекций реализован абстрактный тип данных deque.

Использование

Двусторонняя очередь или deque, имеет возможность добавлять и удалять элементы с любого из концов.

Модуль deque является частью библиотеки collections. В нем есть методы добавления и удаления элементов, которые могут быть вызваны напрямую с помощью аргументов. В нижеприведенной программе мы импортируем модуль коллекций и объявим deque. Без необходимости какого-либо класса мы используем встроенную реализацию этих методов напрямую.

Загрузим модуль deque

from collections import deque

data = deque()

Добавим в очередь элементы

data.append('Красный')
data.append('Синий')
data.append('Черный')
data.append('Белый')

Выведем на печать содержимое нашей очереди

print(data)

deque(['Красный', 'Синий', 'Черный', 'Белый'])

Чтобы получить последний элемент из очереди используем метод pop()

last = data.pop()
print(last)

Белый

Запросив последний элемент из очереди общее количество элементов сократилось на единицу, давайте посмотрим что осталось в очереди

print(data)

deque(['Красный', 'Синий', 'Черный'])

Доступные методы deque

Ниже я приведу список доступных методов для работы с двухсторонней очередью.

• append(z) — добавить элемент z в правую часть
• appendleft(z) — добавить элемент z в левую часть
• clear() — удалить все элементы из очереди
• copy() — создать копию очереди
• count(z) — посчитать количество элементов равных z
• extend(iter) — добавить элементы в правую часть из итерируемого объекта
• extendleft(z) — добавить элементы в левую часть из итерируемого объекта
• index(z) — вернуть индекс первого элемента или вызвать ValueError если ничего не найдено
• insert(i, z) — вставить элемент z в положение i
• pop() — удалить и вернуть элемент
• popleft() — удалить и вернуть элемент из левой части
• remove(z) — удалить первый найденный элемент z
• reverse() — перевернуть очередь

Заключение

Самое подробное и актуальное руководство по двухсторонней очереди можно найти в официальной документации python -> https://docs.python.org/3/library/collections.html#collections.deque

Сегодня мы рассмотрели как используется и для чего нужна эта структура данных в Python. Если у вас есть дополнительные вопросы, не стесняйтесь задавать их в комментариях.