Rad (záznam on-line prednášky pre externistov)

Zhrnutie prednášky

Prednáška zavádza dátovú abstrakciu rad (anglicky queue, česky fronta), ktorá pracuje na princípe FIFO – prvok sa vkladá na koniec a vyberá zo začiatku radu. Rad sa implementuje pomocou rekurzívnych štruktúr (s nárazníkom alebo bez neho, so smerníkom na koniec radu alebo bez neho) a pomocou jednorozmerného poľa. Na príklade atómu s hodnotou typu int a smerníkom nasl je podrobne ukázaná implementácia radu s nárazníkom bez smerníka na koniec: inicializácia, test prázdnosti, vkladanie, zistenie hodnoty na začiatku a odoberanie. Funkčnosť sa overuje vložením znakov reťazca „ahoj“ do radu a výpisom prvého prvku. Odoberanie je rovnaké ako pri zásobníku s nárazníkom, mení však adresu začiatku radu, preto sa funkcia volá odkazom.

• - Rad je štruktúra typu FIFO (first in, first out): vkladá sa na koniec, vyberá sa zo začiatku.
• - Implementácie radu: rekurzívne štruktúry (s nárazníkom/bez, so smerníkom na koniec/bez) a jednorozmerné pole.
• - Rad reprezentuje smerník na začiatok radu; nárazník má nasl nastavené na 0 ako značku konca.
• - Rad je prázdny, ak nasl nárazníka (začiatku radu) je 0.
• - Vkladanie hľadá koniec pomocným smerníkom, nárazník sa stane atómom s hodnotou a vytvorí sa nový nárazník.
• - Funkcia hodnota vracia prvok zo začiatku radu cez odkaz a len ak rad nie je prázdny.
• - Odoberanie posunie začiatok na nasledujúci atóm a pôvodný uvoľní; vyžaduje volanie odkazom (dve hviezdičky).

Zhrnutie pripravené s pomocou AI z prepisu videa.