Podobne ako zásobník, aj front je lineárna dátová štruktúra, ktorá ukladá položky do položky First In First Out ( FIFO ) spôsobom. Pri fronte sa najskôr odstráni najmenej nedávno pridaná položka. Dobrým príkladom radu je každý rad spotrebiteľov pre zdroj, kde je prvý obsluhovaný spotrebiteľ, ktorý prišiel ako prvý.

Operácie spojené s frontom sú:

• Zaradiť do poradia: Pridá položku do frontu. Ak je front plný, hovorí sa, že ide o stav pretečenia – časová zložitosť: O(1)
• Podľa toho: Odstráni položku z frontu. Položky sa vyskakujú v rovnakom poradí, v akom sa tlačia. Ak je front prázdny, potom sa hovorí, že ide o podmienku podtečenia – časová zložitosť: O(1)
• Predná časť: Získajte prednú položku z frontu – Časová zložitosť: O(1)
• zadná časť: Získajte poslednú položku z frontu – Časová zložitosť: O(1)

Implementujte front v Pythone

Existujú rôzne spôsoby implementácie frontu Python. Tento článok popisuje implementáciu frontu pomocou dátových štruktúr a modulov z knižnice Python. Python Queue je možné implementovať nasledujúcimi spôsobmi:

• zoznam
• zbierky.deque
• chvost.chvost

Implementácia pomocou zoznamu

Zoznam je vstavaná dátová štruktúra Pythonu, ktorú možno použiť ako front. Namiesto enqueue() a podľa toho () , pripojiť () a pop() používa sa funkcia. Zoznamy sú však na tento účel dosť pomalé, pretože vloženie alebo odstránenie prvku na začiatku vyžaduje posunutie všetkých ostatných prvkov o jeden, čo si vyžaduje čas O(n).
Kód simuluje front pomocou zoznamu Python. Pridáva prvky „a“ , „b“ , a „c“ do frontu a potom ich vyradí z radu, výsledkom čoho je na konci prázdny rad. Výstup zobrazuje počiatočný front, vyradené prvky ( „a“ , „b“ , „c“ ) a stav frontu je prázdny.

Python3

Výkon:

Initial queue ['a', 'b', 'c'] Elements dequeued from queue a b c Queue after removing elements [] 

Traceback (most recent call last):  File '/home/ef51acf025182ccd69d906e58f17b6de.py', line 25, in   print(queue.pop(0)) IndexError: pop from empty list 

Implementácia pomocou collections.deque

Fronta v Pythone môže byť implementovaná pomocou triedy deque z modulu kolekcií. Deque sa uprednostňuje pred zoznamom v prípadoch, keď potrebujeme rýchlejšie operácie pripojenia a pop z oboch koncov kontajnera, pretože deque poskytuje časovú zložitosť O(1) pre operácie pripojenia a pop v porovnaní so zoznamom, ktorý poskytuje časovú zložitosť O(n). . Namiesto enqueue a deque sa používajú funkcie append() a popleft().
Kód používa a deque> z collections> modul reprezentujúci front. Pripája sa „a“ , „b“ , a „c“ do frontu a vyradí ich z poradia q.popleft()> , výsledkom čoho je prázdny rad. Odkomentovanie q.popleft()> po vyprázdnení frontu by sa zvýšilo an IndexError> . Kód demonštruje operácie frontu a spracováva scenár prázdneho frontu.

Python3

Výkon:

Initial queue deque(['a', 'b', 'c']) Elements dequeued from the queue a b c Queue after removing elements deque([]) 

Traceback (most recent call last):  File '/home/b2fa8ce438c2a9f82d6c3e5da587490f.py', line 23, in   q.popleft() IndexError: pop from an empty deque 

Implementácia pomocou queue.Queue

Queue je vstavaný modul Pythonu, ktorý sa používa na implementáciu frontu. queue.Queue(maxsize) inicializuje premennú na maximálnu veľkosť maxsize. Maximálna veľkosť nula „0“ znamená nekonečný rad. Táto fronta sa riadi pravidlom FIFO.
V tomto module sú k dispozícii rôzne funkcie:

• maxsize – Počet povolených položiek vo fronte.
• prázdne () – Ak je front prázdny, vráťte hodnotu True, inak hodnotu False.
• plný() – Vráťte hodnotu True, ak sú vo fronte položky maximálnej veľkosti. Ak bol front inicializovaný s maxsize=0 (predvolená hodnota), full() nikdy nevráti True.
• dostať () – Odstráňte a vráťte položku z frontu. Ak je front prázdny, počkajte, kým bude položka k dispozícii.
• get_nowait() – Vráťte položku, ak je okamžite dostupná, inak zvýšte QueueEmpty.
• vložiť (položka) – Zaraďte položku do frontu. Ak je front plný, pred pridaním položky počkajte, kým sa neuvoľní voľné miesto.
• put_nowait(položka) – Zaraďte položku do frontu bez blokovania. Ak nie je okamžite k dispozícii žiadny voľný slot, zvýšte QueueFull.
• qsize() – Vráti počet položiek vo fronte.

Príklad: Tento kód využíva Queue> triedy z queue> modul. Začína sa prázdnym radom a naplní sa „ a’, „b“ , a „c“ . Po vyradení z radu sa front vyprázdni a pridá sa „1“. Napriek tomu, že bol predtým prázdny, zostáva plný, pretože maximálna veľkosť je nastavená na 3. Kód demonštruje operácie frontu vrátane kontroly plnosti a prázdnoty.

Python3

Výkon:

0 Full: True Elements dequeued from the queue a b c Empty: True Empty: False Full: False