Deque In Python — Учебник с примерами

Если вы разработчик Python, вы, вероятно, слышали о двухсторонней очереди или «двойной очереди». Это мощный инструмент, который может повысить эффективность вашего приложения и ускорить его работу.

Deque — это специализированный тип данных контейнера, который предлагает более быстрые операции добавления и извлечения с обоих концов контейнера. Это делает его ценным инструментом для реализации очередей и стеков, которые являются распространенными типами данных, подобными спискам, в вычислениях.

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

Продолжайте читать, чтобы узнать больше о Deques и о том, как вы можете реализовать их в своем коде Python !

Оглавление

• Что такое Дека?
  • Особенности Python Deque
  • Приложения Deque
• Как создать и инициализировать дек
  • Использование функции deque()
  • Инициализация двухсторонней очереди с элементами
• Как выполнять стандартные операции Deque
  • Добавление элементов в Deque
  • Добавление нескольких элементов данных в очередь
  • Удаление элементов из очереди
  • Удаление всех элементов из очереди
  • Доступ к элементам дека
  • Изменение элементов дека
• Как работать с деком как с очередью
  • Использование методов append() и popleft()
  • Проверка того, пуста ли очередь Deque
• Работа с Deque как стеком
  • Использование методов append() и pop()
  • Проверка на наличие пустого объекта Deque
• Что такое ограниченная дека?
  • • Ограниченная дека ввода
    • Выходная ограниченная двухсторонняя очередь
• Давайте завернем это

Что такое Дека?

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

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

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

Он также предоставляет функции для других полезных операций, таких как ротация очереди или ее полная очистка.

Особенности Python Deque

В отличие от обычного списка, который имеет временную сложность O(n) для операций добавления и извлечения, двухсторонняя очередь обеспечивает временную сложность O(1). Это значительно ускоряет и эффективно использует память для этих операций чтения и записи.

Вот еще несколько функций deque Python, о которых вам следует знать:

• Это изменяемая структура данных.

• Он может хранить несколько типов данных, например, целые числа, кортежи, массивы и т. д.

• Он поддерживает индексирование, но не операции нарезки.

• Не поддерживает сортировку на месте

• Он поддерживает общие встроенные итерируемые функции и операции, такие как in , sorted() , len() , reverse() и т. д.

Приложения Deque

Деки полезны по целому ряду причин. Например, их можно использовать для реализации очереди или стека, которые являются распространенными структурами данных в информатике.

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

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

Как создать и инициализировать дек

Вы можете создать очередь, используя встроенную функцию из модуля collections. Давайте внимательно посмотрим, как вы можете создать и заполнить эту структуру данных.

Использование функции deque()

Чтобы создать очередь в Python, вы можете использовать встроенную функцию deque() из модуля collections. Эта функция возвращает новый пустой объект двухсторонней очереди, который можно использовать для реализации двусторонней очереди.

Вот пример того, как создать пустой объект deque:

from collections import deque 

my_deque = deque() 

Вы также можете создать очередь с начальными элементами, передав итерируемый объект (список, кортеж и т. д.) в функцию deque() . Двухсторонняя очередь будет инициализирована элементами итерации слева направо.

Вот пример:

from collections import deque

my_list = [1, 2, 3, 4, 5] 
my_deque = deque(my_list)

Инициализация двухсторонней очереди с элементами

Вы также можете инициализировать пустую очередь с элементами, используя различные методы. Один из способов сделать это — использовать методы append() и appendleft() для добавления элементов в очередь справа и слева соответственно.

Вот пример:

from collections import deque

#Initialize the empty deque
my_deque = deque()
print(my_deque)

#Add Values to the deque
my_deque.append(1) 
my_deque.append(2) 
my_deque.appendleft(3) 

print(my_deque)

После запуска этого кода очередь будет содержать элементы [3, 1, 2].

Другой способ инициализировать очередь с элементами — передать список элементов в функцию deque() .

Вот пример:

from collections import deque

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

Запуск этого кода создаст объект очереди, содержащий элементы [1, 2, 3] .

В целом, создание и инициализация двухсторонней очереди в Python не представляет сложности и может быть выполнена с помощью встроенной функции deque() . Вы также можете сделать это, добавив элементы в пустую очередь, используя методы append() и appendleft() .

Как выполнять стандартные операции Deque

Существует множество операций, которые вы можете выполнять с объектами deque в Python. Давайте проверим некоторые из наиболее популярных из них.

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

Вы можете добавлять элементы в очередь Python , используя методы append() и appendleft() . Метод append () добавляет элемент в правый конец очереди, а метод appendleft() добавляет элемент в левый конец очереди.

Вот пример:

import collections 

# Create an empty deque 
my_deque = collections.deque() 

# Add elements to the deque 
my_deque.append(1) 
my_deque.appendleft(2) 
my_deque.append(3) 

print(my_deque) 

# Output: 
deque([2, 1, 3])

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

Если вы не хотите добавлять элементы данных в очередь один за другим, вы можете ускорить процесс с помощью функций extend() или extendleft() . Эти функции принимают итерируемый объект и добавляют его содержимое в конец или в левый конец двухсторонней очереди соответственно.

Вот пример:

from collections import deque

my_list = [1, 2, 3, 4, 5] 
my_deque = deque(my_list)

#Creating a tuple and list
cont = (11, 12, 13, 14)
full = [10,20,30]

#Extending the deque from the right
my_deque.extend(cont)
print(my_deque)

#Extending the deque from the left
my_deque.extendleft(full)
print(my_deque)

В приведенном выше коде функция extend() добавляет несколько значений кортежа cont в конец очереди. Затем функция extendleft() добавляет несколько элементов данных из полного списка в левый конец очереди.

Удаление элементов из очереди

Вы можете удалить элементы из двухсторонней очереди Python, используя методы pop() и popleft() . Метод pop() удаляет и возвращает крайний правый элемент очереди, а метод popleft() удаляет и возвращает крайний левый элемент очереди.

Вот пример:

import collections 

#Create a deque with some elements 
my_deque = collections.deque([1, 2, 3, 4, 5]) 

#Remove elements from the deque 
my_deque.pop() 
my_deque.popleft() 

print(my_deque) 

# Output: deque([2, 3, 4])

Вы также можете удалить конкретное значение из двухсторонней очереди, используя функцию remove() . Функция удаляет первое вхождение указанного значения из очереди.

Вот пример:

import collections 

#Create a deque with some elements 
my_deque = collections.deque([1, 2, 1, 4, 5]) 

#Remove elements from the deque 
my_deque.remove(1)

print(my_deque) 

# Output: deque([2, 1, 4, 5])

Если элемент не найден, Python вернет ValueError .

Удаление всех элементов из очереди

Чтобы удалить все элементы из Deque и вернуть его в пустое состояние, мы можем использовать функцию clear() . Вот как это работает:

from collections import deque 

#Create a deque with some elements 
my_deque = deque([1, 2, 1, 4, 5]) 

#Remove all elements from the deque 
my_deque.clear()

print(my_deque) 

# Output: 
deque([])

Accessing Elements of a Deque

You can access elements of a Python deque using the indexing operator []. You can also use a negative value in the indexing operator to access the deque elements from the right.

The indexing starts from 0 for the leftmost element and -1 for the rightmost element. Here’s an example:

import collections 

# Create a deque with some elements 
my_deque = collections.deque([1, 2, 3, 4, 5]) 

# Access elements of the deque 
print(my_deque[0]) 
# Output: 1 

print(my_deque[-1]) 
# Output: 5 

Modifying Elements of a Deque

You can modify elements of a Python deque using the indexing operator “[]” and the assignment operator “=“. Here’s an example:

from collections import deque

# Create a deque with some elements 
my_deque = deque([1, 2, 3, 4, 5]) 
print(my_deque)

# Modify elements of the deque 
my_deque[0] = 10 
my_deque[-1] = 50 

print(my_deque) 

In the above code, the indexing operator changes the first and last elements of the deque to 10 and 50 respectively.

These are the basic operations you can perform on a deque object in Python. With these operations, you can efficiently implement various data structures such as queues, stacks, and more.

How to Work with a Deque as a Queue

You can use a deque in Python to implement a queue data structure. A queue is an abstract data type that operates on a first in first out (FIFO) basis.

What this means is that you can append new items from one end of the queue and push out old items from the other end.

A good way to explain this is a line at a store. Typically, the first person to arrive will be at the head of the line and will be attended to first.

New arrivals will have to head to the back of the line and wait their turn. So, the first in will be the first answered, while the last in will be the last attended to.

Here’s how you can use a deque to implement queues.

Using append() and popleft() Methods

Чтобы использовать очередь в качестве очереди, вы можете использовать метод append() для добавления элементов в правый конец очереди. Кроме того, вы можете использовать метод popleft() для удаления элементов с левого конца очереди.

Это очень эффективный способ реализации очереди в Python. Вот пример:

from collections import deque 

queue = deque() 
queue.append(1) 
queue.append(2) 
queue.append(3) 

print(queue) 
# Output: deque([1, 2, 3]) 

x = queue.popleft() 
print(x) 
# Output: 1 

print(queue) 
# Output: deque([2, 3]) 

Как видите, метод append() добавляет элементы в правый конец очереди, а метод popleft() удаляет элементы из левого конца очереди.

Это именно то, что нам нужно в реализации очереди.

Проверка того, пуста ли очередь Deque

Чтобы проверить, пуста ли двухсторонняя очередь, вы можете использовать оператор not . Вот пример:

from collections import deque 

queue = deque() 
if not queue: 
   print("Queue is empty") 
else: 
   print("Queue is not empty") 

Это выведет « Очередь пуста », потому что очередь пуста. Если вы добавите элементы в очередь, она больше не будет пустой.

В заключение, использование двухсторонней очереди в качестве очереди в Python очень эффективно и легко реализуемо.

Работа с Deque как стеком

Как и очереди, стеки — еще один пример абстрактных типов данных, которые можно использовать для организации данных. В отличие от очередей, стеки работают по принципу «последний пришел – первый обслужен» (LIFO).

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

Использование методов append() и pop()

При использовании Deque в качестве стека вы можете добавлять элементы в верхнюю часть стека с помощью метода append() . Этот метод добавляет элемент в правый конец двухсторонней очереди.

Точно так же вы можете удалять элементы из вершины стека, используя метод pop() . Этот метод удаляет и возвращает самый правый элемент двухсторонней очереди.

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

 my_stack.append(5) 

Это добавит элемент 5 на вершину стека.

Если вы хотите удалить верхний элемент из стека, вы можете использовать метод pop():

bal = my_stack.pop() 

print(bal)
# Output: 5

Это удалит и вернет крайний правый элемент двухсторонней очереди, который в данном случае равен 5.

Проверка на наличие пустого объекта Deque

Вы можете проверить, пуст ли стек deque, используя логический оператор « not ». Если дек пуст, « not my_deque » вернет True . В противном случае он вернет False .

Например, предположим, что у вас есть стек deque с именем « my_deque », и вы хотите проверить, не пуст ли он. Вы можете использовать следующий код:

if not my_deque: 
   print("The deque is empty") 

else: 
   print("The deque is not empty") 

Это напечатает « The deque is empty », если двухсторонняя очередь пуста. Если он не пуст, вывод будет « The deque is not empty ».

При работе с Deque как со стеком важно следить за тем, пуст стек или нет. Если вы попытаетесь извлечь элемент из пустого стека, вы получите IndexError .

Что такое ограниченная дека?

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

Давайте посмотрим на них:

Ограниченная дека ввода

Двухсторонняя очередь с ограниченным вводом позволяет извлекать или удалять элементы данных с обоих концов двухсторонней очереди. Однако вы можете вставлять элементы данных только с одного конца очереди.

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

Выходная ограниченная двухсторонняя очередь

Двухсторонняя очередь с ограничением вывода позволяет вам вставлять данные с обоих концов двухсторонней очереди. Однако вы можете удалять элементы только с одного конца двухсторонней очереди, который называется внешним интерфейсом.

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

Давайте завернем это

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

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

Они также являются отличным выбором, когда вам нужно реализовать стек или двустороннюю очередь. Некоторые из ключевых преимуществ использования деков включают в себя:

• Эффективные O(1) операции добавления и извлечения с обоих концов двухсторонней очереди

• Быстрый доступ O(1) к первому и последнему элементам очереди

• Встроенная поддержка потокобезопасных атомарных операций

• Гибкие методы вставки, удаления и поворота элементов в деке

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

Готовы узнать больше о Python, ознакомьтесь с нашим плейлистом ниже