6. Rad

6.1 Čo je to?

Rad (front, queue) je taký lineárny zoznam, na ktorom sú definované iba tieto operácie:

• vytvoriť prázdny rad
• pridať nový prvok na koniec radu
• odobrať prvok zo začiatku radu
• zistiť, či je rad prázdny

Operácia „vlož prvok do frontu“ sa niekedy v literatúre označuje enter. Operácia „vyber prvok z frontu“ sa nazýva remove.

Rad sa v praxi spravidla implementuje ako lineárny zoznam. Implementácia pomocou poľa je síce možná, ale veľmi nevýhodná. Operácia odober zo začiatku si vyžaduje posun ostatných prvkov o jedno miesto vľavo. V prípade, že nechceme pole posúvať, môžeme si síce pamätať index prvku, ktorý je na začiatku a index prvku na konci frontu, ale prvky, ktoré sa už z frontu „odstránili,“ sú zbytočne stále uložené v poli. Navyše by sme museli veľkosť frontu vopred vymedziť veľkosťou použitého poľa.

Graficky sa front implementovaný ako jednosmerný lineárny zoznam znázorňuje väčšinou takto:

h1, h2, h3, …, hn sú hodnoty prvkov vo fronte   pointer z ukazuje na začiatok frontu pointer k ukazuje na koniec frontu

Princíp, podľa ktorého sa najskôr vložený prvok odstráni z radu ako prvý, sa nazýva princíp FIFO (z angl. First In First Out – „prvý príde, prvý odíde“).   Rad sa preto nazýva aj pamäť FIFO.

V programoch sa často používajú niektoré špeciálne druhy radov, ktoré sa správajú trochu inak. Medzi najpoužívanejšie patrí
 
dvojitý front – ktorý umožňuje pridávať a odoberať prvky z oboch koncov (analógia bežného radu zo života – na začiatok prichádzajú prominenti, koniec opúšťajú tí, ktorí už nemôžu čakať)
 
front s predbiehaním do ktorého sa nový prvok zaraďuje podľa priority (dôležitosti)

Precvičme si