Fronta (queue)

Fronta (queue alebo aj rad) funguje presne ako rad v supermarkete pri pokladni. Nový zákazník sa vždy postaví na koniec radu, a pokladníčka vždy obslúži toho, kto je na začiatku. Okrem toho máme k dispozícii ešte jednu operáciu -- môžeme sa pozrieť na to, kto je na začiatku. V súvislosti s frontou sa môžeme stretnúť aj s názvom FIFO -- "First In, First Out", čiže "prvý dnu, prvý von" (pretože zákazník, ktorý sa do radu postavil ako prvý, bude aj prvý obslúžený).

queue

Fronta má, podobne ako zásobník, mnoho využití. Môžeme si ňou pomôcť napríklad pri implementovaní správania sieťovej tlačiarne -- tá zvláda tlačiť len nejaké množstvo strán za sekundu (povedzme jednu), ale pritom jej môže prikázať tlačiť mnohostranné dokumenty hneď za sebou niekoľko používateľov. V takom prípade si tlačiareň ukladá nové dokumenty do fronty a keď dotlačí to, čo mala začaté, pustí sa vždy do toho dokumentu, ktorý čakal najdlhšie (čiže do toho, ktorý prišiel prvý).

Fronta je abstraktná dátová štruktúra. Podporuje nasledovné operácie:

  • pridať prvok (na koniec),
  • odobrať prvok (zo začiatku),
  • pozrieť sa na prvý prvok.

Pamäťová zložitosť fronty je $n$. Časové zložitosti jednotlivých operácií sú rovnaké -- $O(1)$.

Implementácia

V Pythone môžeme implementovať frontu pomocou knižnice deque z modulu collections. Táto knižnica implementuje obojsmernú frontu (deque), o ktorej si povieme viac v ďalšej lekcií, ale možno ju použiť aj na implementáciu bežnej fronty. Tu sú základné operácie:

Pridanie prvku na koniec fronty (enqueue)

Pre pridanie nového prvku do fronty použijeme metódu .append().

from collections import deque

queue = deque()
queue.append("mobil")  # pridáme prvok na koniec
queue.append("pocitac")

Odstránenie prvku zo začiatku fronty (dequeue)

Na odobratie vrchného prvku z fronty použijeme metódu .popleft(). Táto metóda nielenže prvok odstráni, ale ho aj vráti.

prvok = queue.popleft()
print(prvok)  # výstup: mobil

Podobne ako pri zásobníku, ak sa pokúsime odobrať prvok z prázdnej fronty, Python vyvolá chybu IndexError. Preto je dobré skontrolovať, či nie je fronta pred odobratím prázdna (napríklad pomocou funkcie len). Podobne ako pri zásobníku možno spraviť aj niečo takéto:

if queue:
    # Fronta nie je prázdna

if not queue:
    # Fronta je prázdna

Nahliadnutie na vrchný prvok (peek)

Ak chceme len zistiť, aký prvok je na začiatku fronty bez toho, aby sme ho odstránili, jednoducho pristúpime k prvému prvku fronty. V Pythone to dosiahneme pomocou indexu 0.

print(queue[0])  # výstup: pocitac

Pred prístupom k indexu 0 je však dobré vždy skontrolovať, či fronta nie je prázdna. Ak by bola prázdna a pokúsili by ste sa o prístup, opäť by to viedlo k chybe IndexError.

Prečo nestačí list?

Na implementáciu fronty možno použiť list, ale nie je to efektívne. Metóda list.pop(0) síce odstraňuje prvok zo začiatku, ale musí presunúť všetky ostatné prvky o jedno miesto vľavo, čo má časovú zložitosť O(n). Naopak deque z collections umožňuje operáciu popleft() v O(1).

Ďalej