Algoritmy a dátové štruktúry prednáška 04

Zhrnutie prednášky

Prednáška po organizačných pokynoch k prvej domácej úlohe pokračuje analýzou základných dátových štruktúr z pohľadu rozhrania (interface) aj implementácie. Predstavuje sa zásobník (LIFO, operácie push a pop) s dvomi implementáciami - pomocou spájaného zoznamu (flexibilná veľkosť, ale pointerová réžia a horšia práca s cache) a pomocou poľa pevnej veľkosti (rýchlejšie, cache-friendly, no vyžaduje vopred známy horný odhad kapacity). Podobne sa rozoberá fronta (FIFO) - jej implementácia spájaným zoznamom (metafora čakárne u lekára) a implementácia v poli, kde naivné posúvanie prvkov pri výbere (metafora pokladne v hypermarkete) vedie k lineárnej zložitosti, čo sa rieši pomocou kruhového bufferu (metafora vydávania poradových lístkov). Záverečná časť prednášky predstavuje dynamické pole (vektor/ArrayList/list) s operáciami indexovania v konštantnom čase a pridávania na koniec (append/push_back), pričom sa pomocou zdvojnásobovania kapacity a argumentu s pokladničkou dokazuje, že táto operácia má amortizovanú konštantnú časovú zložitosť, a diskutuje sa aj o plytvaní pamäťou, voľbe rastového koeficientu a stratégii zmenšovania poľa.

• Zásobník (LIFO) - operácie push a pop
• Implementácia zásobníka spájaným zoznamom vs. poľom pevnej veľkosti
• Fronta (FIFO) - implementácia spájaným zoznamom (čakáreň)
• Fronta v poli - problém posúvania prvkov (pokladňa v hypermarkete)
• Kruhový buffer ako riešenie fronty v poli (výdaj lístočkov)
• Dynamické pole (vektor/ArrayList) - indexovanie a append/push_back
• Zdvojnásobovanie kapacity a amortizovaná konštantná zložitosť (dôkaz pokladničkou)
• Plytvanie pamäťou, rastový koeficient a zmenšovanie poľa

Zhrnutie pripravené s pomocou AI z prepisu videa.