Список представляет собой один из наиболее часто используемых и знакомых наборов данных для всех, кто регулярно пишет код на Python. Это отличные структуры данных с множеством полезных функций, которые позволяют пользователю добавлять, удалять и сортировать элементы. Нет сомнений в том, что этот список является правильным выбором для многих ситуаций, но Python также предоставляет альтернативы, которые лучше подходят для определенных сценариев.
Например, списки могут быть не оптимальной структурой данных для реализации абстрактных типов данных стека или очереди. Это связано с тем, что списки не являются потокобезопасными, а это означает, что что-то может пойти не так, если несколько потоков попытаются получить доступ к одному и тому же элементу и изменить его одновременно. Это дает нам сообщения об ошибках и противоречивые данные.
Абстрактный тип данных очереди — одна из самых популярных структур данных для задач обработки данных в порядке очереди (FIFO). Одним из способов эффективной реализации очереди является использование двусвязного списка. Они идеально подходят для приложений, где требуется быстрый доступ как к первому, так и к последнему элементу очереди.
В этом сообщении блога мы рассмотрим дек Python (структуру данных двусторонней очереди, поставляемую со стандартной библиотекой Python). Мы рассмотрим, что такое дек, и расскажем, как использовать реализацию дека Python для создания структур данных и управления ими.
Что такое дек в Python?
Дек, также известный как двусторонняя очередь (произносится как «колода»), представляет собой упорядоченный набор элементов, в который можно добавлять новые элементы либо в начало, либо в конец очереди. Деки похожи на списки, но они более эффективны при добавлении или удалении элементов из начала или конца списка.
Деки часто используются в качестве очереди, но их также можно использовать в качестве стека.
При использовании в качестве очереди мы добавляем элементы в один конец очереди (обычно в конец) и удаляем их из другого конца (обычно в начало). Это представляет собой определяющее качество очереди, в которой элементы находятся в порядке поступления (FIFO).
При использовании в качестве стека мы добавляем элементы в один конец очереди (обычно в конец) и удаляем их с того же конца (также обычно в конец). Это означает, что дек может представлять собой поведение стека «последним пришел — первым вышел» (LIFO).
Python реализует дек как двусвязный список. Каждый узел в списке имеет ссылку на предыдущий узел и следующий узел. Головной узел имеет ссылку на хвостовой узел, а хвостовой узел имеет ссылку на головной узел.
Зачем использовать дек Python?
Списки не оптимальны, когда вам нужно добавить или удалить элемент спереди (индекс 0). В таких ситуациях весь список необходимо сместить вправо, чтобы освободить место для вновь добавленного элемента, или список необходимо сместить влево, чтобы заполнить пробел от вновь удаленного элемента. В любом случае время, необходимое для этого, растет линейно с размером списка. Это означает, что эти операции имеют временную сложность O(n) или линейную временную сложность.
Однако если вы используете метод.append() для добавления элемента в конец списка, то это будет очень быстрая операция с постоянной сложностью времени или O(1). Аналогично, если вы удалите самый правый элемент с помощью метода.pop(), это будет так же быстро.
Деки решают проблемы, связанные со списками при попытке доступа к передним элементам. Это связано с тем, что деки реализованы как двусвязный список с операциями добавления и извлечения, которые одинаково стабильны и быстры. Это означает, что деки могут обеспечить поточно-ориентированное и эффективное использование памяти операций добавления и извлечения с любой стороны очереди с приблизительно постоянной сложностью времени, или O(1).
Характеристики дека Python
Обобщенный абстрактный тип данных линейной очереди требует, чтобы вставка происходила на одном конце (обычно заднем), а удаление — на другом конце (обычно на переднем). Это представляет собой характеристику очереди FIFO и может привести к нескольким ограничениям на вставку и удаление элементов.
Однако дек Python позволяет нам получить доступ к обоим концам очереди для вставки и удаления.
Ниже приведены характеристики дека Python:
- Деки позволяют эффективно использовать память и потокобезопасно добавлять и извлекать данные с любой стороны очереди с примерно постоянной сложностью времени на обоих концах, что равно O(1).
- Деки можно эффективно реализовать с использованием различных структур данных, включая массивы, связанные списки и деревья.
- Деки можно использовать в качестве замены списков во многих алгоритмах и структурах данных.
- Деки имеют более предсказуемую производительность в худшем случае, чем списки
- Деки проще использовать «правильно», чем списки.
- Деки более гибкие, чем списки
- Во многих ситуациях деки более эффективны, чем списки.
- Деки можно эффективно поворачивать влево или вправо, это называется «циклический буфер».
- Деки — хороший выбор для отслеживания начальных и хвостовых элементов списка.
- Деки можно легко отменить, не создавая новый список и не копируя существующие данные.
- Деки потребляют меньше памяти, чем списки, при хранении большого количества элементов.
- Деки могут использоваться как очередь FIFO или стек LIFO.
- Дек — это двусторонняя очередь, то есть ее можно использовать как стек или очередь.
- Дек — это линейная структура данных, которая поддерживает быструю вставку и удаление на обоих концах.
- Дек часто реализуется как динамический массив, размер которого можно изменять по мере необходимости.
- Дек может использоваться для реализации других структур данных, включая стек, очередь или приоритетную очередь.
Теперь, когда мы рассмотрели характеристики дека, давайте посмотрим на типы дека в Python.
Типы деков Python
В зависимости от способа ограничения операций деки могут быть одного из двух типов:
- Дек с ограничением ввода
- Дек с ограничением вывода
Дек с ограничением ввода
Дек с ограничением ввода — это структура данных, которая позволяет удалять элементы с любого конца дека, но позволяет вставлять элементы только на одном конце дека.
Деки с ограничением ввода часто используются в приложениях, где нам требуется очередь, но порядок элементов не важен. Например, мы могли бы использовать дек с ограничением ввода для хранения задач ЦП, требующих обработки. ЦП может удалить и обработать первую задачу из начала дека, не беспокоясь о порядке оставшихся задач в деке.
Деки с ограничением ввода также часто используются в приложениях, где пространство ограничено. Это связано с тем, что им требуются только два указателя (один для начала и один для конца дека) и не требуется непрерывная память для хранения элементов дека в массиве.
Дек с ограничением вывода
Дек с ограничением вывода — это структура данных, которая позволяет вставлять элементы с любой стороны дека, но позволяет удалять элементы только с одного конца дека.
Этот тип дека может быть полезен в ситуациях, когда вам нужна гибкость очереди FIFO, но вам также необходимо удалять элементы из конца очереди. Например, если вы реализовали стек LIFO с использованием дека с ограничением вывода, вы сможете помещать (вставлять) и извлекать (удалять) элементы в верхней части стека, которая является задней частью дека.
В целом, дек с ограничением вывода — это универсальная структура данных, которую можно использовать в самых разных ситуациях. Если вам нужна функциональность очереди, но также нужна гибкость в удалении из конца очереди, тогда этот тип двухсторонней очереди будет иметь смысл.
Особенности дека
Деки позволяют нам выполнять несколько типов операций:
- Добавить элементы
- Поп-предметы
- Доступ к элементам
- Поворот элементов
Более явно, эти объекты поддерживают следующие методы дека Python:
| Метод | Описание |
| .append() | Добавьте элемент в правую часть двухсторонней очереди |
| .appendleft() | Добавьте элемент в левую часть двухсторонней очереди |
| .прозрачный() | Удалить все элементы из дека |
| .copy() | Создать копию дека |
| .считать() | Подсчитать количество вхождений данного элемента |
| .продлевать() | Расширьте правую часть дека, добавив элементы |
| .extendleft() | Расширьте левую часть дека, добавив элементы |
| .индекс() | Вернуть позицию элемента в двухсторонней очереди |
| .вставлять() | Вставить элемент в заданную позицию |
| .pop() | Удалить и вернуть элемент из правого конца двухсторонней очереди |
| .popleft() | Удалить и вернуть элемент из левого конца двухсторонней очереди |
| .удалять() | Удалить первое вхождение данного значения |
| .обеспечить регресс() | Обратный порядок элементов в двухсторонней очереди |
| .rotate() | Поворот дека на основе заданных аргументов |
| .maxlen() | Возвращает максимальный размер дека |
В таблице выше показаны различные операции, которые мы можем выполнять с объектом двухсторонней очереди. В следующем разделе мы создадим объект двухсторонней очереди и выполним эти операции на Python.
Операции с деком Python
Дек доступен как класс в модуле коллекций стандартной библиотеки Python. Мы можем импортировать дек Python из модуля коллекций и выполнять различные операции над объектом дека. В следующем разделе мы рассмотрим пример двухсторонней очереди Python.
Вставка элементов в дек Python
Для начала давайте создадим пустую дек, а затем выполним несколько операций:
from collections import deque
seq = deque() #create an empty deque
print(seq) #print the dequeseq.append(1) #use append() to insert element at right end
print(‘The deque after appending right:’,seq) #print the dequeseq.appendleft(2) #use appendleft() to insert element at left end
print(‘The deque after appending left:’, seq) #print the dequeseq.extend([4,5]) #use extend() to insert several elements at the right end
print(‘The deque after extending right:’, seq) #print the dequeseq.extendleft([6,7]) #use extendleft() to insert elements at the left end
print(‘The deque after extending left:’, seq) #print the dequeseq.insert(3,2) #use insert() to insert the value 2 at 4th position
print(‘The deque after inserting element:’, seq) #print the deque
Приведенный выше код выводит следующее:
deque([])
The deque after appending right: deque([1])
The deque after appending left: deque([2, 1])
The deque after extending right: deque([2, 1, 4, 5])
The deque after extending left: deque([7, 6, 2, 1, 4, 5])
The deque after inserting element: deque([7, 6, 2, 2, 1, 4, 5])
Так что же здесь произошло? На первом этапе мы импортировали класс deque из модуля коллекций. На втором этапе мы создали новый экземпляр объекта двухсторонней очереди без значений, что означает, что мы создали пустую двухстороннюю очередь.
После этого мы использовали метод.append(), чтобы добавить элемент в правую часть двухсторонней очереди. Затем мы использовали метод.appendleft(), чтобы добавить элемент «2» в левую часть двухсторонней очереди.
Аналогичным образом мы использовали метод.extend() для добавления элементов [4,5] в правую часть дека, а также метод.extendleft () для добавления элементов [7,6] в левую часть дека.. На последнем шаге мы использовали метод.insert() для добавления элемента «2» в четвертую позицию (то есть индекс 3).
Теперь давайте посмотрим, как удалить элементы из объекта двухсторонней очереди.
Удаление элементов из Python Deque
Теперь мы рассмотрим различные методы удаления элементов из дека Python.
from collections import deque
seq = deque([1,2,3,4,5,6]) #create a new deque
print(seq) #print the dequeseq.pop() #use pop() to remove right most element
print(seq) #print the dequeseq.popleft() #use popleft() to remove leftmost element
print(seq) #print the dequeseq.remove(3) #use remove() to remove the given element
print(seq) #print the dequeseq.clear() #use clear() to clear all elements in the deque
print(seq) #print the deque
Приведенный выше код выводит следующее:
deque([1, 2, 3, 4, 5, 6])
deque([1, 2, 3, 4, 5])
deque([2, 3, 4, 5])
deque([2, 4, 5])
deque([])
На первом этапе мы импортировали класс deque из модуля коллекций, а затем определили новый объект deque. Затем мы использовали метод.pop() для удаления самого правого элемента из объекта двухсторонней очереди. Мы также использовали метод.popleft() для удаления самого левого элемента. После этого мы использовали метод.remove() для удаления элемента «3», передав аргумент. Наконец, мы использовали метод.clear() для очистки всех элементов в деке, в результате чего у нас остался пустой объект дека.
В следующем разделе мы рассмотрим дополнительные операции, которые может предложить deque.
Другие операции с деком Python
Помимо добавления и удаления элементов, мы можем выполнять другие операции, включая подсчет элементов, поиск индекса элемента, поворот объекта двухсторонней очереди и т. д. Следующий код показывает, как работают эти операции:
from collections import deque
seq = deque([1,1,2,3,4,5,6]) #create a new deque
print(seq) #print the dequea = seq.count(1) #count the occurrence of 1
print(‘Count of 1 is:’, a) #print the count of 1b = seq.copy() #copy the deque object using count()
print(b) #print the dequec = seq.index(2) #get the index of the element 2
print(‘The index of 2:’, c) #print the indexseq.reverse() #reverse the deque object using reverse()
print(seq) #print the dequeseq.rotate(1) #rotate the deque object to the right
print(seq) #print the deque
Приведенный выше код выводит следующее:
deque([1, 1, 2, 3, 4, 5, 6])
Count of 1 is: 2
deque([1, 1, 2, 3, 4, 5, 6])
The index of 2: 2
deque([6, 5, 4, 3, 2, 1, 1])
deque([1, 6, 5, 4, 3, 2, 1])
На первом этапе мы импортировали класс deque из модуля коллекций, а затем создали объект deque. Затем мы использовали метод.count() для подсчета появления «1» в двухсторонней очереди и распечатали результат. Затем мы использовали метод.copy() для копирования объекта дека в переменную «b». Мы использовали метод.index() для возврата индекса случайного элемента «2». Мы также использовали метод.reverse() для изменения направления объекта дека и, наконец, повернули дек вправо с помощью метода.rotate() и аргумента «1».
Это некоторые операции, которые можно выполнить над объектом двухсторонней очереди. Другие методы, которые мы можем использовать с реализацией дека Python, включают.maxlen(),.len() и.reversed().
Заключение
Дек Python — это важная структура данных, используемая во многих приложениях. В этой статье мы обсудили, что такое двухсторонняя очередь, а также различные операции, которые мы можем выполнять с объектом двухсторонней очереди. Деки в основном используются, когда:
- Нам нужна быстрая временная сложность
- Нам нужен небольшой объем памяти
- Мы хотим создать стек LIFO.
- Мы хотим создать очередь FIFO.
Часто задаваемые вопросы
Что такое очереди и деки в Python?
Очередь — это абстрактный тип данных, представляющий список элементов в порядке FIFO. Дек — это встроенная структура данных Python, которая представляет собой двустороннюю очередь, элементы которой можно добавлять или удалять с любого конца.
Является ли дек Python списком?
Нет, дек — это не список. Дек — это собственная структура данных, похожая на список, но с дополнительными функциями.
Является ли дек лучше очереди в Python?
На этот вопрос нет однозначного ответа, поскольку он зависит от конкретных потребностей программы. Однако в целом двусторонняя очередь может быть более универсальной, чем обычная очередь, поскольку она обеспечивает эффективную вставку и удаление как в начале, так и в конце очереди.
Почему мы используем дек?
Дек используется, когда вам нужна структура данных, подобная очереди, которая позволяет быстро вставлять и удалять как в передней, так и в задней части структуры данных.
Как использовать Deque в качестве стека в Python?
Есть два способа использовать дек Python в качестве стека. Первый способ — использовать методыappend() и pop(). Второй способ — использовать методыappendleft() и popleft().
