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