Fronta

Fronta je užitečná datová struktura v programování. Je podobná frontě na lístky před kinosálem, kde první osoba, která vstoupí do fronty, dostane lístek jako první.

Fronta se řídí pravidlem FIFO (First In First Out) – položka, která je vložena jako první, je zároveň položkou, která je nejdříve vyjmuta.

Základní operace fronty

Enqueue: Přidání prvku na konec fronty

Dequeue: Odebrání prvku z čela fronty

IsEmpty: Zkontroluje, zda je fronta prázdná

IsFull: Zjistí, zda je fronta plná.

Peek: Zjistí hodnotu přední části fronty, aniž by ji odstranil.

Fronta má ukazatele front, který ukazuje na první prvek fronty.
Na začátku nastavte hodnotu front na NULL.

Implementace fronty a inicializace zásobníku

Frontu můžeme implementovat jako jednosměrně zřetězený seznam pomocí struktury.
Ukazatel na QueueNode (prvek fronty) front definujeme pro jednoduchost jako globální proměnné.

Funkce enqueue

Parametr funkce:

Hodnota, kterou chceme do fronty vložit.

Vytvoříme si novou dynamickou proměnnou typu QueueNode:

V této struktuře uložíme do proměnné data hodnotu, kterou vkládáme,
do ukazatele next vložíme NULL (tento nový prvek je poslední ve frontě).

Pokud vkládáme první prvek, tak

ukazatel front ukazuje na tento nový prvek.

Pokud nevkládáme první prvek, tak

nový prvek se stává nástupcem posledního,
nový prvek se stává posledním prvkem.

Funkce isEmpty

Vrací, zda je ukazatel front NULL, nebo ne.

Funkce dequeue

Pokud je fronta prázdná, tak nedělej nic.

Pokud fronta není prázdná, tak

si do pomocné dynamické proměnné uložíme první prvek fronty,
ukazatel front bude ukazovat na původně druhý prvek fronty,
zlikvidujeme pomocnou proměnnou.

Funkce peek

Pokud fronta není prázdná, tak vrátíme hodnotu prvního prvku.

Pokud je fronta prázdná, tak vrátíme -1.

Funkce deleteQueue

Dokud fronta není prázdná, tak provádíme dequeue.

Page updated

Report abuse