Deque в Python – підручник із прикладами

Якщо ви розробник Python, ви, ймовірно, чули про deque або «чергу з двома кінцями». Це потужний інструмент, який може підвищити ефективність вашої програми та прискорити її роботу.

Deque — це спеціалізований тип даних контейнера, який пропонує швидші операції додавання та висунення з обох кінців контейнера. Це робить його цінним інструментом для реалізації черг і стеків, які є поширеними типами даних у формі списків в обчисленнях.

Це низькорівнева та високооптимізована структура даних, яка дуже корисна для різноманітних програм. Як програміст на Python, deque — це один із інструментів, який ви захочете мати у своєму арсеналі.

Продовжуйте читати, щоб дізнатися більше про Deques і про те, як ви можете застосувати їх у своєму!

Зміст

• Що таке Deque?
  • Особливості Python Deque
  • Застосування A Deque
• Як створити та ініціалізувати Deque
  • Використання функції deque().
  • Ініціалізація Deque з елементами
• Як виконувати загальні операції Deque
  • Додавання елементів до Deque
  • Додавання кількох елементів даних до Deque
  • Видалення елементів із Deque
  • Видалення всіх елементів із Deque
  • Доступ до елементів Deque
  • Модифікація елементів Deque
• Як працювати з Deque як чергою
  • Використання методів append() і popleft().
  • Перевірка порожньої черги Deque
• Робота з Deque як стеком
  • Використання методів append() і pop().
  • Перевірка на порожній об’єкт Deque
• Що таке Restricted Deque?
  • • Deque з обмеженим введенням
    • Обмеження виведення Deque
• Давайте завершимо це

Що таке Deque?

Якщо ви новачок у Python або комп’ютерному програмуванні загалом, вам може бути цікаво, що таке deque. Deque розшифровується як « двостороння черга », і це структура даних, яка дозволяє додавати та видаляти елементи з обох кінців черги.

Це схоже на звичайну чергу, але з додатковою гнучкістю, що дозволяє додавати та видаляти елементи як з початку, так і з кінця черги. Це можливо тому, що deque Python реалізовано як подвійний зв’язаний список.

У Python deque реалізовано за допомогою модуля collections, який надає клас deque. Цей клас надає ряд методів для додавання та видалення елементів з deque.

Він також надає функції для інших корисних операцій, таких як обертання дек-черги або її повне очищення.

Особливості Python Deque

На відміну від звичайного списку, який має O(n) часову складність для операцій додавання та висунення, deque забезпечує O(1) часову складність. Це робить його значно швидшим і ефективнішим для цих операцій читання та запису.

Ось ще кілька функцій Python deque, про які вам варто знати:

• Це змінна структура даних.

• Він може зберігати кілька типів даних, наприклад, цілі числа, кортежі, масиви тощо.

• Він підтримує індексування, але не операції нарізки.

• Він не підтримує сортування на місці

• Він підтримує типові вбудовані ітераційні функції та операції, такі як in , sorted() , len() , reverse() тощо.

Застосування A Deque

Deques корисні з різних причин. Наприклад, їх можна використовувати для реалізації черги або стека, обидва з яких є звичайними структурами даних в інформатиці.

Їх також можна використовувати для ефективної обробки даних у режимі реального часу, наприклад, у потокових програмах або системах, які потребують швидкого доступу до даних.

На додаток до використання для черг і стеків, двосторонні пакети також можуть використовуватися для реалізації алгоритмів пошуку в ширину. Вони також корисні для підтримки ковзного вікна елементів у більшій послідовності.

Як створити та ініціалізувати Deque

Ви можете створити deque за допомогою вбудованої функції з модуля колекцій. Давайте детально розглянемо, як ви можете створити та заповнити цю структуру даних.

Використання функції deque().

Щоб створити deque у Python, ви можете використати вбудовану функцію deque() із модуля collections. Ця функція повертає новий порожній об’єкт deque, який можна використовувати для реалізації двосторонньої черги.

Ось приклад того, як створити порожній об’єкт deque:

from collections import deque 

my_deque = deque() 

Ви також можете створити deque з початковими елементами, передавши iterable (список, кортеж тощо) у функцію deque() . Deque буде ініціалізовано елементами в iterable, зліва направо.

Ось приклад:

from collections import deque

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

Ініціалізація Deque з елементами

Ви також можете ініціалізувати порожню чергу з елементами різними методами. Один із способів зробити це — використовувати методи 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)

Після виконання цього коду deque міститиме елементи [3, 1, 2].

Інший спосіб ініціалізації deque з елементами - передати список елементів у функцію deque() .

Ось приклад:

from collections import deque

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

Запуск цього коду створить об’єкт deque, що містить елементи [1, 2, 3] .

Загалом, створення та ініціалізація deque в Python проста і може бути виконана за допомогою вбудованої функції deque() . Ви також можете зробити це, додавши елементи до порожнього двостороннього ряду за допомогою методів append() і appendleft() .

Як виконувати загальні операції Deque

У Python можна виконувати багато операцій над об’єктами deque. Давайте розглянемо деякі з найпопулярніших.

Додавання елементів до Deque

Ви можете додати елементи до deque за допомогою методів 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])

Додавання кількох елементів даних до Deque

Якщо ви не хочете додавати елементи даних до deque один за одним, ви можете прискорити процес за допомогою функцій extend() або extendleft() . Ці функції приймають iterable і додають вміст iterable до кінця або лівого кінця deque відповідно.

Ось приклад:

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() додає кілька елементів даних із повного списку до лівого кінця двоканальної таблиці.

Видалення елементів із Deque

Ви можете видаляти елементи з двоканального коду 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])

Ви також можете видалити конкретне значення з deque за допомогою функції 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

Щоб видалити всі елементи з 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([])

Доступ до елементів Deque

Ви можете отримати доступ до елементів Python deque за допомогою оператора індексування [] . Ви також можете використовувати від’ємне значення в операторі індексування для доступу до елементів deque справа.

Індексація починається з 0 для крайнього лівого елемента та -1 для крайнього правого елемента. Ось приклад:

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 

Модифікація елементів Deque

Ви можете змінювати елементи Python deque за допомогою оператора індексування “ [] ” та оператора призначення “ = “. Ось приклад:

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) 

У наведеному вище коді оператор індексування змінює перший і останній елементи двосторонньої послідовності на 10 і 50 відповідно.

Це основні операції, які можна виконати над об’єктом deque у Python. За допомогою цих операцій ви можете ефективно реалізувати різні структури даних, такі як черги, стеки тощо.

Як працювати з Deque як чергою

Ви можете використовувати deque в Python для реалізації структури даних черги. Черга — це абстрактний тип даних, який працює за принципом FIFO .

Це означає, що ви можете додавати нові елементи з одного кінця черги та виштовхувати старі елементи з іншого кінця.

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

To use a deque as a queue, you can use the append() method to add elements to the right end of the deque. Additionally, you can use the popleft() method to remove elements from the left end of the deque.

This is a very efficient way to implement a queue in Python. Here is an example:

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]) 

As you can see, the append() method adds elements to the right end of the deque, and the popleft() method removes elements from the left end of the deque.

This is exactly what we need in a queue implementation.

Checking if a Deque Queue is Empty

To check if a deque is empty, you can use the not operator. Here is an example:

from collections import deque 

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

This will output “Queue is empty” because the deque is empty. If you add elements to the deque, it will no longer be empty.

In conclusion, using a deque as a queue in Python is very efficient and easy to implement.

Working with Deque as a Stack

Just like queues, stacks are another example of abstract data types that you can use in organizing data. Unlike queues, stacks operate in a last in first out (LIFO) fashion.

This means the last element into the deque will be the first element out. Here’s how you can implement this using the underlying data structure.

Using append() and pop() Methods

When using Deque as a stack, you can add elements to the top of the stack using the append() method. This method adds the element to the right end of the deque.

Similarly, you can remove elements from the top of the stack using the pop() method. This method removes and returns the rightmost element of the deque.

For example, let’s say you have a deque called “my_stack” and you want to add an element to the top of the stack. You can use the following code:

 my_stack.append(5) 

This will add the element 5 to the top of the stack.

If you want to remove the top element from the stack, you can use the pop() method: `

bal = my_stack.pop() 

print(bal)
# Output: 5

This will remove and return the rightmost element of the deque, which in this case is 5.

Checking for an Empty Deque Object

You can check if a deque stack is empty by using the boolean operator “not“. If the deque is empty, “not my_deque” will return True. Otherwise, it will return False.

For example, let’s say you have a deque stack called “my_deque” and you want to check if it is empty. You can use the following code:

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

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

This will print “The deque is empty” if the deque is empty. If it is not empty, the output will be “The deque is not empty“.

When working with Deque as a stack, it is important to keep track of whether the stack is empty or not. If you try to pop an element from an empty stack, you will get an IndexError.

What is A Restricted Deque?

A restricted deque is a double-ended queue with some restrictions placed on data append and pop operations on either end of the deque. There are two main types of restricted deques; Input restricted deque and output restricted deques

Let’s look at them:

Input Restricted Deque

An input-restricted deque allows you to pop or delete data elements from both ends of the deque. However, you can only insert data elements from one end of the deque.

This is very useful in applications with memory constraints. You can use it to add data elements in chronological order while retaining the ability to discard data from any end of the deque.

Output Restricted Deque

An output-restricted deque allows you to insert data from both ends of the deque. However, you can only delete items from one end of the deque called the front end.

An output-restricted deque is very useful in cases where you need to implement a FIFO data structure, but still want the functionality to append data from both ends.

Let’s Wrap This UP

By now, you should have a good understanding of the deque module in Python and how it can be used to implement efficient queues and stacks.

Deques are a versatile data structure that offers many advantages over traditional lists. These advantages are apparent when it comes to memory-efficient append and pop operations.

They are also a great choice when you need to implement a stack or a double-ended queue. Some of the key benefits of using deques include:

• Efficient O(1) append and pop operations from both ends of the deque

• Fast O(1) access to the first and last elements of the deque

• Built-in support for thread-safe, atomic operations

• Flexible methods for inserting, removing, and rotating elements in the deque

Overall, the deque module is a powerful tool that can help you write more efficient and maintainable Python code. Whether you are working on a small script or a large-scale project, deques are definitely worth considering as an alternative to traditional lists or other data structures!

Готові дізнатися більше про Python, перегляньте наш список відтворення нижче