Первоначально опубликовано 6 августа 2022 года на сайте https://rivea0.github.io/blog.
Два абстрактных типа данных, с которыми вы, скорее всего, уже сталкивались, — это стеки и очереди. Важным аспектом является то, что каждый из них имеет различные принципы поведения при вставке и удалении элементов — LIFO (last in, first out) для стеков, FIFO (first in, first out) для очередей. При использовании стека последний вставленный элемент первым выходит, поэтому мы вставляем и вынимаем элементы с одного конца стека. В очереди первый вставленный элемент будет удален первым, подобно очереди в реальной жизни, поэтому операции enqueue и dequeue выполняются с противоположных концов очереди.
При использовании «двусторонней очереди», или deque (произносится как «колода»), мы можем зачислять и отчислять, а также выталкивать и выгружать элементы с обоих концов в любое время. Реализованная как двусвязный список, операции вставки и удаления занимают постоянное время O(1). Это еще одна причина, по которой deque отлично подходит — вы можете представить, что для той же цели мы можем использовать список Python list, но в этом случае, если мы хотим вставлять и удалять с начала (скажем, с левого конца), операция займет O(n) времени, что, ну, не очень хорошо.
Давайте посмотрим на это. Используя список, вы могли видеть стек, реализованный таким образом*:
class Stack:
"""Stack implementation as a list."""
def __init__(self):
"""Create new stack."""
self._items = []
def is_empty(self):
"""Check if the stack is empty."""
return not bool(self._items)
def push(self, item):
"""Add an item to the stack."""
self._items.append(item)
def pop(self):
"""Remove an item from the stack."""
return self._items.pop()
def peek(self):
"""Get the value of the top item in the stack."""
return self._items[-1]
def size(self):
"""Get the number of items in the stack."""
return len(self._items)
И, например, очередь:
class Queue:
"""Queue implementation as a list."""
def __init__(self):
"""Create new queue."""
self._items = []
def is_empty(self):
"""Check if the queue is empty."""
return not bool(self._items)
def enqueue(self, item):
"""Add an item to the queue."""
self._items.insert(0, item)
def dequeue(self):
"""Remove an item from the queue."""
return self._items.pop()
def size(self):
"""Get the number of items in the queue."""
return len(self._items)
Поскольку мы хотим использовать здесь deque вместо списка, давайте рассмотрим это на примере.
Мы можем инициализировать объект deque, передав в качестве аргумента итерабельную переменную. Он находится в модуле collections, поэтому мы также должны его импортировать:
from collections import deque
d = deque([7, 3, 0, 1])
print(d) # deque([7, 3, 0, 1])
empty_d = deque()
print(empty_d) # deque([])
Также помните, что строки — это последовательности, в таком случае наш deque будет выглядеть следующим образом:
d = deque('hey')
print(d) # deque(['h', 'e', 'y'])
Мы также можем предоставить аргумент maxlen, чтобы указать максимальную длину элементов, которые мы хотим иметь в нашем deque — чтобы сделать его ограниченным.
Это тривиальный пример, но давайте разберемся, как это работает:
from collections import deque
d = deque([4, 5, 3, 1, 8], maxlen=3)
print(d) # deque([3, 1, 8], maxlen=3)
d = deque([4, 5, 3, 1, 8], maxlen=4)
print(d) # deque([5, 3, 1, 8], maxlen=4)
Поскольку элементы итерабельной таблицы добавляются с одного конца, удаление других элементов (в случае примера maxlen=3, 4 и 5) будет происходить с противоположного конца.
Конечно, эффективность deque также обусловлена его методами appendleft() и popleft(), которые метко названы и лучше, чем list с точки зрения временной сложности.
from collections import deque
d = deque([7, 11])
d.appendleft(3)
print(d) # deque([3, 7, 11])
d.appendleft(1)
print(d) # deque([1, 3, 7, 11])
first_i = d.popleft()
print(first_i) # 1
print(d) # deque([3, 7, 11])
У нас также есть методы append() и pop(), которые выполняют свои операции справа/справа — как обычный список:
from collections import deque
d = deque([2, 4, 6])
d.append(8)
print(d) # deque([2, 4, 6, 8])
first_popped = d.pop()
second_popped = d.pop()
print(f'Popped {first_popped} first, then {second_popped} second.')
# -> Popped 8 first, then 6 second.
print(d) # deque([2, 4])
Теперь, когда мы рассмотрели операции append и pop с обеих сторон, давайте сначала реализуем очередь, аналогичную версии list в начале статьи:
from collections import deque
class Queue:
"""Queue implementation as a deque."""
def __init__(self):
"""Create new queue."""
self._items = deque()
def is_empty(self):
"""Check if the queue is empty."""
return not bool(self._items)
def enqueue(self, item):
"""Add an item to the queue."""
self._items.append(item)
def dequeue(self):
"""Remove an item from the queue."""
return self._items.popleft()
def size(self):
"""Get the number of items in the queue."""
return len(self._items)
Для стековой версии, поскольку нам нужно добавлять и выгружать с одного конца, методы append() и pop(), использующие list, сначала тоже могут показаться подходящими. Но давайте модифицируем предыдущую версию стека выше, чтобы реализовать его как deque:
from collections import deque
class Stack:
"""Stack implementation as a deque."""
def __init__(self):
"""Create new stack."""
self._items = deque()
def is_empty(self):
"""Check if the stack is empty."""
return not bool(self._items)
def push(self, item):
"""Add an item to the stack."""
self._items.append(item)
def pop(self):
"""Remove an item from the stack."""
return self._items.pop()
def peek(self):
"""Get the value of the top item in the stack."""
return self._items[-1]
Вроде бы ничего особенного не изменилось, но можно представить и другой конец, используя appendleft() вместе с popleft().
Мы рассмотрели очень простой способ создания стеков и очередей с помощью deque, но, конечно, есть еще много интересного. В первую очередь следует обратиться к официальной документации, также вы можете ознакомиться со статьей Real Python на эту тему. Как и во многих других случаях, вы сами решаете, чего хотите достичь, и двусторонняя очередь — это еще один инструмент в вашем наборе инструментов, который стоит рассмотреть.
* Примеры реализации стека и очереди в виде списка взяты из замечательной книги Брэда Миллера и Дэвида Ранума об алгоритмах и структурах данных.