Struktury danych
Struktury danych to darmowa interaktywna symulacja ze StudyFi Lab. Działa bezpośrednio w przeglądarce, bez rejestracji i bez instalacji.
Stosy, kolejki, listy, drzewa i grafy
Eksperymenty
Stos
Stos działa jak sterta talerzy: dokładasz (push) i zdejmujesz (pop) tylko z góry, więc to, co weszło ostatnie, wychodzi pierwsze (LIFO). Wskaźnik top pokazuje wierzchołek; push i pop trwają O(1). Korzystają z niego Cofnij w edytorze, przycisk Wstecz w przeglądarce i wywołania funkcji w programie (stos wywołań).
Spróbuj: Wykonaj push 1, 2, 3, a potem trzy razy pop — liczby wyjdą w odwrotnej kolejności. Potem spróbuj dziewiątego push.
Kolejka
Kolejka działa jak kolejka do kasy: nowe elementy dołączają na końcu (enqueue, wskaźnik rear) i wychodzą z przodu (dequeue, wskaźnik front), więc kto pierwszy przyszedł, ten pierwszy wychodzi (FIFO). W tablicy przechowuje się ją jako bufor cykliczny: oba wskaźniki po ostatniej komórce wracają do komórki 0, dlatego enqueue i dequeue trwają O(1). Kolejki obsługują drukarkę, żądania do serwera i buforowanie wideo.
Spróbuj: Włącz widok cykliczny, dodaj sześć liczb, usuń cztery i dodaj kolejne cztery — zobacz, jak rear przeskakuje z komórki 7 do komórki 0.
Lista jednokierunkowa
Każdy węzeł przechowuje wartość i wskaźnik next do następnego węzła; ostatni wskazuje na null, a lista zaczyna się od wskaźnika head. Wstawienie na początek kosztuje O(1), ale dojście do pozycji i lub szukanej wartości wymaga przejścia węzeł po węźle — O(n). W przeciwieństwie do tablicy nic się nie przesuwa, tylko przepina wskaźniki; tak działają playlisty, historie kroków i listy wolnej pamięci.
Spróbuj: Wyszukaj ostatnią wartość i policz kroki wskaźnika, a potem wstaw liczbę na początek — to zawsze jeden krok.
Drzewo BST
W każdym węźle mniejsze wartości są po lewej, a większe po prawej. Dlatego wyszukiwanie i wstawianie idą jedną ścieżką od korzenia i trwają O(h), gdzie h to wysokość drzewa — w drzewie zrównoważonym h ≈ log₂ n. Usuwanie ma trzy przypadki: liść po prostu znika, węzeł z jednym dzieckiem zastępuje to dziecko, a węzeł z dwojgiem dzieci przejmuje wartość następnika w porządku in-order. Przejście in-order wypisuje wartości posortowane; podobne drzewa napędzają indeksy baz danych.
Spróbuj: Usuń korzeń — ma dwoje dzieci, więc zobaczysz szukanie następnika. Potem spróbuj „Wstaw posortowane wartości”: drzewo zamienia się w listę, a wysokość rośnie do n.
Graf: BFS i DFS
Przeszukiwanie wszerz (BFS) pobiera węzły z kolejki, więc najpierw odwiedza wszystkich sąsiadów startu, potem ich sąsiadów — warstwa po warstwie, dzięki czemu znajduje najkrótszą ścieżkę pod względem liczby krawędzi. Przeszukiwanie w głąb (DFS) pobiera węzły ze stosu i idzie jak najdalej, zanim się cofnie. Oba odwiedzają każdy węzeł i krawędź raz: O(V + E). BFS wykorzystują nawigacje i „znajomi znajomych”, DFS — labirynty i wykrywanie cykli.
Spróbuj: Przechodź krok po kroku od węzła 0 i porównuj kolejkę ze stosem. Potem zmień start na węzeł 7 — kolejność odwiedzin zmieni się całkowicie.
Najczęstsze pytania
Czym jest Struktury danych?
Struktury danych to darmowa interaktywna symulacja ze StudyFi Lab. Działa bezpośrednio w przeglądarce, bez rejestracji i bez instalacji. Stosy, kolejki, listy, drzewa i grafy
Czy aplikacja Struktury danych jest darmowa?
Tak. Aplikacja Struktury danych jest całkowicie darmowa. Działa w przeglądarce na komputerze, tablecie i telefonie, a konto nie jest potrzebne.
Co mogę odkryć w aplikacji Struktury danych?
Stos, Kolejka, Lista jednokierunkowa, Drzewo BST, Graf: BFS i DFS.
Co pokazuje eksperyment „Stos”?
Stos działa jak sterta talerzy: dokładasz (push) i zdejmujesz (pop) tylko z góry, więc to, co weszło ostatnie, wychodzi pierwsze (LIFO). Wskaźnik top pokazuje wierzchołek; push i pop trwają O(1). Korzystają z niego Cofnij w edytorze, przycisk Wstecz w przeglądarce i wywołania funkcji w programie (stos wywołań).
Co pokazuje eksperyment „Kolejka”?
Kolejka działa jak kolejka do kasy: nowe elementy dołączają na końcu (enqueue, wskaźnik rear) i wychodzą z przodu (dequeue, wskaźnik front), więc kto pierwszy przyszedł, ten pierwszy wychodzi (FIFO). W tablicy przechowuje się ją jako bufor cykliczny: oba wskaźniki po ostatniej komórce wracają do komórki 0, dlatego enqueue i dequeue trwają O(1). Kolejki obsługują drukarkę, żądania do serwera i buforowanie wideo.
Uczysz się do sprawdzianu?
Wgraj swoje notatki, a StudyFi zrobi z nich fiszki, testy i podcasty.