Структури даних є важливим елементом у програмуванні. Вони дозволяють нам організовувати інформацію так, щоб можна було її ефективно використовувати. Черга є однією з найбільш зрозумілих і корисних структур даних.
У цій статті ми розглянемо, що таке черга та як її реалізувати за допомогою мови Python.
Що таке черга?
Черга — це лінійна структура даних, яка функціонує за принципом “перший прийшов, перший вийшов” (FIFO). Це відрізняється від стека, де діє принцип “останній прийшов, перший вийшов” (LIFO).
Уявімо чергу в касі кінотеатру. Ось наочний приклад черги:
У черзі до каси, друга людина зможе підійти до каси лише після того, як перша завершить свої справи. Спочатку обслуговується перший, потім другий. Таким чином, люди дотримуються принципу FIFO: хто першим прийшов, той першим і буде обслужений. Подібні черги ми спостерігаємо щодня.
Структура даних “черга” працює за тим самим принципом. Тепер ви розумієте, що таке черга та як вона працює. Давайте розглянемо операції, які можна виконувати з чергою.
Операції з чергою
Як і у випадку зі стеком, у черзі існують дві основні операції:
Помістити в чергу (enqueue)
Додає новий елемент в кінець черги. Цей кінець називається “заднім”.
Виключити з черги (dequeue)
Видаляє елемент з початку черги. Цей початок називається “переднім”.
Щоб краще зрозуміти, давайте подивимося на ілюстрації цих операцій. Як кажуть, одне зображення варте тисячі слів.
Для зручності ми можемо додати допоміжні функції, щоб отримувати додаткову інформацію про чергу. Кількість таких функцій не обмежена. Давайте зосередимося на найважливіших, згаданих нижче.
Задній елемент (rear)
Повертає останній елемент черги.
Передній елемент (front)
Повертає перший елемент черги.
Черга порожня (is_empty)
Повертає значення, що вказує, чи є черга порожньою.
Вам не набридло? Я маю на увазі, що теоретичні теми можуть бути трохи нудними.
Для мене так!
Але ми не можемо перейти до кодування, не розуміючи основних понять. Ми повинні добре їх засвоїти перед тим, як почнемо реалізацію. Не хвилюйтеся, настав час засукати рукава і перейти до коду.
Припускаю, що на вашому комп’ютері встановлено Python. Якщо ні, ви можете скористатися онлайн-компілятором.
Реалізація черги
Реалізація черги не займе у програміста більше ніж 15 хвилин. Після навчання, ви зможете реалізувати її за кілька хвилин.
Існує кілька способів реалізації черги в Python. Давайте розглянемо різні підходи крок за кроком.
#1. Використання списку
Список — це вбудований тип даних у Python. Ми використаємо його для створення класу черги. Ми пройдемо всі етапи реалізації структури даних черги з нуля, без використання будь-яких модулів. Розпочнімо.
Крок 1:
Створіть клас під назвою Queue.
class Queue:
pass
Крок 2:
Нам потрібна змінна для зберігання даних черги. Назвемо її `elements`. Звичайно, це буде список.
class Queue:
def __init__(self):
self.elements = []
Крок 3:
Для додавання елементів до черги, нам потрібен метод у класі. Назвемо його `enqueue`, як ми вже обговорювали.
Цей метод приймає дані та додає їх до кінця списку `elements`. Ми використаємо метод `append` для цього.
class Queue:
# ...
def enqueue(self, data):
self.elements.append(data)
return data
Крок 4:
Нам потрібен метод для видалення елементів з черги. Назвемо його `dequeue`. Як ви вже, мабуть, здогадалися, ми будемо використовувати метод `pop` типу даних `list`.
Метод `pop` видаляє елемент зі списку за заданим індексом. Якщо індекс не вказано, видаляється останній елемент. У нашому випадку, нам потрібно видалити перший елемент, тому ми передаємо `0` як індекс.
class Queue:
# ...
def dequeue(self):
return self.elements.pop(0)
Цього достатньо для черги. Але нам потрібні допоміжні функції, щоб перевірити, чи працює черга правильно. Давайте їх напишемо.
Крок 5:
Метод `rear()` повертає останній елемент черги. Для цього скористаємося від’ємною індексацією у списках Python.
class Queue:
# ...
def rear(self):
return self.elements[-1]
Крок 6:
Метод `front()` повертає перший елемент черги. Ми можемо отримати його за допомогою індексу `0`.
class Queue:
# ...
def front(self):
return self.elements[0]
Крок 7:
Метод `is_empty()` перевіряє, чи є черга порожньою. Для цього ми перевіряємо довжину списку.
class Queue:
# ...
def is_empty(self):
return len(self.elements) == 0
Фух! Ми завершили реалізацію структури даних черги. Тепер нам потрібно створити об’єкт, щоб використовувати наш клас `Queue`.
Зробімо це.
class Queue:
# ...
if __name__ == '__main__':
queue = Queue()
Тепер у нас є об’єкт `Queue`. Давайте перевіримо його за допомогою кількох операцій.
- Перевірте, чи черга порожня за допомогою методу `is_empty`. Він повинен повернути `True`.
- Додайте числа 1, 2, 3, 4, 5 до черги за допомогою методу `enqueue`.
- Метод `is_empty` повинен повернути `False`. Перевірте це.
- Виведіть перший та останній елементи за допомогою методів `front` та `rear` відповідно.
- Видаліть елемент з черги за допомогою методу `dequeue`.
- Перевірте перший елемент. Він повинен повернути `2`.
- Тепер видаліть усі елементи з черги.
- Метод `is_empty` повинен повернути `True`. Перевірте це.
Думаю, цього достатньо, щоб перевірити нашу реалізацію черги. Напишіть код для кожного з цих кроків, щоб перевірити її роботу.
Ви написали код?
Ні, не хвилюйтеся.
Подивіться на код нижче.
class Queue:
def __init__(self):
self.elements = []
def enqueue(self, data):
self.elements.append(data)
return data
def dequeue(self):
return self.elements.pop(0)
def rear(self):
return self.elements[-1]
def front(self):
return self.elements[0]
def is_empty(self):
return len(self.elements) == 0
if __name__ == '__main__':
queue = Queue()
## перевірка методу is_empty -> True
print(queue.is_empty())
## додавання елементів
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
queue.enqueue(4)
queue.enqueue(5)
## знову перевірка методу is_empty -> False
print(queue.is_empty())
## виведення переднього та заднього елементів за допомогою методів front та rear відповідно -> 1, 5
print(queue.front(), end=' ')
print(queue.rear())
## видалення елемента -> 1
queue.dequeue()
## перевірка переднього та заднього елементів за допомогою методів front та rear відповідно -> 2 5
print(queue.front(), end=' ')
print(queue.rear())
## видалення всіх елементів
queue.dequeue()
queue.dequeue()
queue.dequeue()
queue.dequeue()
## перевірка методу is_empty востаннє -> True
print(queue.is_empty())
Запустіть цю програму, і ви отримаєте результат, схожий на наступний.
True False 1 5 2 5 True
Ми можемо безпосередньо використовувати тип даних `list` як структуру даних черги. Реалізація черги, яку ми щойно розглянули, допоможе вам краще зрозуміти, як це реалізувати в інших мовах програмування.
Ви можете використовувати клас `Queue` в інших проєктах, просто створивши його об’єкт, як ми робили раніше.
Ми реалізували чергу з нуля, використовуючи тип даних `list`. А чи є вбудовані модулі для черги? Так! У нас є вбудовані реалізації черги. Давайте їх подивимося.
#2. Використання deque з модуля collections
`deque` (двостороння черга) реалізована в модулі `collections`. Оскільки вона підтримує додавання та видалення елементів з обох кінців, ми можемо використовувати її як стек і як чергу. Давайте подивимося, як реалізувати чергу за допомогою `deque`.
Вона реалізована за допомогою іншої структури даних, двозв’язного списку. Це забезпечує стабільну продуктивність операцій вставки та видалення. Доступ до елементів у середині двозв’язного списку має складність O(n). Ми можемо використовувати її як чергу, оскільки нам не потрібно отримувати доступ до елементів у середині черги.
Давайте перевіримо методи, які пропонує `deque`:
- `append(data)` – додає дані до кінця черги.
- `popleft()` – видаляє перший елемент з черги.
Немає окремих методів для `front`, `rear` та `is_empty`. Замість `front` та `rear` ми можемо вивести всю чергу. Для перевірки, чи порожня черга, можна використовувати функцію `len`.
Ми виконали ряд кроків для перевірки реалізації черги раніше. Давайте виконаємо ті самі кроки тут.
from collections import deque ## створення об'єкту deque queue = deque() ## перевірка, чи черга порожня -> True print(len(queue) == 0) ## додавання елементів queue.append(1) queue.append(2) queue.append(3) queue.append(4) queue.append(5) ## знову перевірка, чи черга порожня -> False print(len(queue) == 0) ## виведення черги print(queue) ## видалення елемента -> 1 queue.popleft() ## виведення черги print(queue) ## видалення всіх елементів queue.popleft() queue.popleft() queue.popleft() queue.popleft() ## перевірка, чи черга порожня востаннє -> True print(len(queue) == 0)
Ви отримаєте результат, схожий на наступний.
True False deque([1, 2, 3, 4, 5]) deque([2, 3, 4, 5]) True
#3. Використання Queue з модуля queue
У Python є вбудований модуль `queue`, який містить клас `Queue` для реалізації черги. Він схожий на клас, який ми реалізували раніше.
Давайте спочатку перевіримо методи класу `Queue`:
- `put(data)` – додає дані до черги.
- `get()` – видаляє та повертає перший елемент з черги.
- `empty()` – перевіряє, чи порожня черга.
- `qsize()` – повертає довжину черги.
Давайте реалізуємо чергу за допомогою цих методів.
from queue import Queue
## створення об'єкту Queue
queue_object = Queue()
## перевірка, чи черга порожня -> True
print(queue_object.empty())
## додавання елементів
queue_object.put(1)
queue_object.put(2)
queue_object.put(3)
queue_object.put(4)
queue_object.put(5)
## знову перевірка, чи черга порожня -> False
print(queue_object.empty())
## видалення всіх елементів
print(queue_object.get())
print(queue_object.get())
print(queue_object.get())
## перевірка розміру черги
print("Size", queue_object.qsize())
print(queue_object.get())
print(queue_object.get())
## перевірка, чи черга порожня востаннє -> True
print(queue_object.empty())
Перевірте результат наведеного коду.
True False 1 2 3 Size 2 4 5 True
У класі `Queue` є й інші методи. Ви можете їх дослідити за допомогою вбудованої функції `dir`.
Висновок
Сподіваюся, ви дізналися про структуру даних черги та її реалізацію. Це все, що стосується черги. Ви можете використовувати чергу у різних ситуаціях, де потрібно обробляти дані в порядку FIFO (перший прийшов, перший вийшов). Застосовуйте чергу щоразу, коли це доцільно.
Хочете опанувати Python? Перегляньте ці навчальні ресурси.
Щасливого кодування 🙂 👨💻