Розуміння реалізації черги в Python

Структури даних відіграють ключову роль у світі програмування. Вони допомагають нам упорядковувати наші дані таким чином, щоб їх можна було ефективно використовувати. Черга є однією з найпростіших доступних структур даних.

У цій статті ми дізнаємося про чергу та її реалізацію в Python.

Що таке черга?

Черга — це лінійна структура даних, яка відповідає принципу «першим прийшов/першим вийшов» (FIFO). Це протилежність до структури даних стека.

Ми можемо порівняти чергу з реальною чергою біля каси кінотеатру. Розглянемо наступну ілюстрацію черги.

Якщо спостерігати за чергою біля стійки, друга особа може пройти до стійки лише після того, як перша особа закінчить свою роботу. Тут до прилавка підходить перший, а потім другий. Отже, тут люди дотримуються принципу FIFO (першим прийшов/першим вийшов). Хто перший прийде, той першим і завершить роботу. Подібні черги ми можемо спостерігати в нашому повсякденному житті.

Структура даних черги також дотримується того самого принципу. Тепер ви знаєте, що таке черги і принцип їх роботи. Давайте розглянемо операції, які можна виконувати над структурою даних черги.

Операції в черзі

Подібно до стеку, ми знайдемо дві основні операції в структурі даних черги.

поставити в чергу (дані)

Додає нові дані в чергу в кінці. Бічна частина називається задньою.

виключити з черги()

Видаляє дані з початку черги. Сторона називається передньою.

Давайте переглянемо ілюстрації операцій черги для кращого розуміння. Одне зображення говорить тисячу слів.

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

задній()

Повертає перший елемент із кінця черги.

фронт()

Повертає перший елемент із початку черги.

пусто()

Повертає, чи черга порожня чи ні.

Вам не нудно? Я маю на увазі концептуальні теми.

Для мене Так!

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

Я припускаю, що на вашому комп’ютері встановлено python, якщо ні, ви також можете спробувати онлайн-компілятор.

Реалізація черги

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

Є кілька способів реалізації черги в Python. Давайте крок за кроком розглянемо різні реалізації черги.

#1. Список

Список є вбудованим типом даних у Python. Ми збираємося використовувати тип даних list для реалізації черги в класі. Ми розповімо вам про різні етапи впровадження структури даних черги з нуля без будь-яких модулів. Давайте стрибнемо в нього.

Крок 1:

Напишіть клас під назвою Queue.

class Queue:
	pass

Крок 2:

Повинна бути якась змінна для зберігання даних черги в класі. Назвемо його елементами. І це, звичайно, список.

class Queue:

	def __init__(self):
		self.elements = []

крок 3:

Щоб вставити дані в чергу, нам потрібен метод у класі. Метод називається enqueue, як ми вже обговорювали в попередньому розділі підручника.

Метод бере деякі дані та додає їх до черги (елементів). Ми можемо використовувати метод append типу даних list, щоб додати дані в кінець черги.

class Queue:

	# ...

	def enqueue(self, data):
		self.elements.append(data)
		return data

крок 4:

З черги повинен бути вихід. І це називається дечерга. Думаю, ви вже здогадалися, що ми будемо використовувати метод pop типу даних list. Якщо ви вгадали чи ні, ура!

Метод pop типу даних list видаляє елемент зі списку заданого індексу. Якщо ми не дали жодного індексу, то видаляється останній елемент списку.

Тут нам потрібно видалити перший елемент списку. Отже, ми повинні передати індекс 0 методу pop.

class Queue:

	# ...

	def dequeue(self):
		return self.elements.pop(0)

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

крок 5:

Метод rear() використовується для отримання останнього елемента черги. Негативна індексація в типі даних list допомагає нам отримати останній елемент черги.

class Queue:

	# ...

	def rear(self):
		return self.elements[-1]

крок 6:

Метод front() використовується для отримання першого елемента черги. Ми можемо отримати перший елемент черги за допомогою індексу списку.

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 до черги за допомогою методу постановки в чергу.
• Метод is_empty має повертати False. Перевір це.
• Надрукуйте передні та задні елементи відповідно переднім і заднім методами.
• Видаліть елемент із черги за допомогою методу 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()

	## checking is_empty method -> True
	print(queue.is_empty())

	## adding the elements
	queue.enqueue(1)
	queue.enqueue(2)
	queue.enqueue(3)
	queue.enqueue(4)
	queue.enqueue(5)

	## again checking is_empty method -> False
	print(queue.is_empty())

	## printing the front and rear elements using front and rear methods respectively -> 1, 5
	print(queue.front(), end=' ')
	print(queue.rear())

	## removing the element -> 1
	queue.dequeue()

	## checking the front and rear elements using front and rear methods respectively -> 2 5
	print(queue.front(), end=' ')
	print(queue.rear())

	## removing all the elements
	queue.dequeue()
	queue.dequeue()
	queue.dequeue()
	queue.dequeue()

	## checking the is_empty method for the last time -> True
	print(queue.is_empty())

Я думаю, що ви запускаєте наведену вище програму. Ви можете отримати результат, подібний до наступного.

True
False
1 5
2 5
True

Ми можемо безпосередньо використовувати тип даних списку як структуру даних черги. Наведена вище реалізація черги допоможе вам краще зрозуміти реалізацію черги в інших мовах програмування.

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

Ми реалізували чергу з нуля, використовуючи тип даних list. Чи є вбудовані модулі для черги? так! у нас є вбудовані реалізації черги. Давайте їх подивимось.

#2. дека з колекцій

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

Він реалізований за допомогою інших структур даних, які називаються двозв’язаним списком. Таким чином, продуктивність вставки та видалення елементів узгоджена. Доступ до елементів із середнього пов’язаного списку зайняв O(n) часу. Ми можемо використовувати його як чергу, оскільки немає необхідності отримувати доступ до середніх елементів із черги.

Давайте перевіримо різні методи, які пропонує нам дечерга.

• append(data) – використовується для додавання даних до черги
• popleft() – використовується для видалення першого елемента з черги

Немає альтернативних методів для front, rear і is_empty. Ми можемо надрукувати всю чергу замість переднього та заднього методів. Далі ми можемо використати метод len, щоб перевірити, чи черга порожня чи ні.

Ми виконали серію кроків, щоб перевірити реалізацію черги в попередньому. Давайте виконаємо ту саму послідовність кроків і тут.

from collections import deque

## creating deque object
queue = deque()

## checking whether queue is empty or not -> True
print(len(queue) == 0)

## pushing the elements
queue.append(1)
queue.append(2)
queue.append(3)
queue.append(4)
queue.append(5)

## again checking whether queue is empty or not -> False
print(len(queue) == 0)

## printing the queue
print(queue)

## removing the element -> 1
queue.popleft()

## printing the queue
print(queue)

## removing all the elements
queue.popleft()
queue.popleft()
queue.popleft()
queue.popleft()

## checking the whether queue is empty or not for the last time -> True
print(len(queue) == 0)

Ви отримаєте результат, подібний до наступного.

True
False
deque([1, 2, 3, 4, 5])
deque([2, 3, 4, 5])
True

#3. Черга з черги

У Python є вбудований модуль під назвою queue, який обслуговує клас під назвою Queue для реалізації черги. Він схожий на той, який ми реалізували раніше.

Спочатку перевіримо різні методи класу Queue.

• put(data) – додає або надсилає дані до черги
• get() – видаляє перший елемент із черги та повертає його
• empty() – повертає, чи стек порожній чи ні
• qsize() – повертає довжину черги.

Давайте реалізуємо чергу за допомогою описаних вище методів.

from queue import Queue

## creating Queue object
queue_object = Queue()

## checking whether queue is empty or not -> True
print(queue_object.empty())

## adding the elements
queue_object.put(1)
queue_object.put(2)
queue_object.put(3)
queue_object.put(4)
queue_object.put(5)

## again checking whether queue is empty or not -> False
print(queue_object.empty())

## removing all the elements
print(queue_object.get())
print(queue_object.get())
print(queue_object.get())

## checking the queue size
print("Size", queue_object.qsize())

print(queue_object.get())
print(queue_object.get())

## checking the whether queue_object is empty or not for the last time -> True
print(queue_object.empty())

Перевірте результат наведеного вище коду.

True
False
1
2
3
Size 2
4
5
True

У класі Queue є деякі інші методи. Ви можете досліджувати їх за допомогою вбудованої функції dir.

Висновок

Сподіваюся, ви дізналися про структуру даних черги та її реалізацію. Ось і все, що стосується черги. Ви можете використовувати чергу в різних місцях, де потрібно обробляти дані в порядку FIFO (першим увійшов/першим вийшов). Використовуйте чергу у вирішенні проблем щоразу, коли є можливість її використовувати.

Хочете опанувати Python? Перегляньте ці навчальні ресурси.

Щасливого кодування 🙂 👨‍💻