Pochopení implementace fronty v Pythonu

Datové struktury hrají klíčovou roli ve světě programování. Pomáhají nám organizovat naše data způsobem, který lze efektivně využít. Fronta je jednou z nejjednodušších dostupných datových struktur.

V tomto článku se seznámíme s Queue a její implementací v Pythonu.

Co je to fronta?

Fronta je lineární datová struktura, která se řídí principem First In/First Out (FIFO). Je opakem datové struktury zásobníku.

Frontu můžeme porovnat s reálnou frontou u pokladny kina. Podívejme se na ilustraci fronty následovně.

Pokud pozorujete frontu u přepážky, může druhá osoba jít k přepážce až poté, co první dokončí svou práci. Zde přichází k přepážce první osoba a poté druhá osoba. Takže zde lidé dodržují princip FIFO (First In/First Out). Kdo dřív přijde, ten dřív dílo dokončí. Podobný druh front můžeme vidět v našem každodenním životě.

Datová struktura Queue se také řídí stejným principem. Nyní víte, co jsou fronty a jejich princip. Podívejme se na operace, které lze provádět na datové struktuře fronty.

Operace ve frontě

Podobně jako u zásobníku nalezneme v datové struktuře fronty dvě hlavní operace.

zařadit (data)

Přidá nová data do fronty na konci. Strana se nazývá zadní.

dequeue()

Odebere data z přední části fronty. Strana se nazývá přední.

Pro lepší pochopení se podívejme na ilustrace operací fronty. Jeden obrázek mluví za tisíc slov.

Můžeme napsat nějaké pomocné funkce, abychom získali více informací o frontě. Počet pomocných funkcí, které budete mít, není nijak omezen. Zůstaňme zatím u toho nejdůležitějšího, co bylo jednou zmíněno níže.

zadní()

Vrátí první prvek z konce fronty.

přední()

Vrátí první prvek od začátku fronty.

je prázdný()

Vrací, zda je fronta prázdná nebo ne.

Není to pro vás nuda? Mám na mysli koncepční témata.

Za mě ano!

Bez znalosti pojmů však nemůžeme nic dělat. Před realizací to musíme znát. Nebojte se, je čas ušpinit si ruce nějakým kódem.

Předpokládám, že máte na svém PC nainstalovaný python, pokud ne, můžete také vyzkoušet online kompilátor.

Implementace fronty

Implementace fronty nezabere programátorovi déle než 15 minut. Až se to naučíš, řekneš to. Možná to můžete implementovat během několika minut po tomto tutoriálu.

Existuje několik způsobů, jak implementovat frontu v Pythonu. Podívejme se krok za krokem na různé implementace fronty.

#1. Seznam

Seznam je vestavěný datový typ v Pythonu. Datový typ seznamu použijeme k implementaci fronty ve třídě. Provedeme vás různými kroky k implementaci datové struktury fronty od začátku bez jakýchkoli modulů. Pojďme do toho skočit.

Krok 1:

Napište třídu s názvem Queue.

class Queue:
	pass

Krok 2:

Musí existovat nějaká proměnná pro uložení dat fronty ve třídě. Pojmenujme to prvky. A je to samozřejmě seznam.

class Queue:

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

Krok 3:

Pro vložení dat do fronty potřebujeme metodu ve třídě. Tato metoda se nazývá enqueue, jak jsme již probrali v předchozí části tutoriálu.

Metoda vezme nějaká data a přidá je do fronty (prvků). Pro přidání dat na konec fronty můžeme použít metodu append datového typu seznamu.

class Queue:

	# ...

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

Krok 4:

Fronta musí mít východ. A tomu se říká dequeue. Myslím, že jste již uhodli, že použijeme metodu pop datového typu seznamu. Jestli jste uhodli nebo ne, zdravím!

Metoda pop datového typu list odstraní prvek ze seznamu daného indexu. Pokud jsme nezadali žádný index, smaže poslední prvek seznamu.

Zde musíme odstranit první prvek seznamu. Musíme tedy předat index 0 metodě pop.

class Queue:

	# ...

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

To stačí na frontu. Potřebujeme však pomocné funkce, abychom otestovali, zda operace fronty fungují správně nebo ne. Napišme také pomocné funkce.

Krok 5:

K získání posledního prvku fronty se používá metoda zadní (). Negativní indexování v datovém typu seznamu nám pomáhá získat poslední prvek fronty.

class Queue:

	# ...

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

Krok 6:

Metoda front() se používá k získání prvního prvku fronty. První prvek fronty můžeme získat pomocí indexu seznamu.

class Queue:

	# ...

	def front(self):
		return self.elements[0]

Krok 7:

Metoda is_empty() se používá ke kontrole, zda je fronta prázdná nebo ne. Můžeme zkontrolovat délku seznamu.

class Queue:

	# ...

	def is_empty(self):
		return len(self.elements) == 0

Fuj! dokončila implementační část datové struktury fronty. Potřebujeme vytvořit objekt, který bude třída Queue používat.

Pojďme na to.

class Queue:

	# ...

if __name__ == '__main__':
	queue = Queue()

Nyní máme objekt Queue. Pojďme si to otestovat sérií operací.

• Pomocí metody is_empty zkontrolujte, zda je fronta prázdná nebo ne. Mělo by vrátit True.
• Přidejte čísla 1, 2, 3, 4, 5 do fronty pomocí metody enqueue.
• Metoda is_empty by měla vrátit hodnotu False. Zkontroluj to.
• Vytiskněte přední a zadní prvky pomocí přední a zadní metody.
• Odstraňte prvek z fronty pomocí metody dequeue.
• Zkontrolujte přední prvek. Měl by vrátit prvek 2.
• Nyní odstraňte všechny prvky z fronty.
• Metoda is_empty by měla vrátit True. Zkontroluj to.

Myslím, že to stačí k otestování naší implementace fronty. Napište kód pro každý výše uvedený krok a otestujte frontu.

Napsal jsi kód?

Ne, nebojte se.

Zkontrolujte kód níže.

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

Myslím, že spouštíte výše uvedený program. Můžete získat výstup podobný následujícímu výsledku.

True
False
1 5
2 5
True

Datový typ seznamu můžeme přímo použít jako datovou strukturu fronty. Výše uvedená implementace fronty vám pomůže lépe porozumět implementaci fronty v jiných programovacích jazycích.

Můžete také použít výše uvedenou třídu implementace fronty v jiném programu projektu jednoduchým vytvořením objektu jako dříve.

Implementovali jsme frontu od začátku pomocí datového typu seznamu. Existují nějaké vestavěné moduly pro frontu? To jo! máme vestavěné implementace fronty. Pojďme se na ně podívat.

#2. deque ze sbírek

Je implementován jako dvojitá fronta. Protože podporuje přidávání a odebírání prvků z obou konců, můžeme jej použít jako zásobník a frontu. Podívejme se na implementaci fronty pomocí dequeue.

Je implementován pomocí jiných datových struktur nazývaných dvojitě propojený seznam. Výkon vkládání a mazání prvků je tedy konzistentní. Přístup k prvkům z prostředního propojeného seznamu trval O(n) čas. Můžeme ji použít jako frontu, protože není potřeba přistupovat k prostředním prvkům z fronty.

Pojďme se podívat na různé metody, které nám dequeue nabízí.

• append(data) – používá se k přidání dat do fronty
• popleft() – používá se k odstranění prvního prvku z fronty

Neexistují žádné alternativní metody pro přední, zadní a is_empty. Můžeme vytisknout celou frontu místo přední a zadní metody. Dále můžeme pomocí metody len zkontrolovat, zda je fronta prázdná nebo ne.

Sledovali jsme řadu kroků k testování implementace fronty v předchozím. Pokračujme stejnou řadou kroků i zde.

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)

Dostanete výsledek podobný následujícímu výstupu.

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

#3. Fronta z fronty

Python má vestavěný modul nazvaný queue, který slouží třídě nazvané Queue pro implementaci fronty. Je podobný tomu, který jsme implementovali dříve.

Nejprve se podívejme na různé metody třídy Queue.

• put(data) – přidá nebo přesune data do fronty
• get() – odstraní první prvek z fronty a vrátí jej
• empty() – vrátí, zda je zásobník prázdný nebo ne
• qsize() – vrátí délku fronty.

Pojďme implementovat frontu výše uvedenými metodami.

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

Zkontrolujte výstup výše uvedeného kódu.

True
False
1
2
3
Size 2
4
5
True

Ve třídě Queue jsou některé další metody. Můžete je prozkoumat pomocí vestavěné funkce dir.

Závěr

Doufám, že jste se dozvěděli o datové struktuře fronty a její implementaci. To je vše pro frontu. Frontu můžete použít na různých místech, kde je potřeba zpracovat v pořadí FIFO (First In/First Out). Použijte frontu při řešení problémů, kdykoli dostanete případ k použití.

Máte zájem ovládat Python? Podívejte se na tyto výukové zdroje.

Veselé kódování 🙂 👨‍💻