Frontu možno opísať ako neprirodzená štruktúra lineárnych údajov, ktorá sa riadi poradím FIFO, v ktorom sú údaje dátové prvky vložené z jedného konca (zadný koniec) a vymazané z druhého konca (predný koniec). Ostatné varianty frontu sú kruhová fronta, dvojitá koncová fronta a prioritná fronta.
Porovnávacia tabuľka
| Základ pre porovnanie | Lineárna fronta | Kruhová fronta |
|---|---|---|
| základné | Organizuje dátové prvky a pokyny v postupnom poradí jeden po druhom. | Usporiada údaje v kruhovom vzore, kde je prvý prvok pripojený k prvému prvku. |
| Poradie vykonávania úlohy | Úlohy sa vykonávajú, aby boli umiestnené pred (FIFO). | Poradie vykonávania úlohy sa môže zmeniť. |
| Vloženie a vymazanie | Nový prvok je pridaný z zadného konca a vyťahovaný z prednej strany. | Vloženie a odstránenie sa môže vykonať na ľubovoľnej pozícii. |
| výkon | neefektívne | Funguje lepšie ako lineárna fronta. |
Definícia lineárneho frontu
Lineárny rad je racionálne prvý v prvom zozname. Je to tzv. Lineárny, pretože sa podobá priamke, kde sú prvky umiestnené jeden po druhom. Obsahuje homogénny zber prvkov, v ktorých sú na jednom konci pridané nové prvky a odstránené z iného konca. Koncept frontu možno pochopiť na príklade frontu publika, ktorý čaká mimo vstupenky, aby získal vstupenku do divadla. V tomto rade sa osoba pripojí na zadnú časť frontu, aby vzala lístok a lístok sa vydáva na prednej strane frontu.
V rade je vykonaných niekoľko operácií
- Najskôr sa fronta inicializuje na nulu (tj prázdne).
- Určite, či je fronta prázdna alebo nie.
- Určte, či je fronta plná alebo nie.
- Vloženie nového prvku zo zadného konca (Enqueue).
- Vymazanie prvku z predného konca (Dequeue).
Riadok môže byť implementovaný dvoma spôsobmi
- Staticky (pomocou polí)
- Dynamicky (pomocou ukazovateľov)
Obmedzenie lineárneho poradia spočíva v tom, že vytvára scenár, v ktorom nemôže byť vo fronte pridaný žiadny nový prvok, aj keď fronta obsahuje prázdne medzery. Táto situácia je ilustrovaná na nižšie uvedenom obrázku. Tu zadná strana smeruje na posledný index, zatiaľ čo všetky políčka sú prázdne, nemožno pridávať žiadny nový prvok.
Definícia okrúhleho frontu
Kruhová fronta je variantom lineárneho frontu, ktorý účinne prekonáva obmedzenie lineárneho radu. V kruhovom rade sa nový prvok pridáva na prvú pozíciu frontu, ak je posledná obsadená a je k dispozícii priestor. Pokiaľ ide o lineárnu frontu, vkladanie môže byť vykonané iba zo zadného konca a vymazanie z predného konca. V plnej fronte po vykonaní sérií postupných vymazaní vo fronte vzniká určitá situácia, kedy sa nemôže pridávať žiadny nový prvok ani vtedy, ak je dostupný priestor, pretože stále existuje podmienka spodného toku (Rear = max - 1).
Kruhová fronta spája oba konce cez ukazovateľ, v ktorom prvý prvok prichádza po poslednom prvku. Takisto udržuje prehľad o prednej a zadnej časti implementáciou nejakej extra logiky, aby mohla sledovať prvky, ktoré sa majú vložiť a vymazať. Týmto sa okrúhla fronta nevygeneruje stav pretečenia, kým fronta nie je plná.
Niektoré podmienky nasledujú po kruhovej fronte:
- Predná časť musí smerovať na prvý prvok.
- Riadok bude prázdny, ak je Front = Rear.
- Keď sa pridá nový prvok, fronta sa zvýši o hodnotu jedna (Zadná strana = Zadná strana + 1).
- Keď sa prvok vymaže z frontu, front sa zvýši o jednu (Front = Front + 1).
Kľúčové rozdiely medzi lineárnym frontom a okrúhlym frontom
- Lineárna fronta je usporiadaný zoznam, v ktorom sú dátové prvky organizované v postupnom poradí. Na rozdiel od toho, kruhová fronta ukladá dáta kruhovým spôsobom.
- Lineárna fronta sleduje objednávku FIFO na vykonanie úlohy (prvok pridaný v prvej pozícii bude vymazaný v prvej pozícii). Naopak, v kruhovom rade sa môže zmeniť poradie operácií vykonávaných na prvku.
- Vloženie a vymazanie prvkov je fixované v lineárnom fronte, tj doplnenie zo zadného konca a vymazanie z predného konca. Na druhej strane je kruhová fronta schopná vkladať a odstraňovať prvok z akéhokoľvek miesta, kým nie je obsadený.
- Lineárny front stráca pamäťový priestor, kým okruhová fronta umožňuje efektívne využitie priestoru.
Implementácia lineárneho radu
Nižšie uvedený algoritmus ilustruje pridanie prvkov do frontu:
Riadok potrebuje tri dátové premenné vrátane jedného poľa na uloženie frontu a ďalšie na uloženie prednej a zadnej východiskovej pozície, ktorá je -1.
vložiť (položka, fronta, n, zadná) {if (zadná == n) potom vytlačiť "pretečenie frontu"; iný {zadný = zadný + 1; fronta [zadná] = položka; }} Nižšie uvedený algoritmus ilustruje vymazanie prvkov vo fronte:
delete_circular (položka, fronta, zadná strana, predná strana) {if (zadná == predná strana) potom vytlačiť "podfond fronty"; inak {front = front + 1; položka = front [front]; }} Implementácia kruhového frontu
Algoritmus interpretácie pridania prvku do kruhového frontu:
insert_circular (položka, fronta, zadná, predná strana) {rear = (zadná + 1) mod n; ak (predná = = zadná) potom tlač "fronta je plná"; inak {queue [rear] = položka; }} Algoritmus vysvetľuje vymazanie prvku v kruhovom rade:
delete_circular (položka, fronta, zadná strana, predná strana) {if (predná = = zadná) a potom vytlačiť ("fronta je prázdna"); inak {front = front + 1; položka = front [front]; }} záver
Lineárna fronta je neefektívna v určitých prípadoch, keď sú prvky potrebné premiestniť do prázdnych priestorov, aby vykonali operáciu vkladania. To je dôvod, prečo má tendenciu plytvať úložným priestorom, zatiaľ čo okrúhla fronta vhodne využíva úložný priestor, pretože prvky sú pridané v ľubovoľnej polohe, ak existuje prázdny priestor.
