Dátové štruktúry
Dátové štruktúry je bezplatná interaktívna simulácia zo StudyFi Lab. Beží priamo v prehliadači, bez registrácie a bez inštalácie.
Zásobník, front, zoznam, strom a graf
Pokusy
Zásobník
Zásobník funguje ako kôpka tanierov: pridávaš (push) aj odoberáš (pop) iba hore, takže čo prišlo posledné, odchádza prvé (LIFO). Ukazovateľ top určuje vrchol; push aj pop trvajú O(1). Používa ho tlačidlo Späť v editore, história prehliadača aj volania funkcií v programe (call stack).
Vyskúšaj: Vlož 1, 2, 3 a potom trikrát daj pop — čísla vyjdú v opačnom poradí. Skús vložiť deviate číslo.
Front
Front funguje ako rad pri pokladni: nové prvky prichádzajú na koniec (enqueue, ukazovateľ rear) a odchádzajú zo začiatku (dequeue, ukazovateľ front), takže kto prišiel prvý, ide prvý (FIFO). V poli sa front ukladá ako kruhový buffer: oba ukazovatele sa po poslednom slote vrátia na slot 0, takže enqueue aj dequeue trvajú O(1). Fronty riadia tlačiareň, spracovanie požiadaviek na serveri aj vyrovnávaciu pamäť videa.
Vyskúšaj: Zapni kruhový pohľad, vlož šesť čísel, štyri odober a vlož ďalšie štyri — sleduj, ako rear preskočí zo slotu 7 na slot 0.
Spájaný zoznam
Každý uzol nesie hodnotu a odkaz next na ďalší uzol; posledný ukazuje na null a zoznam začína ukazovateľom head. Vložiť na začiatok stojí O(1), ale k prvku na pozícii i alebo k hľadanej hodnote sa musíš „prejsť“ uzol po uzle — O(n). Na rozdiel od poľa nič neposúvaš, len prepojíš odkazy; tak fungujú playlisty, história krokov či zoznamy voľných blokov pamäte.
Vyskúšaj: Vyhľadaj poslednú hodnotu a spočítaj kroky ukazovateľa, potom vlož číslo na začiatok — tam je to vždy len jeden krok.
Binárny vyhľadávací strom
V každom uzle platí: vľavo sú menšie hodnoty, vpravo väčšie. Hľadanie aj vkladanie preto ide iba jednou cestou od koreňa a trvá O(h), kde h je výška stromu — pri vyváženom strome h ≈ log₂ n. Mazanie má tri prípady: list jednoducho zmizne, uzol s jedným potomkom nahradí jeho potomok a uzol s dvoma potomkami prevezme hodnotu in-order nasledovníka. Prechod in-order vypíše hodnoty zoradené; podobné stromy poháňajú databázové indexy.
Vyskúšaj: Zmaž koreň — má dvoch potomkov, takže uvidíš hľadanie nasledovníka. Potom skús „Vložiť zoradené hodnoty“: strom sa zvrhne na zoznam a výška narastie na n.
Graf: BFS a DFS
Prehľadávanie do šírky (BFS) berie uzly z frontu, takže prejde najprv všetkých susedov štartu, potom ich susedov — vrstvu po vrstve, a nájde tak najkratšiu cestu v počte hrán. Prehľadávanie do hĺbky (DFS) berie uzly zo zásobníka a ide čo najďalej, kým sa vráti. Obe navštívia každý uzol a hranu raz: O(V + E). BFS používajú navigácie a „priatelia priateľov“ na sociálnych sieťach, DFS bludiská a hľadanie cyklov.
Vyskúšaj: Krokuj od uzla 0 a porovnaj obsah frontu a zásobníka. Potom zmeň štart na uzol 7 — poradie návštev sa úplne zmení.
Časté otázky
Čo je Dátové štruktúry?
Dátové štruktúry je bezplatná interaktívna simulácia zo StudyFi Lab. Beží priamo v prehliadači, bez registrácie a bez inštalácie. Zásobník, front, zoznam, strom a graf
Je aplikácia Dátové štruktúry zadarmo?
Áno. Aplikácia Dátové štruktúry je úplne zadarmo. Funguje v prehliadači na počítači, tablete aj telefóne a nepotrebuješ k nej účet.
Čo môžem preskúmať v aplikácii Dátové štruktúry?
Zásobník, Front, Spájaný zoznam, Binárny vyhľadávací strom, Graf: BFS a DFS.
Čo ukazuje pokus „Zásobník“?
Zásobník funguje ako kôpka tanierov: pridávaš (push) aj odoberáš (pop) iba hore, takže čo prišlo posledné, odchádza prvé (LIFO). Ukazovateľ top určuje vrchol; push aj pop trvajú O(1). Používa ho tlačidlo Späť v editore, história prehliadača aj volania funkcií v programe (call stack).
Čo ukazuje pokus „Front“?
Front funguje ako rad pri pokladni: nové prvky prichádzajú na koniec (enqueue, ukazovateľ rear) a odchádzajú zo začiatku (dequeue, ukazovateľ front), takže kto prišiel prvý, ide prvý (FIFO). V poli sa front ukladá ako kruhový buffer: oba ukazovatele sa po poslednom slote vrátia na slot 0, takže enqueue aj dequeue trvajú O(1). Fronty riadia tlačiareň, spracovanie požiadaviek na serveri aj vyrovnávaciu pamäť videa.
Učíš sa na test?
Nahraj svoje poznámky a StudyFi z nich urobí kartičky, testy a podcasty.