V oblasti programování hrají klíčovou úlohu datové struktury. Umožňují nám organizovat data tak, aby byla efektivně využitelná. Jednou z nejzákladnějších datových struktur je fronta.
Tento článek vás seznámí s konceptem fronty a ukáže vám, jak ji implementovat v jazyce Python.
Co je to fronta?
Fronta je lineární datová struktura, která se řídí principem „První dovnitř, první ven“ (FIFO – First In/First Out). Funguje na opačném principu než datová struktura zásobník.
Pro lepší představu si můžeme frontu přirovnat k reálné frontě u pokladny v kině. Podívejme se na následující ilustraci:
V takové frontě u přepážky obslouží pokladník druhého zákazníka až poté, co dokončí obsluhu prvního. Zákazníci přicházejí v pořadí, v jakém se zařadili do fronty. Je zde uplatněn princip FIFO – kdo dřív přijde, ten dřív bude obsloužen. S podobnými frontami se setkáváme v běžném životě.
Datová struktura fronta se řídí stejným pravidlem. Nyní už tedy víte, co je fronta a jak funguje. Pojďme se podívat na operace, které můžeme s touto strukturou provádět.
Operace s frontou
Stejně jako u zásobníku, i u fronty se setkáváme se dvěma základními operacemi:
Vložit (data)
Tato operace přidává nová data na konec fronty. Tento konec se nazývá zadní (rear).
Odebrat()
Tato operace odebírá data z přední části fronty. Tento konec se nazývá přední (front).
Pro lepší pochopení si ukážeme ilustrace operací s frontou. Jeden obrázek totiž řekne více než tisíc slov.
Kromě těchto základních operací můžeme definovat i pomocné funkce pro získání dalších informací o frontě. Počet těchto pomocných funkcí není nijak omezen, my se však zaměříme na ty nejdůležitější:
Zadní()
Tato funkce vrací prvek na konci fronty.
Přední()
Tato funkce vrací prvek na začátku fronty.
Je prázdná()
Tato funkce vrací informaci o tom, zda je fronta prázdná.
Možná už se nudíte těmito teoretickými informacemi, ale je nutné si je ujasnit před implementací. Bez toho se dále nepohneme. Nemusíte se ale bát, brzy se podíváme i na kód.
Předpokládám, že máte na počítači nainstalovaný Python. Pokud ne, můžete si ho vyzkoušet v online kompilátoru.
Implementace fronty
Implementace fronty by programátorovi neměla zabrat déle než 15 minut. Až se ji naučíte, sami to potvrdíte. Možná ji po tomto tutoriálu dokážete implementovat i během několika minut.
Existuje několik způsobů, jak implementovat frontu v Pythonu. Pojďme se na ně podívat krok za krokem.
#1. Seznam
Seznam (list) je vestavěný datový typ v Pythonu. Použijeme ho k implementaci fronty uvnitř třídy. Projdeme si krok za krokem různé způsoby implementace datové struktury fronty od začátku, bez použití externích modulů. Pusťme se do toho.
Krok 1:
Vytvoříme třídu s názvem Queue.
class Queue:
pass
Krok 2:
Ve třídě potřebujeme proměnnou pro ukládání dat fronty. Nazvěme ji `elements`. Samozřejmě to bude seznam.
class Queue:
def __init__(self):
self.elements = []
Krok 3:
Pro vkládání dat do fronty potřebujeme metodu. Tato metoda se nazývá `enqueue`, jak jsme si již řekli. Metoda převezme data a přidá je do fronty (seznamu `elements`). K přidání dat na konec seznamu můžeme použít metodu `append` datového typu seznam.
class Queue:
# ...
def enqueue(self, data):
self.elements.append(data)
return data
Krok 4:
Fronta musí mít také metodu pro odebírání dat. Ta se nazývá `dequeue`. Tušíte správně, použijeme metodu `pop` datového typu seznam. Pokud jste to uhodli, gratuluji!
Metoda `pop` odstraní prvek ze seznamu na zadaném indexu. Pokud index nezadáme, odstraní poslední prvek seznamu. My však potřebujeme odstranit první prvek, takže metodě `pop` předáme index 0.
class Queue:
# ...
def dequeue(self):
return self.elements.pop(0)
To stačí pro základní frontu. Potřebujeme ale ještě pomocné metody, abychom mohli otestovat, zda operace s frontou fungují správně. Pojďme je tedy napsat.
Krok 5:
K získání posledního prvku fronty slouží metoda `zadní()`. Negativní indexování v datovém typu seznam nám pomůže získat poslední prvek.
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 získáme pomocí indexu seznamu.
class Queue:
# ...
def front(self):
return self.elements[0]
Krok 7:
Metoda `is_empty()` slouží ke kontrole, zda je fronta prázdná. Můžeme zkontrolovat délku seznamu.
class Queue:
# ...
def is_empty(self):
return len(self.elements) == 0
Uf, to je z implementace datové struktury fronty vše. Teď potřebujeme vytvořit objekt, který bude třídu `Queue` používat.
Pojďme na to.
class Queue:
# ...
if __name__ == '__main__':
queue = Queue()
Nyní máme objekt `Queue`. Otestujme jej sérií operací:
- Pomocí metody `is_empty` zkontrolujte, zda je fronta prázdná. Mělo by se vrátit `True`.
- Přidejte do fronty čísla 1, 2, 3, 4, 5 pomocí metody `enqueue`.
- Metoda `is_empty` by nyní měla vrátit `False`. Ověřte to.
- Vypište první a poslední prvek fronty pomocí metod `front` a `rear`.
- Odeberte prvek z fronty pomocí metody `dequeue`.
- Zkontrolujte první prvek fronty. Měla by se vrátit hodnota 2.
- Nyní odeberte všechny prvky z fronty.
- Metoda `is_empty` by nyní měla vrátit `True`. Zkontrolujte to.
Myslím, že toto stačí k otestování naší implementace fronty. Napište kód pro každý uvedený krok a otestujte frontu.
Napsali jste kód?
Nevadí, pokud ne.
Podívejte se na 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())
Pokud jste spustili výše uvedený kód, měli byste dostat podobný výstup:
True False 1 5 2 5 True
Datový typ seznam můžeme použít přímo jako datovou strukturu fronty. Výše uvedená implementace fronty vám pomůže lépe pochopit, jak fronta funguje v jiných programovacích jazycích.
Tuto třídu `Queue` můžete jednoduše použít i v jiném projektu, stačí vytvořit její objekt, jak jsme si ukázali.
Implementovali jsme frontu od začátku pomocí datového typu seznam. Existují ale i vestavěné moduly pro práci s frontou? Ano, samozřejmě! Máme vestavěné implementace fronty. Pojďme se na ně podívat.
#2. `deque` z modulu `collections`
Implementuje se jako oboustranná fronta. Protože umožňuje přidávat a odebírat prvky z obou konců, můžeme ji použít i jako zásobník. Podívejme se na implementaci fronty pomocí `deque`.
Implementuje se pomocí jiné datové struktury, takzvaného obousměrně vázaného seznamu. Vkládání a mazání prvků je tedy časově konzistentní. Přístup k prvkům z prostředka takového seznamu je časově náročný O(n). Protože u fronty nepotřebujeme přistupovat k prvkům uprostřed, můžeme `deque` použít jako frontu.
Pojďme se podívat na různé metody, které nám `deque` nabízí:
- `append(data)` – slouží k přidání dat do fronty
- `popleft()` – slouží k odstranění prvního prvku z fronty
Neexistují žádné alternativní metody pro `přední`, `zadní` a `je_prázdná`. Místo metod `přední` a `zadní` můžeme vypsat celou frontu. A pro kontrolu, zda je fronta prázdná, můžeme použít metodu `len`.
V předchozím jsme testovali implementaci fronty sérií kroků. Použijeme stejnou sérii 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)
Měli byste dostat výstup podobný tomuto:
True False deque([1, 2, 3, 4, 5]) deque([2, 3, 4, 5]) True
#3. `Queue` z modulu `queue`
Python má vestavěný modul `queue`, který obsahuje třídu s názvem `Queue` pro implementaci fronty. Funguje podobně jako ta, kterou jsme implementovali předtím.
Nejprve se podívejme na různé metody třídy `Queue`:
- `put(data)` – přidá data do fronty
- `get()` – odstraní první prvek z fronty a vrátí ho
- `empty()` – vrátí informaci, zda je fronta prázdná
- `qsize()` – vrátí délku fronty
Pojďme implementovat frontu pomocí výše uvedených metod:
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
Třída `Queue` má i další metody. Můžete je prozkoumat pomocí vestavěné funkce `dir`.
Závěr
Doufám, že jste se dozvěděli něco o datové struktuře fronty a její implementaci. To je pro frontu vše. Frontu můžete použít všude tam, kde je potřeba zpracovávat data v pořadí FIFO (First In/First Out). Používejte ji vždy, když narazíte na problém, který to vyžaduje.
Zajímá vás Python? Podívejte se na následující zdroje pro výuku:
Šťastné kódování 🙂 👨💻