V informatike je rad lineárna dátová štruktúra, kde sú komponenty umiestnené na jednom konci a odstránené z druhého konca podľa princípu „first-in, first-out“ (FIFO). Táto dátová štruktúra môže byť použitá na riadenie akčnej sekvencie alebo ukladanie dát. C je počítačový jazyk s funkciou frontu zabudovanou vo forme polí alebo prepojených zoznamov.
Charakteristika:
- Front je typ lineárnej dátovej štruktúry, ktorú možno vytvoriť pomocou poľa alebo prepojeného zoznamu.
- Prvky sú premiestnené do zadnej časti frontu, zatiaľ čo sú odstránené spredu.
- Zaradiť do radu (pridať prvok dozadu) a vyradiť z radu (odstrániť prvok spredu) sú dve operácie radu.
- Pri častom pridávaní a odstraňovaní prvkov môže byť rad vytvorený ako kruhový, aby sa zabránilo plytvaniu pamäťou.
Použitie poľa:
Ak chcete implementovať front v C pomocou poľa, najprv definujte maximálnu veľkosť frontu a deklarujte pole tejto veľkosti. Predné a zadné celé číslo boli nastavené na 1. Predná premenná predstavuje predný prvok frontu a zadná premenná predstavuje zadný prvok.
Pred zatlačením nového prvku na konečnú pozíciu frontu musíme zvýšiť premennú back o 1. Front je teraz plný a nie je možné pridať žiadne ďalšie prvky, keď zadná pozícia dosiahne maximálnu kapacitu frontu. Pridáme prvok na začiatok frontu a zväčšíme prednú premennú o jednu iba na odstránenie prvku z frontu. Ak sú predné a zadné pozície rovnaké a nie je možné vymazať žiadne ďalšie komponenty, môžeme povedať, že front je prázdny.
Nižšie je uvedený príklad frontu napísaného v jazyku C, ktorý využíva pole:
Programovací jazyk C:
#define MAX_SIZE 100 int queue[MAX_SIZE]; int front = -1; int rear = -1; void enqueue(int element) { if (rear == MAX_SIZE - 1) { printf('Queue is full'); return; } if (front == -1) { front = 0; } rear++; queue[rear] = element; } int dequeue() { if (front == -1 || front > rear) { printf('Queue is empty'); return -1; } int element = queue[front]; front++; return element; } int main() { enqueue(10); enqueue(20); enqueue(30); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); return 0; } Výstupom kódu bude:
Výkon:
10 20 30 Queue is empty-1
Vysvetlenie:
- Najprv zaradíme do radu tri prvky 10, 20 a 30.
- Potom vyradíme a vytlačíme predný prvok frontu, ktorým je 10.
- Ďalej vyradíme z frontu a znova vytlačíme predný prvok frontu, čo je 20.
- Potom znova vyradíme a vytlačíme predný prvok frontu, čo je 30.
- Nakoniec vytvoríme dequeue z prázdneho frontu, ktorý vypíše 'Queue is empty' a vráti -1.
Použitie prepojeného zoznamu:
Ďalším alternatívnym prístupom k zostaveniu frontu v programovacom jazyku C je použitie prepojeného zoznamu. Každý z uzlov vo fronte je pomocou tejto metódy vyjadrený uzlom, ktorý obsahuje hodnotu prvku a ukazovateľ na nasledujúci uzol vo fronte. Aby bolo možné sledovať prvý a posledný uzol vo fronte, používajú sa predné a zadné ukazovatele.
Vytvoríme nový uzol s hodnotou prvku a nastavíme jeho ďalší ukazovateľ na NULL, aby sme pridali prvok do frontu. Na nový uzol nastavíme predný a zadný ukazovateľ, ak je front prázdny. Ak nie, aktualizujeme zadný ukazovateľ a nastavíme ďalší ukazovateľ starého zadného uzla tak, aby ukazoval na nový uzol.
Pri odstraňovaní uzla z frontu sa najprv vymaže predchádzajúci uzol, potom sa predný ukazovateľ aktualizuje na nasledujúci uzol vo fronte a nakoniec sa uvoľní pamäť, ktorú odstránený uzol zaberal. Ak má predný ukazovateľ po odstránení hodnotu NULL, front je prázdny.
Tu je príklad fronty implementovanej v C pomocou prepojeného zoznamu:
Programovací jazyk C:
#include #include struct Node { int data; struct Node* next; }; struct Node* front = NULL; struct Node* rear = NULL; void enqueue(int element) { struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); new_node->data = element; new_node->next = NULL; if (front == NULL && rear == NULL) { front = rear = new_node; return; } rear->next = new_node; rear = new_node; } int dequeue() { if (front == NULL) { printf('Queue is empty'); return -1; } struct Node* temp = front; int element = temp->data; if (front == rear) { front = rear = NULL; } else { front = front->next; } free(temp); return element; } int main() { enqueue(10); enqueue(20); enqueue(30); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); return 0; } Výstupom kódu bude:
Výkon:
10 20 30 Queue is empty-1
Vysvetlenie:
- Najprv zaradíme do radu tri prvky 10, 20 a 30.
- Potom vyradíme a vytlačíme predný prvok frontu, ktorým je 10.
- Ďalej vyradíme z frontu a znova vytlačíme predný prvok frontu, čo je 20.
- Potom znova vyradíme a vytlačíme predný prvok frontu, čo je 30.
- Nakoniec sa pokúsime o vyradenie z prázdneho frontu, čo vypíše správu 'Queue is empty' a vráti -1.
Výhody:
- Fronty sú užitočné najmä pri implementácii algoritmov, ktoré vyžadujú spracovanie prvkov v presnom poradí, ako je vyhľadávanie na šírku a plánovanie úloh.
- Pretože operácie vo fronte majú časovú zložitosť O(1), môžu sa vykonávať rýchlo aj v obrovských frontoch.
- Fronty sú obzvlášť flexibilné, pretože môžu byť jednoducho implementované pomocou poľa alebo prepojeného zoznamu.
Nevýhody:
- Front, na rozdiel od zásobníka, nemôže byť skonštruovaný s jedným ukazovateľom, čo robí implementáciu frontu o niečo zložitejšou.
- Ak je front vytvorený ako pole, môže sa čoskoro zaplniť, ak sa pridá príliš veľa prvkov, čo môže viesť k problémom s výkonom alebo možno k zlyhaniu.
- Pri použití prepojeného zoznamu na implementáciu frontu môže byť réžia pamäte každého uzla významná, najmä pre malé prvky.
Záver:
Aplikácie, ktoré používajú fronty, kľúčovú dátovú štruktúru, zahŕňajú operačné systémy, siete a hry, aby sme vymenovali len niektoré. Sú ideálne pre algoritmy, ktoré musia spracovávať prvky v určitom poradí, pretože sa dajú jednoducho vytvoriť pomocou poľa alebo prepojeného zoznamu. Fronty však majú nevýhody, ktoré treba brať do úvahy pri výbere dátovej štruktúry pre konkrétnu aplikáciu, ako je spotreba pamäte a zložitosť implementácie.